Why indexes matter in SQL - Performance Analysis

Time Complexity: Why indexes matter

O(n) without index, O(log n) with index

Understanding Time Complexity

We want to understand how using indexes changes the speed of searching data in a database.

How does the time to find data grow as the database gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following SQL queries.

-- Query without index
SELECT * FROM employees WHERE last_name = 'Smith';

-- Create index on last_name
CREATE INDEX idx_last_name ON employees(last_name);

-- Query with index on last_name
SELECT * FROM employees WHERE last_name = 'Smith';
    

The first query searches without an index, scanning all rows. The second uses an index to find matches faster.

Identify Repeating Operations

Look at what repeats when searching for data.

• Primary operation: Checking each row's last_name in the table scan (no index) or searching the index tree.
• How many times: Without index, once per row (n times). With index, fewer steps following tree branches (logarithmic steps).

How Execution Grows With Input

As the table grows, the search time changes differently with and without an index.

Input Size (n)	Approx. Operations Without Index	Approx. Operations With Index
10	10 checks	About 3 steps
100	100 checks	About 7 steps
1000	1000 checks	About 10 steps

Pattern observation: Without index, operations grow directly with data size. With index, operations grow slowly even as data grows large.

Final Time Complexity

Time Complexity: O(n) without index, O(log n) with index

This means searching without an index takes longer as data grows, but with an index, search stays fast even for big data.

Common Mistake

[X] Wrong: "Adding an index always makes queries faster no matter what."

[OK] Correct: Indexes speed up searches but can slow down data changes like inserts or updates because the index must be updated too.

Interview Connect

Understanding how indexes affect search speed helps you explain how databases handle large data efficiently, a useful skill in many real projects.

Self-Check

"What if the index was on a column with many repeated values? How would that affect the time complexity?"