When indexes help and when they hurt in SQL - Time & Space Complexity

Time Complexity: When indexes help and when they hurt

O(log n)

Understanding Time Complexity

Indexes can speed up database searches but sometimes slow down other operations.

We want to understand when using an index helps and when it might hurt performance.

Scenario Under Consideration

Analyze the time complexity of this query using an index.

-- Assume an index exists on column 'name'
SELECT * FROM employees WHERE name = 'Alice';

-- Insert operation
INSERT INTO employees (id, name, department) VALUES (101, 'Bob', 'Sales');
    

The first query searches for a specific name using an index. The second inserts a new row, which may update the index.

Identify Repeating Operations

Look at what repeats during these operations.

• Primary operation for SELECT: Searching the index tree to find matching rows.
• How many times: Depends on the height of the index tree, usually much less than scanning all rows.
• Primary operation for INSERT: Adding a new entry to the index structure.
• How many times: Once per insert, but involves updating the index which can be costly.

How Execution Grows With Input

As the table grows, the index search stays efficient, but inserts get a bit slower.

Input Size (n)	Approx. Operations for SELECT	Approx. Operations for INSERT
10	About 3 steps (small tree height)	Simple insert + index update
100	About 4 steps	Insert + more index updates
1000	About 5 steps	Insert + even more index updates

Pattern observation: SELECT grows slowly with input size, INSERT grows a bit faster due to index maintenance.

Final Time Complexity

Time Complexity: O(log n)

This means searching with an index grows slowly as data grows, but insertions cost more because the index must be updated.

Common Mistake

[X] Wrong: "Adding an index always makes everything faster."

[OK] Correct: Indexes speed up searches but slow down inserts, updates, and deletes because the index must be maintained.

Interview Connect

Understanding when indexes help or hurt shows you know how databases balance speed and cost, a key skill for real projects.

Self-Check

"What if we added multiple indexes on different columns? How would that affect insert and search time complexity?"