# B-Tree

## 1. Why "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.

## 2. Shape: 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.

![A B-tree has a root, internal nodes and linked sorted leaves; each node is a page with many keys, so the tree is shallow and range scans walk the leaf chain](diagrams/01-btree-shape.svg)

## 3. Lookup: Descend, Don't Backtrack

```sql
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)**.

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

```sql
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.

## 5. Insert 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.

## 6. Under the Hood: Why Balance Matters More On Disk Than In Memory

A binary search tree can, in the worst case (inserting already-sorted data with no rebalancing), degrade into a linked list — O(n) lookups instead of O(log n). For an in-memory structure this is bad but survivable; for a disk-backed index it's catastrophic, because every extra level of tree height is a full random I/O read on a device that (even for SSDs, and especially for spinning disks) is orders of magnitude slower than an in-memory pointer dereference. A B-tree's self-balancing guarantee — every leaf is at the same depth, always — is precisely the property that bounds the *worst-case* number of disk reads per lookup, which is why database engines refuse to use a structure that could silently degrade under adversarial or just unlucky insert patterns.

## 7. 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.

## 8. 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
```