Single column index in SQL - Time & Space Complexity

Time Complexity: Single column index

O(log n)

Understanding Time Complexity

When we use a single column index in a database, it helps us find data faster. We want to understand how the time to find data changes as the table grows.

How does using an index affect the speed of searching through many rows?

Scenario Under Consideration

Analyze the time complexity of the following SQL query using a single column index.

SELECT *
FROM employees
WHERE employee_id = 12345;
-- Assume employee_id has a single column index

This query looks for one employee by their unique ID using an index on that column.

Identify Repeating Operations

What repeats when the database searches for the employee?

• Primary operation: The database traverses the index tree to find the matching employee_id.
• How many times: It moves through levels of the index, which grows slowly compared to the number of rows.

How Execution Grows With Input

As the number of employees grows, the search steps increase slowly.

Input Size (n)	Approx. Operations
10	About 3 steps
100	About 7 steps
1000	About 10 steps

Pattern observation: The steps grow slowly, adding only a few more as the table gets much bigger.

Final Time Complexity

Time Complexity: O(log n)

This means the search time grows slowly as the table gets bigger, making lookups efficient.

Common Mistake

[X] Wrong: "Using an index makes the search time the same no matter how big the table is."

[OK] Correct: The search time still grows as the table grows, but only slowly, not instantly or fixed.

Interview Connect

Understanding how indexes speed up searches helps you explain database efficiency clearly. This skill shows you know how data grows and how to keep queries fast.

Self-Check

"What if the index was on two columns instead of one? How would the time complexity change?"