Why indexes speed up queries in MySQL - Performance Analysis

Time Complexity: Why indexes speed up queries

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

Understanding Time Complexity

When we use indexes in databases, queries can find data faster. We want to understand how using an index changes the work the database does as the data grows.

How does the time to find data change when we have an index versus when we don't?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT * FROM employees WHERE employee_id = 12345;

-- Assume employee_id is indexed in the second case
    

This query looks for one employee by their ID. We compare how it runs with and without an index on employee_id.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Scanning rows to find the matching employee_id.
• How many times: Without an index, it checks each row one by one. With an index, it uses a tree search to jump directly to the right row.

How Execution Grows With Input

Explain the growth pattern intuitively.

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

Pattern observation: Without an index, the work grows directly with the number of rows. With an index, the work grows slowly, adding just a few steps even as data grows a lot.

Final Time Complexity

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

This means without an index, the database checks every row, but with an index, it quickly narrows down to the right row using fewer steps.

Common Mistake

[X] Wrong: "Adding an index makes the query instantly fast no matter what."

[OK] Correct: Indexes help a lot, but the speed still depends on data size and query type. Some queries don't benefit from indexes.

Interview Connect

Understanding how indexes change query speed shows you know how databases handle data efficiently. This skill helps you write faster queries and explain your choices clearly.

Self-Check

"What if the query searched for a range of employee IDs instead of one? How would the time complexity change with and without an index?"