Why indexes are critical for performance in MongoDB - Performance Analysis

Time Complexity: Why indexes are critical for performance

O(n) without index, O(log n) with index

Understanding Time Complexity

When we search data in MongoDB, how fast it happens depends a lot on indexes.

We want to understand how using indexes changes the work MongoDB does as data grows.

Scenario Under Consideration

Analyze the time complexity of the following MongoDB find query with and without an index.

// Find documents where age is 30
// Without index
db.users.find({ age: 30 })

// With index on age
// Assume index created: db.users.createIndex({ age: 1 })

This code searches for users aged 30, first scanning all documents, then using an index.

Identify Repeating Operations

Look at what repeats as data grows.

• Primary operation: Scanning documents or index entries one by one.
• How many times: Without index, it checks every document; with index, it checks fewer index entries.

How Execution Grows With Input

As the number of users grows, the work changes like this:

Input Size (n)	Approx. Operations Without Index	Approx. Operations With Index
10	10 document checks	About 4 index checks
100	100 document checks	About 7 index checks
1000	1000 document checks	About 10 index checks

Pattern observation: Without index, work grows directly with data size; with index, work grows slowly, like steps up a tree.

Final Time Complexity

Time Complexity: O(n) without index, O(log n) with index

This means searching without an index gets slower directly with more data, but with an index, it grows much slower.

Common Mistake

[X] Wrong: "Adding an index always makes queries instantly fast no matter what."

[OK] Correct: Indexes help most for searches on indexed fields, but if the query is on other fields or returns many results, the speed gain may be less.

Interview Connect

Understanding how indexes change search speed shows you know how databases handle data efficiently, a key skill for real projects.

Self-Check

"What if we added a compound index on age and city? How would that affect the time complexity for queries filtering by both fields?"