B+Tree Indexing
From “index makes query faster” to “I can implement and debug one.”
1 / 32
From “index makes query faster” to “I can implement and debug one.”
A table scan asks too much:
look at page
look at next page
look at next page
...
An index should reduce the number of pages touched.
A database B+Tree is not mainly a binary tree.
It is a page-aware tree.
One node means one page-sized chunk of sorted keys.
internal pages: separators + child pointers
leaf pages: actual key/value entries
leaf links: ordered sideways scan
High fanout.
fanout 200
height 2 -> ~200 leaves
height 3 -> ~40,000 leaves
height 4 -> ~8,000,000 leaves
For separators:
[10 | 20 | 40]
Children represent:
<10
10..19
20..39
>=40
Search key 20 routes to the child right of separator 20.
The separator is the lower bound of the right subtree.
choose first separator greater than key
otherwise choose rightmost child
This is upper_bound.
Inside a leaf:
find first key >= target
if equal -> found
else -> missing
This is lower_bound.
[10 | 20]
/ | \
[1,4,7] [10,13] [20,25,30]
Search 13: root -> middle leaf -> found.
Search 20: root -> right leaf -> found.
Query:
lo <= key <= hi
Algorithm:
lo.Next.hi.Without links:
find next key by going back through tree
With links:
move to next leaf page
Order = 3
[1,2,3,4] overflow
left: [1,2]
right: [3,4]
promote: 3
Promoted key stays in the right leaf.
[10,20,30,40] overflow
left: [10,20]
promote: 30
right: [40]
Promoted key moves up and is removed from the child.
split bool
promote int
right *Node
The child reports what happened.
The parent decides where to insert the separator and right child.
When the root splits, height increases.
new root: [promoted]
/ \
left right
Routing equality left.
Symptom: keys equal to separators disappear.
Fix: internal routing uses first separator greater than key.
Leaf split promotes the wrong key.
Correct: first key of the right leaf.
Internal split keeps the promoted key in a child.
Correct: internal promoted key moves up.
Parent inserts right child in the wrong position.
Correct: if child idx split, new right child goes at idx+1.
A few successful lookups do not prove the tree is valid.
Check invariants.
Sorted input lets us build bottom-up:
fill leaves -> link leaves -> build parents -> repeat
pairs: 1 2 3 4 5 6 7 8
leaves: [1,2,3] -> [4,5,6] -> [7,8]
root: [4,7]
Toy model:
int key -> int value
Real model:
composite key -> tuple pointer / primary key / included columns
Index on:
(tenant_id, created_at, id)
Sorted by tenant first.
This explains the left-prefix rule.
If the leaf has all needed columns, the engine may avoid table lookup.
ORDER BYIt can be weak for:
After this module, learners should be able to: