How an index works (B-tree mental model) in SQL - Performance & Efficiency

Time Complexity: How an index works (B-tree mental model)

O(log n)

Understanding Time Complexity

We want to understand how fast searching is when using an index in a database.

Specifically, how the work grows as the data gets bigger.

Scenario Under Consideration

Analyze the time complexity of this query using a B-tree index.

SELECT * FROM employees
WHERE employee_id = 12345;
-- Assume employee_id is indexed with a B-tree

This query looks up one employee by their ID using a B-tree index.

Identify Repeating Operations

Look at what repeats when searching the B-tree.

• Primary operation: Comparing the search key to node keys in the B-tree.
• How many times: Once per tree level, moving down from root to leaf.

How Execution Grows With Input

As the number of employees grows, the tree gets taller slowly.

Input Size (n)	Approx. Operations
10	About 2 comparisons
100	About 3 comparisons
1000	About 4 comparisons

Pattern observation: The number of steps grows very slowly, adding just one step for about every 10 times more data.

Final Time Complexity

Time Complexity: O(log n)

This means the search time grows slowly as data grows, making lookups efficient even for large data.

Common Mistake

[X] Wrong: "Searching an index is as slow as scanning all rows one by one."

[OK] Correct: The B-tree index lets the database skip most rows by jumping through tree levels, so it does not check every row.

Interview Connect

Knowing how indexes speed up searches helps you explain database efficiency clearly and confidently.

Self-Check

"What if the index was a simple list instead of a B-tree? How would the time complexity change?"