Time Complexity: Unique indexes
O(log n)
0
0
Unique indexes in MySQL - Time & Space Complexity
Understanding Time Complexity
When we use unique indexes in a database, it helps keep data clean by preventing duplicates.
We want to understand how the time to check uniqueness grows as the data grows.
Scenario Under Consideration
Analyze the time complexity of the following code snippet.
CREATE TABLE users (
id INT PRIMARY KEY,
email VARCHAR(255),
UNIQUE INDEX unique_email (email)
);
INSERT INTO users (id, email) VALUES (1, 'a@example.com');
INSERT INTO users (id, email) VALUES (2, 'b@example.com');
-- Attempt to insert duplicate email
INSERT INTO users (id, email) VALUES (3, 'a@example.com');
This code creates a table with a unique index on the email column and tries to insert rows, including a duplicate email.
Identify Repeating Operations
- Primary operation: Checking if the email already exists in the unique index.
- How many times: Once per insert operation, the database searches the index to find duplicates.
How Execution Grows With Input
As more rows are added, the database must search a larger index to check uniqueness.
| Input Size (n) | Approx. Operations |
|---|---|
| 10 | About 4 steps to find or reject duplicate |
| 100 | About 7 steps |
| 1000 | About 10 steps |
Pattern observation: The number of steps grows slowly as data grows, not one-by-one.
Final Time Complexity
Time Complexity: O(log n)
This means checking for duplicates takes a little more time as data grows, but it grows slowly and efficiently.
Common Mistake
[X] Wrong: "Checking for duplicates takes the same time no matter how many rows there are."
[OK] Correct: The database uses a special structure that lets it find duplicates faster than checking every row one by one.
Interview Connect
Understanding how unique indexes work and their time cost shows you know how databases keep data clean efficiently.
Self-Check
"What if the unique index was on multiple columns instead of one? How would the time complexity change?"