B-tree index (default) behavior in PostgreSQL - Time & Space Complexity

Time Complexity: B-tree index (default) behavior

O(log n)

Understanding Time Complexity

We want to understand how fast a B-tree index helps find data in a database as the data grows.

How does the time to search change when we add more rows?

Scenario Under Consideration

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

-- Assume a table 'users' with a B-tree index on 'email'
SELECT * FROM users WHERE email = '[e-mail]';
    

This query looks up a user by email using the B-tree index to speed up the search.

Identify Repeating Operations

In a B-tree search, the main repeating operation is moving down tree levels.

• Primary operation: Comparing the search key with node keys at each tree level.
• How many times: Once per tree level, which grows slowly as data grows.

How Execution Grows With Input

As the number of rows grows, the tree gets taller but only 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, roughly adding one step for every tenfold increase in 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 tables.

Common Mistake

[X] Wrong: "Searching with a B-tree index takes the same time as scanning every row one by one."

[OK] Correct: A B-tree index narrows down the search quickly by jumping through tree levels, so it does not check every row.

Interview Connect

Knowing how B-tree indexes scale helps you explain why databases stay fast as data grows, a key skill for working with real systems.

Self-Check

"What if the index was a hash index instead? How would the time complexity change for exact match searches?"