B+tree lookups

A B+tree is a balanced search tree tuned for disks. Every node is one page. Inner pages hold separator keys and child pointers. Only leaf pages hold the actual index entries or rows, and the leaves are linked in order, so range scans are cheap.

The key property is fanout: how many children each inner page has. A large fanout keeps the tree shallow. Shallow means few page reads per lookup, which is what matters when each read may hit disk.

Walking through it: fanout arithmetic

Take a 4 KB page. An 8-byte key plus an 8-byte child pointer makes 16 bytes per entry. Page headers take a little space, so call it about 256 entries. Here is what that gives for the tree height:

fanout 256      → 3 levels hold 256^3   ≈ 16.8 million rows
fanout 256      → 4 levels hold 256^4   ≈ 4.3 billion rows

So a table with 16 million rows needs about 3 page reads to find one key, and the root page usually stays in memory. The lookup itself is a binary search inside each page.

This sketch shows the search at the leaf level. Each leaf holds sorted keys, and separator keys pick the leaf.

import bisect

leaves = [[(1, "a"), (5, "b")], [(7, "c"), (12, "d")], [(20, "e"), (31, "f")]]
separators = [7, 20]          # first key of each leaf after the first

def lookup(k):
    leaf = leaves[bisect.bisect_right(separators, k)]
    keys = [kv[0] for kv in leaf]
    i = bisect.bisect_left(keys, k)
    return leaf[i][1] if i < len(leaf) and leaf[i][0] == k else None

print(lookup(12), lookup(13), lookup(20))

Output:

d None e

Real engines add pages, locking and latching, but the search follows this path.

Page splits

When a leaf is full and a new key arrives, the tree splits the page into two half-full pages and adds a separator key to the parent. If the parent is full, it splits too, and the split can climb to the root. The tree grows taller only at the root, so it stays balanced.

Splits explain a lot about insert speed:

• Sequential keys (an auto-increment ID) always append to the right-most leaf. Old leaves stay full, and the cost is predictable.
• Random keys (UUIDv4) land on any leaf. Almost every leaf is partly full, many splits happen, and the cache that held the hot pages keeps churning.

That is why random UUIDs as clustered primary keys cost more writes and more space. UUIDv7 is time-ordered, so its inserts append like sequential IDs. The trade-offs for IDs are covered in secure randomness and tokens.

Common mistakes

• Using random primary keys on a write-heavy table without measuring the split and cache cost.
• Assuming a deep tree is slow. With fanout in the hundreds, depth 3 or 4 covers almost any table.
• Forgetting that a range scan on a clustered table reads sequential leaves, while a scan through a secondary index can jump randomly between pages.

Check yourself

• Why does a fanout of 256 keep a 16-million-row tree three levels deep? Answer: 256 cubed is about 16.8 million, so three levels of fanout 256 can address that many leaf entries.
• Why do random keys cost more to insert than sequential ones? Answer: they split pages all over the tree, leaving pages half full and churning the cache.

Key takeaways

• A B+tree node is one page, and the fanout keeps the tree shallow.
• A lookup reads one page per level, so a few reads find any row.
• Splits keep the tree balanced, but random keys cause many more of them.
• Sequential or time-ordered keys keep inserts cheap.

Further learning

Next, see how the buffer pool keeps the upper levels of the tree in memory.