How MongoDB indexes work (B-tree mental model) - Performance & Efficiency

Time Complexity: How MongoDB indexes work (B-tree mental model)

O(log n)

Understanding Time Complexity

When we use indexes in MongoDB, we want to find data faster. Understanding how indexes work helps us see why some searches are quick and others are slow.

We ask: How does the time to find data grow as the database gets bigger?

Scenario Under Consideration

Analyze the time complexity of searching a MongoDB collection using a B-tree index.

// Find a document by indexed field
db.collection.find({ indexedField: value })

// The index is a B-tree structure
// It helps MongoDB quickly locate the value
    

This code uses an index to find documents by a specific field value efficiently.

Identify Repeating Operations

Look at what repeats when searching the B-tree index:

• Primary operation: Checking nodes in the B-tree to find the right branch.
• How many times: The number of nodes checked grows slowly as the tree grows taller, not as the number of documents.

How Execution Grows With Input

As the collection grows, the B-tree grows in height slowly. Searching means moving down the tree levels.

Input Size (n)	Approx. Operations (nodes checked)
10	2-3
100	3-4
1000	4-5

Pattern observation: The number of steps grows very slowly, much slower than the number of documents.

Final Time Complexity

Time Complexity: O(log n)

This means finding a document using an index takes a small number of steps even if the database is very large.

Common Mistake

[X] Wrong: "Searching with an index checks every document one by one."

[OK] Correct: The index uses a tree structure to jump quickly to the right place, so it does not look at every document.

Interview Connect

Knowing how indexes speed up searches shows you understand how databases handle big data efficiently. This skill helps you explain and improve data queries in real projects.

Self-Check

"What if the index was a simple list instead of a B-tree? How would the time complexity change?"

Practice

1. What is the main purpose of an index in MongoDB using a B-tree structure?

easy

A. To encrypt data for security

B. To store data in a compressed format

C. To speed up search and sort operations on data

D. To backup the database automatically

Solution

1. Step 1: Understand what a B-tree index does

   A B-tree index organizes data so that searching and sorting can happen quickly.

2. Step 2: Identify the main benefit of indexing

   Indexes help queries find data faster by avoiding full collection scans.

3. Final Answer:

   To speed up search and sort operations on data -> Option C

4. Quick Check:

   Index = Faster search and sort [OK]

Hint: Indexes speed up queries by organizing data [OK]

Common Mistakes:

• Thinking indexes compress data
• Confusing indexes with backups
• Assuming indexes encrypt data

2. Which of the following is the correct syntax to create an ascending index on the field age in MongoDB?

easy

A. db.collection.createIndex({age: 1})

B. db.collection.createIndex(age: ascending)

C. db.collection.index({age: 'asc'})

D. db.collection.addIndex({age: 1})

Solution

1. Step 1: Recall MongoDB index creation syntax

   The correct method is createIndex with a document specifying field and order.

2. Step 2: Check the correct format for ascending order

   Ascending order is represented by 1, so {age: 1} is correct.

3. Final Answer:

   db.collection.createIndex({age: 1}) -> Option A

4. Quick Check:

   createIndex + {field: 1} = correct syntax [OK]

Hint: Use createIndex({field: 1}) for ascending index [OK]

Common Mistakes:

• Using addIndex instead of createIndex
• Passing string 'asc' instead of 1
• Omitting curly braces around field

3. Given a collection with an index on score, what will be the order of documents returned by this query?
db.collection.find().sort({score: 1})

medium

A. Documents sorted by score in descending order

B. Documents sorted by insertion order

C. Documents in random order

D. Documents sorted by score in ascending order

Solution

1. Step 1: Understand the sort parameter

   The sort({score: 1}) means sort by score ascending (lowest to highest).

2. Step 2: Recognize index usage

   Since there is an index on score, MongoDB uses it to return documents in ascending order efficiently.

3. Final Answer:

   Documents sorted by score in ascending order -> Option D

4. Quick Check:

   sort({score: 1}) = ascending order [OK]

Hint: sort({field: 1}) means ascending order [OK]

Common Mistakes:

• Confusing 1 with descending order
• Assuming no order without explicit index
• Thinking insertion order is default

4. You created a unique index on the field email but still see duplicate emails in your collection. What is the likely cause?

medium

A. The index was created with ascending order instead of unique

B. The unique index was created after duplicates existed

C. MongoDB does not enforce uniqueness on indexes

D. The field email is missing in some documents

Solution

1. Step 1: Understand unique index behavior

   Unique indexes prevent duplicates only for new inserts after index creation.

2. Step 2: Consider existing duplicates

   If duplicates existed before creating the unique index, MongoDB allows them unless you drop or clean data first.

3. Final Answer:

   The unique index was created after duplicates existed -> Option B

4. Quick Check:

   Unique index blocks new duplicates, not old ones [OK]

Hint: Unique index blocks new duplicates, not existing ones [OK]

Common Mistakes:

• Thinking ascending order affects uniqueness
• Believing MongoDB ignores unique constraints
• Assuming missing fields cause duplicates

5. You want to optimize queries filtering by category and sorting by price. Which index is best to improve performance?

hard

A. A compound index on {category: 1, price: 1}

B. Two separate indexes: one on category, one on price

C. A unique index on price

D. No index needed if collection is small

Solution

1. Step 1: Understand compound index benefits

   A compound index on {category: 1, price: 1} supports queries filtering by category and sorting by price efficiently.

2. Step 2: Compare with separate indexes

   Separate indexes cannot optimize combined filter and sort as well as a compound index.

3. Step 3: Consider uniqueness and collection size

   Unique index on price is irrelevant here; small collections may not need indexes but that is not optimization.

4. Final Answer:

   A compound index on {category: 1, price: 1} -> Option A

5. Quick Check:

   Compound index = best for filter + sort [OK]

Hint: Use compound index for filter and sort fields together [OK]

Common Mistakes:

• Using separate indexes instead of compound
• Confusing unique index with performance index
• Ignoring index for small collections