How MongoDB indexes work (B-tree mental model) - Visual Walkthrough

Concept Flow - How MongoDB indexes work (B-tree mental model)

Start: Query for value

↓

Check root node keys

↓

Compare query value with keys

↓

Go to child node based on range

↓

Repeat check keys in child node

↓

Reach leaf node with pointers to documents

↓

Return matching documents

↓

End

The query starts at the root node of the B-tree, compares the value with keys to decide which child node to follow, repeats this until reaching a leaf node that points to matching documents.

Execution Sample

MongoDB

db.collection.find({age: 30}).explain('executionStats')

This query searches for documents where the age is 30 using an index on the age field.

Execution Table

Step	Node Type	Keys in Node	Query Value Compared	Decision	Next Action
1	Root	[20, 40, 60]	30	30 > 20 and < 40	Go to child node between 20 and 40
2	Child	[25, 35]	30	30 > 25 and < 35	Go to child node between 25 and 35
3	Leaf	[28, 30, 33]	30	Found 30	Return pointers to documents with age=30
4	End	N/A	N/A	Query complete	Return results to user

💡 Reached leaf node containing the key 30, so query returns matching documents.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	Final
Current Node	Root	Child between 20 and 40	Child between 25 and 35	Leaf with keys [28,30,33]	Leaf node reached
Query Value	30	30	30	30	30
Decision	N/A	Go to child node between 20 and 40	Go to child node between 25 and 35	Found 30	Return documents

Key Moments - 2 Insights

Why does the search start at the root node and not directly at the leaf?

The root node contains keys that help decide which child node to follow. This step-by-step narrowing down is how the B-tree efficiently finds the correct leaf node, as shown in steps 1 and 2 of the execution_table.

What happens if the query value is not found exactly in the keys?

The search still follows the child node whose key range would contain the value if it existed. Eventually, it reaches a leaf node where no exact match is found, and the query returns no results. This is implied by the decision steps in the execution_table.

Visual Quiz - 3 Questions

Look at the execution_table, at Step 2, which keys are in the child node?

A [25, 35]

B [20, 40, 60]

C [28, 30, 33]

D [30, 40, 50]

💡 Hint

Check the 'Keys in Node' column at Step 2 in the execution_table.

At which step does the query find the exact key matching the query value?

A Step 1

B Step 3

C Step 2

D Step 4

💡 Hint

Look at the 'Decision' column where it says 'Found 30'.

If the query value was 50 instead of 30, which child node would the root node direct the search to?

A Child node between 20 and 40

B Child node between 60 and above

C Child node between 40 and 60

D Leaf node directly

💡 Hint

Refer to Step 1's decision logic comparing query value with root keys.

Concept Snapshot

MongoDB indexes use a B-tree structure.
Queries start at the root node.
Keys in nodes guide which child node to follow.
Search continues down until leaf nodes.
Leaf nodes point to matching documents.
This makes searches fast and efficient.

Full Transcript

When MongoDB uses an index, it organizes keys in a B-tree structure. The search begins at the root node, which contains keys dividing the data ranges. The query value is compared with these keys to decide which child node to visit next. This process repeats, moving down the tree nodes, narrowing the search range. Eventually, the search reaches a leaf node that contains pointers to the actual documents matching the query. If the key is found, those documents are returned. If not, the query returns no results. This step-by-step traversal makes searching large datasets fast and efficient.