Time Complexity: Why advanced indexing matters
O(log n + k)
0
0
Why advanced indexing matters in MongoDB - Performance Analysis
Understanding Time Complexity
When we use advanced indexing in MongoDB, it changes how fast queries run as data grows.
We want to see how indexing affects the work the database does when searching.
Scenario Under Consideration
Analyze the time complexity of this MongoDB query using an index.
db.products.createIndex({ category: 1, price: -1 });
const results = db.products.find({ category: "books", price: { $lt: 20 } });
This code creates an index on category and price fields, then finds products in "books" category priced below 20.
Identify Repeating Operations
Look at what repeats when the query runs.
- Primary operation: Scanning the index entries matching the category and price condition.
- How many times: Once per matching index entry, not all documents.
How Execution Grows With Input
As the number of products grows, the query looks only at relevant index parts.
| Input Size (n) | Approx. Operations |
|---|---|
| 10 | About 3-5 index checks |
| 100 | About 10-15 index checks |
| 1000 | About 20-30 index checks |
Pattern observation: The work grows slowly because the index narrows the search quickly.
Final Time Complexity
Time Complexity: O(log n + k)
This means the query gets slower only a little as data grows, thanks to the index.
Common Mistake
[X] Wrong: "Adding an index makes queries instantly fast no matter what."
[OK] Correct: Some queries don't use indexes well, and indexes add small overhead when writing data.
Interview Connect
Understanding how indexes affect query speed shows you know how databases handle big data efficiently.
Self-Check
"What if we removed the index on price and only indexed category? How would the time complexity change?"