Creating indexes in MySQL - Performance & Efficiency

Time Complexity: Creating indexes

O(n)

Understanding Time Complexity

When we create indexes in a database, it helps us find data faster. But creating these indexes also takes some time.

We want to know how the time to create an index grows as the amount of data grows.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

CREATE INDEX idx_customer_name ON customers(name);
    

This code creates an index on the "name" column of the "customers" table to speed up searches by name.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Scanning all rows in the table to build the index structure.
• How many times: Once for each row in the table.

How Execution Grows With Input

As the number of rows grows, the time to create the index grows roughly in the same way.

Input Size (n)	Approx. Operations
10	About 10 operations to read and insert into the index
100	About 100 operations
1000	About 1000 operations

Pattern observation: The time grows roughly in direct proportion to the number of rows.

Final Time Complexity

Time Complexity: O(n)

This means creating the index takes time proportional to the number of rows in the table.

Common Mistake

[X] Wrong: "Creating an index is instant and does not depend on table size."

[OK] Correct: The database must look at every row to build the index, so more rows mean more work and more time.

Interview Connect

Understanding how index creation time grows helps you explain database performance clearly and shows you know how data size affects operations.

Self-Check

"What if the index was created on multiple columns instead of one? How would the time complexity change?"