How MongoDB stores data as documents - Performance & Efficiency

Time Complexity: How MongoDB stores data as documents

O(n)

Understanding Time Complexity

When we store data in MongoDB, it saves information as documents. Understanding how the time to store or find these documents changes as we add more data helps us use MongoDB well.

We want to know: How does the work grow when we add more documents?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Insert multiple documents into a collection
const docs = [
  { name: "Alice", age: 25 },
  { name: "Bob", age: 30 },
  { name: "Carol", age: 22 }
];

await db.collection('users').insertMany(docs);

// Find all documents where age is greater than 20
const results = await db.collection('users').find({ age: { $gt: 20 } }).toArray();
    

This code adds several documents to a collection and then searches for documents with age over 20.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Scanning documents to find matches.
• How many times: Each document is checked once during the search.

How Execution Grows With Input

As the number of documents grows, the time to check each document grows too.

Input Size (n)	Approx. Operations
10	About 10 document checks
100	About 100 document checks
1000	About 1000 document checks

Pattern observation: The work grows directly with the number of documents. Double the documents, double the checks.

Final Time Complexity

Time Complexity: O(n)

This means the time to find documents grows in a straight line with the number of documents stored.

Common Mistake

[X] Wrong: "Finding documents is always instant no matter how many there are."

[OK] Correct: Without special help like indexes, MongoDB must look at each document one by one, so more documents mean more time.

Interview Connect

Knowing how MongoDB handles documents helps you explain how databases work behind the scenes. This shows you understand how data size affects speed, a key skill in many jobs.

Self-Check

"What if we added an index on the age field? How would the time complexity change when searching by age?"