Composite indexes in MySQL - Time & Space Complexity

Time Complexity: Composite indexes

O(log n)

Understanding Time Complexity

When we use composite indexes in a database, we want to know how they affect the speed of searching data.

We ask: How does the time to find data grow as the table gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following SQL query using a composite index.

CREATE INDEX idx_name_age ON users(name, age);

SELECT * FROM users
WHERE name = 'Alice' AND age = 30;
    

This code creates a composite index on the columns name and age, then searches for users matching both.

Identify Repeating Operations

Look at what repeats when searching with this index.

• Primary operation: The database looks up entries in the index tree for name and then age.
• How many times: It follows a path down the index tree, which grows with the number of unique name and age pairs.

How Execution Grows With Input

As the table grows, the index tree grows slowly, so searching stays fast.

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

Pattern observation: The number of steps grows slowly, not directly with the number of rows.

Final Time Complexity

Time Complexity: O(log n)

This means the search time grows slowly as the table gets bigger, making lookups efficient.

Common Mistake

[X] Wrong: "Adding more columns to the composite index always makes searches faster."

[OK] Correct: Adding columns that are not used in the query or in the wrong order can make the index less useful or slower.

Interview Connect

Understanding how composite indexes affect search speed shows you know how databases handle data efficiently, a useful skill for many projects.

Self-Check

What if we changed the query to search only by age without name? How would the time complexity change?