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?"

Practice

1. What is the main purpose of maintaining indexes in a MySQL database?

easy

A. To speed up data searches and queries

B. To increase the size of the database

C. To delete all data from tables

D. To backup the database automatically

Solution

1. Step 1: Understand what indexes do

   Indexes help the database find data faster, like an index in a book.

2. Step 2: Identify the main benefit of index maintenance

   Maintaining indexes keeps searches quick and efficient.

3. Final Answer:

   To speed up data searches and queries -> Option A

4. Quick Check:

   Indexes improve search speed = D [OK]

Hint: Indexes speed up queries by organizing data [OK]

Common Mistakes:

• Thinking indexes increase database size only
• Confusing index maintenance with data backup
• Believing indexes delete data

2. Which of the following is the correct syntax to drop an index named idx_name from a table users in MySQL?

easy

A. DELETE INDEX idx_name FROM users;

B. DROP INDEX idx_name ON users;

C. REMOVE INDEX idx_name IN users;

D. DROP idx_name FROM users;

Solution

1. Step 1: Recall MySQL syntax for dropping an index

   The correct command is DROP INDEX index_name ON table_name;.

2. Step 2: Match the syntax with options

   DROP INDEX idx_name ON users; matches the correct syntax exactly.

3. Final Answer:

   DROP INDEX idx_name ON users; -> Option B

4. Quick Check:

   DROP INDEX ... ON ... is correct syntax = B [OK]

Hint: Use DROP INDEX index_name ON table_name; to remove indexes [OK]

Common Mistakes:

• Using DELETE or REMOVE instead of DROP
• Omitting ON keyword
• Wrong keyword order

3. Given the table products with an index on category_id, what will be the effect of running OPTIMIZE TABLE products;?

medium

A. It renames the products table

B. It deletes all rows from the products table

C. It adds a new index on category_id automatically

D. It rebuilds the table and its indexes to improve performance

Solution

1. Step 1: Understand what OPTIMIZE TABLE does

   OPTIMIZE TABLE rebuilds the table and its indexes to reduce fragmentation and improve speed.

2. Step 2: Analyze the options

   Only It rebuilds the table and its indexes to improve performance correctly describes this effect.

3. Final Answer:

   It rebuilds the table and its indexes to improve performance -> Option D

4. Quick Check:

   OPTIMIZE TABLE rebuilds table and indexes = A [OK]

Hint: OPTIMIZE TABLE rebuilds indexes and table for better speed [OK]

Common Mistakes:

• Thinking OPTIMIZE deletes data
• Assuming it adds indexes automatically
• Confusing it with renaming tables

4. You tried to drop an index using DROP INDEX idx_user ON users; but got an error. What is a likely cause?

medium

A. The table users does not exist

B. You must use DELETE INDEX instead of DROP INDEX

C. The index name idx_user does not exist on the table

D. You need to restart the MySQL server before dropping indexes

Solution

1. Step 1: Check common reasons for DROP INDEX errors

   An error usually occurs if the index name is wrong or missing.

2. Step 2: Evaluate the options

   The index name idx_user does not exist on the table is the most common cause; other options are incorrect commands or unnecessary actions.

3. Final Answer:

   The index name idx_user does not exist on the table -> Option C

4. Quick Check:

   Wrong index name causes DROP INDEX error = C [OK]

Hint: Verify index name exists before dropping it [OK]

Common Mistakes:

• Using DELETE instead of DROP
• Assuming server restart is needed
• Not checking table existence first

5. You have a large table orders with a composite index on (customer_id, order_date). After frequent inserts and deletes, queries on customer_id are slow. What is the best index maintenance step to improve performance?

hard

A. Run OPTIMIZE TABLE orders; to rebuild the table and indexes

B. Drop the composite index and create separate indexes on each column

C. Delete all rows and reload the table

D. Rename the table to refresh indexes

Solution

1. Step 1: Understand index fragmentation impact

   Frequent inserts and deletes cause index fragmentation, slowing queries.

2. Step 2: Choose the best maintenance action

   OPTIMIZE TABLE rebuilds indexes and reduces fragmentation, improving query speed.

3. Step 3: Evaluate other options

   Dropping and recreating indexes separately may not help and can be costly; deleting data or renaming table is unrelated.

4. Final Answer:

   Run OPTIMIZE TABLE orders; to rebuild the table and indexes -> Option A

5. Quick Check:

   OPTIMIZE TABLE fixes fragmentation = A [OK]

Hint: Use OPTIMIZE TABLE to fix fragmented indexes after many changes [OK]

Common Mistakes:

• Dropping composite index without reason
• Thinking renaming table refreshes indexes
• Deleting data instead of maintaining indexes