Index impact on INSERT and UPDATE in SQL - Time & Space Complexity

Time Complexity: Index impact on INSERT and UPDATE

O(n x k)

Understanding Time Complexity

When we add or change data in a table with indexes, the time it takes can change.

We want to understand how indexes affect the speed of INSERT and UPDATE commands.

Scenario Under Consideration

Analyze the time complexity of the following SQL commands with indexes.

-- Insert a new row
INSERT INTO employees (id, name, department) VALUES (101, 'Alice', 'HR');

-- Update an existing row
UPDATE employees SET department = 'Finance' WHERE id = 101;
    

This code adds a new employee and then updates their department in a table that has indexes.

Identify Repeating Operations

Look at what happens repeatedly when these commands run.

• Primary operation: Updating the index entries for each affected row.
• How many times: Once per row inserted or updated, plus once per index on the table.

How Execution Grows With Input

As you add or update more rows, the work grows with the number of rows and indexes.

Input Size (n rows)	Approx. Operations
10	10 x (1 + number of indexes)
100	100 x (1 + number of indexes)
1000	1000 x (1 + number of indexes)

Pattern observation: The time grows linearly with the number of rows and the number of indexes.

Final Time Complexity

Time Complexity: O(n x k)

This means the time grows with the number of rows (n) and the number of indexes (k) that need updating.

Common Mistake

[X] Wrong: "Indexes only slow down SELECT queries, so INSERT and UPDATE speed stay the same."

[OK] Correct: Every INSERT or UPDATE must also update all indexes, so more indexes mean more work and slower writes.

Interview Connect

Understanding how indexes affect data changes helps you design databases that balance fast reads and writes.

Self-Check

What if we added a new index on the department column? How would that change the time complexity for INSERT and UPDATE?