Index selection strategy in MySQL - Time & Space Complexity

Time Complexity: Index selection strategy

O(log n)

Understanding Time Complexity

When a database uses an index to find data, it can do it faster than searching every row.

We want to understand how choosing the right index affects the speed of finding data as the table grows.

Scenario Under Consideration

Analyze the time complexity of this query using an index.

SELECT * FROM employees
WHERE last_name = 'Smith';

-- Assume there is an index on last_name
    

This query looks for all employees with the last name 'Smith' using an index on the last_name column.

Identify Repeating Operations

Look at what repeats when the database searches for matching rows.

• Primary operation: Searching the index tree to find matching entries.
• How many times: The search follows a path down the index, which grows slowly as the table grows.

How Execution Grows With Input

As the table gets bigger, the index search path grows slowly, not linearly.

Input Size (n)	Approx. Operations
10	About 3 steps
100	About 7 steps
1000	About 10 steps

Pattern observation: The number of steps grows slowly, like climbing a short ladder, even if the table grows a lot.

Final Time Complexity

Time Complexity: O(log n)

This means the time to find data grows slowly as the table gets bigger, thanks to the index.

Common Mistake

[X] Wrong: "Using an index means the query always runs instantly no matter the table size."

[OK] Correct: Even with an index, the search takes more steps as the table grows, just much fewer than scanning all rows.

Interview Connect

Understanding how indexes speed up searches helps you explain why databases stay fast with lots of data.

Self-Check

"What if the query searched on a column without an index? How would the time complexity change?"