B+ tree
A B+ tree is a variant of the B-tree where all satellite data (or all keys in their final sorted order) live in the leaves. Internal nodes carry only separator keys to guide search—like a directory. Leaves are usually linked as a sorted linked list, making range scans and sequential I/O efficient.
- Internal nodes vs leaf level
- Why databases favor B+ for indexes
- Contrast with classic B-tree
Read B-tree first for multi-way nodes and disk motivation. Balanced in-memory BSTs (AVL, red-black) differ: they target pointer-heavy RAM structures, not block I/O.
1) Structure
- Root may be a leaf (small tree) or an internal index node.
- Internal nodes: copies of keys (or routing keys) with child pointers; no user records stored here in the strictest textbook form.
- Leaves: contain keys in order; often store row IDs or heap locations; sibling pointers support
WHERE key BETWEEN …style scans.
2) Search and ranges
Point lookup: walk from root using comparisons until a leaf; confirm the key there.
Range query: find the start key’s leaf, then walk forward along leaf links—no backtracking through internal nodes.
3) Why SQL engines use B+ trees
| Aspect | Benefit |
|---|---|
| Leaf linked list | Efficient sorted iteration and range filters |
| Higher fan-out in internal nodes | Shallower tree (more keys per node when values live only in leaves) |
| Predictable depth | Stable query latency for large tables |
4) B+ vs B-tree (summary)
Classic B-trees may store values at internal nodes; B+ trees push all search keys to leaves and duplicate routing keys above. That duplication is a small storage cost compared to simpler range queries and higher branching in practice.
Key takeaway
The B+ tree is the default mental model for relational index structures: internal layers are a search map; the truth for ordering and scans lives in the leaf level.
See also: B-tree · Binary search tree · Tree tutorial (hub)