Single field index in MongoDB - Time & Space Complexity

Time Complexity: Single field index

O(log n)

Understanding Time Complexity

When we use a single field index in MongoDB, it helps the database find data faster. We want to understand how the time to find data changes as the data grows.

How does using this index affect the speed of searching?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

db.users.createIndex({ age: 1 });

const result = db.users.find({ age: 30 });

This code creates an index on the "age" field and then searches for users who are 30 years old.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The database uses the index to quickly locate matching entries without scanning all documents.
• How many times: The search moves through the index entries, which grow as more documents are added.

How Execution Grows With Input

As the number of documents grows, the index helps keep the search fast by not checking every document.

Input Size (n)	Approx. Operations
10	About 3-4 steps through the index
100	About 7 steps through the index
1000	About 10 steps through the index

Pattern observation: The number of steps grows slowly, much less than the total number of documents.

Final Time Complexity

Time Complexity: O(log n)

This means the search time grows slowly as the data grows, making queries efficient even with lots of data.

Common Mistake

[X] Wrong: "Using an index makes the search time constant no matter how big the data is."

[OK] Correct: The search still takes more steps as data grows, but thanks to the index, it grows slowly, not instantly.

Interview Connect

Understanding how indexes speed up searches helps you explain how databases stay fast with lots of data. This skill shows you know how to make queries efficient.

Self-Check

"What if we searched without creating an index? How would the time complexity change?"