How an index works (B-tree mental model) in SQL - Visual Walkthrough

Concept Flow - How an index works (B-tree mental model)

Start: Search for value

↓

Check root node keys

↓

Go to child node

↓

Repeat check keys in node

↓

Reach leaf node

↓

Find value or conclude not found

↓

End

The B-tree index starts at the root, compares keys to decide which child node to follow, repeats this until reaching a leaf node where the value is found or not.

Execution Sample

SQL

SELECT * FROM users WHERE id = 42;

This query uses the B-tree index on 'id' to quickly find the row with id 42.

Execution Table

Step	Node Level	Keys in Node	Compare with 42	Decision	Next Node
1	Root	[10, 30, 50]	42 > 30 and < 50	Go to child between 30 and 50	Child Node 2
2	Child Node 2	[35, 40, 45]	42 > 40 and < 45	Go to child between 40 and 45	Child Node 5
3	Child Node 5 (Leaf)	[41, 42, 43]	Found 42	Return row with id=42	End

💡 Value 42 found at leaf node, search ends.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3
Current Node	Root	Child Node 2	Child Node 5	Leaf Node with value 42
Keys Compared	None	[10, 30, 50]	[35, 40, 45]	[41, 42, 43]
Decision	None	Go to child between 30 and 50	Go to child between 40 and 45	Found 42

Key Moments - 2 Insights

Why do we compare the search value with keys in the node instead of scanning all data?

Because the B-tree index stores keys in sorted order in nodes, comparing keys lets us quickly decide which child node to follow, avoiding scanning all data. See execution_table steps 1 and 2.

What happens if the value is not found in the leaf node?

If the value is not in the leaf node keys, the search concludes the value does not exist in the table. The search stops at the leaf node after comparisons, as shown in execution_table step 3.

Visual Quiz - 3 Questions

Look at the execution_table, at Step 2, which keys are compared to decide the next node?

A [10, 30, 50]

B [35, 40, 45]

C [41, 42, 43]

D [30, 50, 70]

💡 Hint

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

At which step does the search find the value 42?

A Step 3

B Step 2

C Step 1

D Search never finds 42

💡 Hint

Look at the 'Compare with 42' and 'Decision' columns in execution_table.

If the root node keys changed to [20, 40, 60], which child node would the search follow for value 42?

A Child between 20 and 40

B Child less than 20

C Child between 40 and 60

D Child greater than 60

💡 Hint

Compare value 42 to the root keys and decide which range it falls into.

Concept Snapshot

B-tree index stores keys in sorted nodes.
Search starts at root node.
Compare search value with node keys.
Follow child pointer based on comparison.
Repeat until leaf node.
Find value or conclude not found.

Full Transcript

A B-tree index helps find data quickly by organizing keys in a tree structure. The search starts at the root node, compares the search value with keys in that node, and decides which child node to follow. This process repeats down the tree until reaching a leaf node. At the leaf, the value is either found or determined to be missing. This avoids scanning all data by narrowing down the search path step-by-step.