Time Complexity: Unique index behavior
O(log n)
0
0
Unique index behavior in SQL - Time & Space Complexity
Understanding Time Complexity
When we use a unique index in a database, it helps quickly find if a value already exists.
We want to know how the time to check or insert changes as the data grows.
Scenario Under Consideration
Analyze the time complexity of the following SQL commands involving a unique index.
CREATE UNIQUE INDEX idx_email ON users(email);
INSERT INTO users (email, name) VALUES ('a@example.com', 'Alice');
SELECT * FROM users WHERE email = 'a@example.com';
This code creates a unique index on the email column, inserts a new user, and searches by email.
Identify Repeating Operations
Look at what repeats when we insert or search using the unique index.
- Primary operation: Searching the index tree to find the right spot or value.
- How many times: The search steps grow slowly as data grows, not checking every row.
How Execution Grows With Input
As the number of users grows, the steps to find or insert an email grow slowly.
| Input Size (n) | Approx. Operations |
|---|---|
| 10 | About 3 steps |
| 100 | About 7 steps |
| 1000 | About 10 steps |
Pattern observation: The steps grow slowly, adding only a few more as data grows much larger.
Final Time Complexity
Time Complexity: O(log n)
This means the time to find or insert grows slowly, even if the data gets very big.
Common Mistake
[X] Wrong: "Checking a unique index takes as long as scanning all rows."
[OK] Correct: The unique index uses a tree structure that jumps quickly to the right place, so it does not check every row.
Interview Connect
Understanding unique index time helps you explain how databases keep searches fast even with lots of data.
Self-Check
What if we removed the unique index and only had a regular index? How would the time complexity change?