Chapter 14: B-Tree Internals — The Data Structure Behind Indexes

The B-Tree (and its variant B+Tree) is the most important data structure in databases. Understanding it explains why indexes are fast, why column order in composite indexes matters, and why some queries can't use indexes.

Why B-Trees? (Not Binary Trees)

A binary search tree has 2 children per node. For 1 million keys, that's ~20 levels deep = 20 disk reads per lookup. Too slow.

A B-Tree has hundreds of children per node (because each node = one disk page = 8KB, fitting many keys). For 1 million keys with a branching factor of 500, that's only 3 levels deep = 3 disk reads.

B+Tree Structure (What Databases Actually Use)

Databases use B+Trees (a variant where all data is in leaf nodes):

Operations

Lookup: O(log n)

// Find key=42:
// 1. Root: 42 > 30, 42 < 60 → go to second child
// 2. Internal: find leaf containing 42
// 3. Leaf: binary search within leaf → found at position 3
// 4. Follow row pointer → read actual row from heap
// Total: 3-4 page reads

Range Scan: O(log n + k)

// Find all keys between 35 and 78:
// 1. B-tree lookup to find leaf containing 35 (3 reads)
// 2. Follow leaf links → → → until key > 78
// 3. Collect all row pointers along the way
// This is why leaf nodes are linked!

Insert: O(log n)

// Insert key=40:
// 1. Find correct leaf (same as lookup)
// 2. Insert into leaf (maintaining sorted order)
// 3. If leaf is full → SPLIT into two leaves
//    → promote middle key to parent
//    → if parent full, split recursively up

Composite Index Column Order

A composite index on (country, city, name) sorts like a phone book: first by country, then by city within each country, then by name within each city.

Index Types Beyond B-Tree

Clustered vs Non-Clustered