B+ trees explained: how your database finds a row in 3 reads

Thirty million rows. One indexed column. A WHERE clause hits that column and Postgres finds your row by reading three 8 KB pages off disk. Three. Not three thousand, not thirty. Three.

How does a tree that holds 30 million keys stay only three levels tall? That's the question this post answers.

🎯 Why not a binary tree?

If you took algorithms in school, your brain probably jumps to a balanced binary search tree. AVL tree, red-black tree, something like that. And the math works fine in memory: log₂(30,000,000) ≈ 25 comparisons to find any key. Fast.

But databases don't live in memory. They live on disk. And disk I/O reads a fixed-size page (8 KB in Postgres, 16 KB in MySQL/InnoDB). One page read, one round trip. A binary tree node holds exactly one key, so you burn one full page read for every single level you descend. Twenty-five levels means twenty-five page reads. That's brutal.

The fix is obvious once you see it: cram hundreds of keys into each node. If your node fits inside one page and holds 400 keys instead of 1, you only need log₄₀₀(30,000,000) ≈ 3 levels. Same data, same answer, twenty-two fewer disk reads.

That's a B+ tree. A wide, shallow tree where every node fills a disk page.

🔑 What makes it a B+ tree (not a B-tree)

Quick naming confession. Postgres docs say "B-tree." MySQL docs say "B-tree." Every DBA you've ever met says "B-tree." But the actual structure both databases implement is a B+ tree. The classic B-tree stores data pointers at every level. A B+ tree keeps all data pointers in the leaves and stores only separator keys in internal nodes. Both Postgres (Lehman-Yao variant) and InnoDB ("all index records are stored in the leaf pages," Oracle docs verbatim) are structurally B+ trees.

Nobody corrects this in conversation because it doesn't matter for day-to-day work. But it matters for understanding the design. Internal nodes being routing-only is exactly what gives you that massive fanout.

Node anatomy

An internal node in a Postgres nbtree index on a BIGINT column looks roughly like this:

8 KB page
Each slot: ~8-byte key + 6-byte child pointer + overhead ≈ 20 bytes
Usable space: ~8000 bytes
Keys per page: ~400

So fanout is about 400. Leaf pages hold the same keys but paired with 6-byte TIDs (tuple identifiers pointing to the actual heap row). And here's the thing that makes everything else work: leaf pages are linked together as a doubly-linked list.

Worked height calculation

Height	Max rows indexed
1 (root only)	~400
2	400² = 160,000
3	400³ = 64,000,000
4	400⁴ ≈ 25,600,000,000

Three levels for tens of millions of rows. Four levels for billions. And the root page is always cached in shared buffers, so in practice you're looking at one or two actual disk reads for a point lookup on a table with millions of rows. Wild.

🛠️ How the tree grows and splits

Inserts are straightforward until a page fills up. You descend from root to the correct leaf, slot the new key in sorted order, done. But when the leaf is full, things get interesting.

Page splits

BEFORE (leaf page full, inserting key 25):
┌──────────────────────────────────┐
│  [10, 15, 20, 30, 35, 40]       │  ← full leaf
└──────────────────────────────────┘

AFTER (split at midpoint, promote 30 to parent):
┌──────────────────┐     ┌─────────────────┐
│  [10, 15, 20, 25]│  →  │  [30, 35, 40]   │   ← two leaves, linked
└──────────────────┘     └─────────────────┘
         parent gets: [..., 30 → new_page_ptr, ...]

The split moves roughly half the items (by bytes, not count) to a new right-sibling page. The lowest key of the new page gets promoted up as a separator in the parent. If the parent is also full, it splits recursively. If the root splits, a brand-new root is created with two children, and the tree grows taller by exactly one level. Always at the top.

What about deletes?

Textbook B+ trees merge half-empty siblings to rebalance. Postgres doesn't do this. Deleted entries get marked LP_DEAD by index scans, then physically cleaned up by VACUUM. Completely empty pages are eventually unlinked, but partly-full pages are never merged. Postgres 14 added bottom-up deletion to proactively clear version-churn duplicates before they cause a split, but that's still not a merge.

Fill factor

Postgres defaults to a 90% fill factor for btree leaf pages. That 10% headroom means sequential inserts won't immediately trigger splits. But if your key is random (think UUIDv4) inserts scatter across all leaves. Half the pages end up splitting at ~50% capacity. Fragmentation everywhere.

Why linked leaves are the real trick

The tree structure gets you to the first matching key in 2–3 reads. Great for point lookups. But WHERE price BETWEEN 10 AND 50? Or ORDER BY created_at DESC?

            [  17  |  35  ]              ← root
           /       |       \
    [5|12|17]   [21|28|35]   [40|48]     ← internal
     / | | \     / | | \      / | \
   [3,5]→[7,12]→[17,19]→[21,28]→[35,38]→[40,48,52]
                                          ← leaves linked →

Once you land on the first leaf that matches, you just follow the forward pointer. Sequential page reads, no re-traversal of internal nodes. The kernel's read-ahead kicks in because you're reading physically adjacent pages. And because the leaf order is sorted key order, an ORDER BY on the indexed column is free. Postgres streams results directly from the leaf chain without a separate sort step.

This is why a btree index can accelerate range queries, not just equality lookups. One sentence on a related topic: composite index column ordering matters for which ranges you can serve this way, but that's a separate post.

UUIDs: the key shape that fights the tree

Sequential keys (BIGSERIAL, timestamps) are B+ tree friendly. Every insert goes to the rightmost leaf page. Only that page ever splits. Postgres even has a fast path that caches the rightmost leaf per backend to skip the tree descent entirely.

Random keys (UUIDv4 is the poster child) break this completely. Inserts hit random leaf pages scattered across the index. Pages split at low utilization. The working set of pages you need in cache explodes. Write amplification goes up. Your index bloats.

UUIDv7 and ULID fix this by embedding a timestamp prefix. The value increases monotonically over time, so inserts append to the right edge just like BIGSERIAL. You keep the global uniqueness of a UUID without punishing the B+ tree. If you need a UUID primary key, use v7.

Fragmentation from random keys is real enough that the Postgres ecosystem has REINDEX (rebuilds from scratch, requires exclusive lock) and REINDEX CONCURRENTLY (PG 12+, no blocking). But prevention beats the cure — pick a key shape that appends.

Similar to how git stores objects as content-addressed hashes and accepts the random-distribution trade-off because it doesn't need range scans, UUIDv4 is fine when your access pattern is purely point lookups. But a primary key usually isn't.

📌 Key takeaways

A B+ tree index on a bigint column in Postgres is ~3 levels tall for tens of millions of rows. Fanout of ~400 per page makes the difference between 23 reads (binary tree) and 3.
Internal nodes hold only separator keys. All record pointers live in the linked leaf pages. That's what makes it a B+ tree, and why both range scans and ORDER BY are cheap.
Page splits happen when a leaf fills up. The split promotes a key to the parent. The tree only grows taller at the root. Postgres doesn't merge pages on delete; it lets VACUUM reclaim space.
Random primary keys (UUIDv4) scatter inserts and cause fragmentation. Sequential keys, UUIDv7, or ULID keep inserts appending to the right edge. Pick accordingly.

If index-only scans and covering indexes interest you, I'll cover those in an upcoming post.