Time Complexity: Soft delete pattern in MongoDB
O(n)
0
0
Soft delete pattern in MongoDB - Time & Space Complexity
Understanding Time Complexity
We want to understand how the time to find active records changes as the database grows when using the soft delete pattern.
Specifically, how does filtering out deleted items affect query speed?
Scenario Under Consideration
Analyze the time complexity of the following MongoDB query using soft delete.
// Find all active users (not deleted)
db.users.find({ deleted: { $ne: true } })
This query fetches all users who are not marked as deleted by checking the 'deleted' field.
Identify Repeating Operations
Look for repeated work done by the database to answer the query.
- Primary operation: Scanning user records to check the 'deleted' field.
- How many times: Once for each user document in the collection.
How Execution Grows With Input
As the number of users grows, the database must check more documents to find active ones.
| Input Size (n) | Approx. Operations |
|---|---|
| 10 | 10 checks |
| 100 | 100 checks |
| 1000 | 1000 checks |
Pattern observation: The number of checks grows directly with the number of users.
Final Time Complexity
Time Complexity: O(n)
This means the time to find active users grows linearly with the total number of users.
Common Mistake
[X] Wrong: "Adding a 'deleted' flag means queries will always be fast regardless of data size."
[OK] Correct: Without an index on the 'deleted' field, MongoDB must check every document, so query time grows with data size.
Interview Connect
Understanding how soft delete affects query time shows you grasp practical database design and performance trade-offs.
Self-Check
"What if we add an index on the 'deleted' field? How would the time complexity change?"