Time Complexity: Multikey indexes for arrays
O(n)
0
0
Multikey indexes for arrays in MongoDB - Time & Space Complexity
Understanding Time Complexity
When MongoDB uses multikey indexes on arrays, it creates index entries for each element in the array. Understanding how this affects query time is important.
We want to know how the number of array elements changes the work MongoDB does when searching.
Scenario Under Consideration
Analyze the time complexity of querying a collection with a multikey index on an array field.
db.products.createIndex({ tags: 1 })
db.products.find({ tags: "organic" })
This code creates a multikey index on the 'tags' array field and then queries for documents containing the tag "organic".
Identify Repeating Operations
Look at what repeats when MongoDB uses a multikey index.
- Primary operation: Index entries are created for each element in every array in the collection.
- How many times: For each document, once per array element in the indexed field.
How Execution Grows With Input
As the number of array elements grows, the index size and search work grow too.
| Input Size (n) | Approx. Operations |
|---|---|
| 10 elements per array | About 10 index entries checked |
| 100 elements per array | About 100 index entries checked |
| 1000 elements per array | About 1000 index entries checked |
Pattern observation: The work grows roughly in direct proportion to the number of array elements.
Final Time Complexity
Time Complexity: O(n)
This means the query time grows linearly with the number of elements in the array field being indexed.
Common Mistake
[X] Wrong: "Multikey indexes make queries run in constant time regardless of array size."
[OK] Correct: Each array element creates an index entry, so more elements mean more entries to check, increasing query time.
Interview Connect
Knowing how multikey indexes scale helps you explain database performance clearly and shows you understand how data structure affects query speed.
Self-Check
"What if the array field contained nested arrays? How would that affect the time complexity of queries using multikey indexes?"