Time Complexity: Unique index behavior
O(log n)
0
0
Unique index behavior in MongoDB - Time & Space Complexity
Understanding Time Complexity
When using a unique index in MongoDB, it is important to understand how the time to check for duplicates grows as the data grows.
We want to know how the cost of enforcing uniqueness changes when more documents exist.
Scenario Under Consideration
Analyze the time complexity of inserting a document with a unique index on a field.
// Create a unique index on the "email" field
db.users.createIndex({ email: 1 }, { unique: true })
// Insert a new user document
db.users.insertOne({ name: "Alice", email: "alice@example.com" })
This code creates a unique index on the email field and inserts a new user, which requires checking the index for duplicates.
Identify Repeating Operations
When inserting, MongoDB must check the unique index to ensure no duplicate email exists.
- Primary operation: Searching the unique index for the email value.
- How many times: Once per insert operation.
How Execution Grows With Input
The unique index is a balanced tree structure, so searching it grows slowly as data grows.
| Input Size (n) | Approx. Operations |
|---|---|
| 10 | About 4 steps |
| 100 | About 7 steps |
| 1000 | About 10 steps |
Pattern observation: The number of steps grows slowly, adding only a few more checks as data grows.
Final Time Complexity
Time Complexity: O(log n)
This means checking for duplicates takes a little more time as the collection grows, but it grows slowly and efficiently.
Common Mistake
[X] Wrong: "Checking for duplicates with a unique index takes the same time no matter how many documents exist."
[OK] Correct: The unique index uses a tree structure, so the time to check grows slowly with more data, not instantly constant.
Interview Connect
Understanding how unique indexes work helps you explain database efficiency and data integrity in real projects.
Self-Check
"What if the unique index was on multiple fields instead of one? How would the time complexity change?"