Index maintenance in MySQL - Time & Space Complexity

Time Complexity: Index maintenance

O(log n)

Understanding Time Complexity

When we add or remove data in a database, the indexes need to update too.

We want to know how the time to update indexes changes as data grows.

Scenario Under Consideration

Analyze the time complexity of the following index update during an insert.

INSERT INTO employees (id, name, department) VALUES (101, 'Alice', 'Sales');
-- The database updates the index on 'id' after this insert
    

This code inserts a new row and updates the index on the 'id' column.

Identify Repeating Operations

When inserting, the database finds the right place in the index tree to add the new key.

• Primary operation: Traversing the index tree from root to leaf.
• How many times: Once per insert, following the tree height.

How Execution Grows With Input

As the table grows, the index tree gets taller, but only slowly.

Input Size (n)	Approx. Operations
10	About 2 steps down the tree
100	About 3 steps down the tree
1000	About 4 steps down the tree

Pattern observation: The steps grow slowly, roughly with the height of the tree, not the total rows.

Final Time Complexity

Time Complexity: O(log n)

This means the time to update the index grows slowly as the data grows, making inserts efficient.

Common Mistake

[X] Wrong: "Updating an index takes as long as scanning all rows."

[OK] Correct: Indexes use tree structures that let the database jump quickly to the right spot without checking every row.

Interview Connect

Understanding how indexes update helps you explain why databases stay fast even with lots of data.

Self-Check

"What if the index was a simple list instead of a tree? How would the time complexity change?"