B-Tree

1Why "B-tree" and Not Just "a Tree"

01-database_indexes/ established that most indexes are B-trees by default. This topic is about why — what specifically about a B-tree makes it the right default structure for a relational database index, as opposed to a plain binary search tree or a hash table.

A B-tree (short for "balanced tree," not "binary tree" — this is a common misconception) is a self-balancing, multi-way tree: unlike a binary tree where each node has at most 2 children, a B-tree node can hold many keys and many children, and the tree rebalances itself on insert/delete to stay flat and evenly filled.

2Shape: Wide and Shallow, Not Tall and Thin

                [ 50 | 100 | 150 ]                    <- root
               /      |      |      \
        [10|30]   [60|80]  [110|130]  [160|180]        <- internal nodes
        /  |  \    /  |  \    ...        ...
     ... (leaf nodes hold the actual indexed values, sorted) ...

A binary search tree with a million entries can be roughly 20 levels deep. A B-tree with the same million entries, because each node holds dozens or hundreds of keys (sized to match a disk page, typically 4-8 KB), might only be 3-4 levels deep. Every level of tree traversal is a separate disk/page read in the worst case, so a shallower tree directly means fewer I/O operations per lookup — this is the entire reason B-trees, not binary trees, became the standard for on-disk index structures.

3Lookup: Descend, Don't Backtrack

SELECT * FROM employees WHERE id = 73;

A B-tree lookup starts at the root, compares the target value against the keys in that node, picks the single child pointer whose range contains the target, and descends — repeating until it reaches a leaf node holding the actual value (or a pointer to the row). Each step eliminates a whole subtree from consideration, giving lookup time proportional to the tree's height: O(log n).

4Range Queries: Why B-trees, Not Hash Indexes, Handle </>/BETWEEN

SELECT * FROM employees WHERE hired_at BETWEEN '2023-01-01' AND '2023-06-30';
SELECT * FROM employees ORDER BY salary DESC LIMIT 10;

The leaf nodes of a B-tree are linked together in sorted order — once you've descended to the correct starting leaf, you can walk sideways across leaf nodes to collect a contiguous range without ever going back up the tree. A hash index has no such thing: it maps a key to a bucket via a hash function, and hash functions scramble ordering by design, so "give me everything between X and Y" has no efficient answer in a hash index — it would require scanning nearly everything. This is the single biggest reason B-tree beats hash index as the default: B-tree supports both exact-match and range/order queries; hash index supports only exact-match.

5Insert and Delete: Splits and Merges Keep the Tree Balanced

Node at capacity: [10 | 20 | 30]   (max 3 keys in this toy example)

Insert 25 -> node overflows -> SPLIT:

        [20]
       /    \
   [10]    [25|30]

When a node exceeds its capacity on insert, it splits in two, and the split propagates upward — potentially all the way to the root, which is the one case where the tree's height grows by one level (uniformly across the whole tree, which is what keeps it balanced rather than lopsided like an unbalanced BST can become). Deletes work in reverse: when a node drops below a minimum occupancy, it merges with a sibling or borrows a key from one, again propagating upward if needed. Both operations are what "self-balancing" means in practice — the tree's shape is actively maintained on every write, not just built once and left to degrade.

⚠️ Common Pitfalls

1. Assuming "B-tree" means "binary tree" — it doesn't; the whole performance story depends on nodes holding many keys, not two.
2. Expecting a B-tree index to help a hash-equality-only workload beat a hash index — for pure point lookups with no range queries ever, a hash index can be marginally faster; B-tree wins because it also handles ranges, not because it's unconditionally faster at everything.
3. Forgetting that inserts in already-sorted key order still cause splits — self-balancing prevents degeneration, but a monotonically increasing key (like an auto-incrementing ID) still causes a predictable pattern of right-edge splits; this is normal, not a sign of a broken index.
4. Thinking index depth is fixed regardless of table size — it grows (slowly, logarithmically) as the table grows; a B-tree over a 10-row table and one over a 10-billion-row table are the same kind of structure, at very different heights.

📋 Quick Reference

B-tree = "balanced tree" (not "binary tree") — wide nodes, shallow height
Height ~ log_b(n), b = node fanout (often 100s) -> few disk reads even for huge tables
Leaf nodes linked in sorted order -> supports range queries (<, >, BETWEEN, ORDER BY)
Hash index -> O(1) exact match only, NO range query support (unordered by design)
Insert/delete -> node split / merge, propagates upward, keeps every leaf at the same depth
Self-balancing = bounds WORST-CASE lookup depth, which is what matters for disk I/O

🎤 Interview Q&A

🛠️ Practice exercises

Each exercise is a file in this topic folder. Code exercises are self-checking: run them and make the checks pass.

✅ Check yourself

Source: dbidx_b_tree_theory.md · generated by tools/build_lessons.py