CREATE INDEX syntax in SQL - Time & Space Complexity

Time Complexity: CREATE INDEX syntax

O(n log n)

Understanding Time Complexity

Let's explore how the time to create an index changes as the data grows.

We want to know how the work done by the database increases when building an index on a table.

Scenario Under Consideration

Analyze the time complexity of the following SQL command.

CREATE INDEX idx_customer_name
ON customers (last_name);
    

This command creates an index on the last_name column of the customers table to speed up searches.

Identify Repeating Operations

When creating an index, the database must process each row to build the index structure.

• Primary operation: Reading each row's last_name value and inserting it into the index.
• How many times: Once for every row in the customers table.

How Execution Grows With Input

As the number of rows grows, the work to create the index grows too.

Input Size (n)	Approx. Operations
10	About 10 reads and inserts
100	About 100 reads and inserts
1000	About 1000 reads and inserts

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

Final Time Complexity

Time Complexity: O(n log n)

This means creating the index takes a bit more than just looking at each row once, because it also organizes the data efficiently.

Common Mistake

[X] Wrong: "Creating an index is just as fast as scanning the table once, so it is O(n)."

[OK] Correct: Building the index involves sorting or organizing data, which adds extra steps, making it slower than a simple scan.

Interview Connect

Understanding how index creation time grows helps you explain database performance clearly and shows you know what happens behind the scenes.

Self-Check

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