STAGE 2 · THE B-TREE

The Branching Frame

One move, split a full page and push the middle key up, is the entire structure.

What you're wiring up

A sorted array searches fast and inserts terribly. A linked list is the mirror image. The B-tree is the thousand-year-old bridge between them: keys stay sorted inside fixed-size pages, and the pages form a very shallow tree, so a lookup among millions of keys is still a handful of page reads.

The whole trick is a single move. When a page fills up, split it in two and push the middle key into the parent. If the parent fills, it splits too, and so on upward. Only a root split makes the tree taller, which is how a B-tree stays balanced without anyone ever rebalancing it.

Inside a page you will use a slotted layout: an array of cell offsets growing from the front, variable-length cells growing from the back, free space in the middle. You keep the offsets sorted, so you sort pointers rather than shuffling key bytes.

# one leaf page, slotted layout
[ hdr | slot0 slot1 slot2 -->   free   <-- cell2 cell1 cell0 ]

# hdr:   type=leaf, nkeys=3, right-sibling (added in stage 3)
# slots: sorted u16 offsets
# cell:  len(key) key len(val) val

Assembly steps

[ 01 ]

Design the node layout: a header carrying node type and key count, then the slotted array of offsets and the length-prefixed cells packed from the back.

hint

Write node.check() now (keys sorted, offsets in bounds, free space sane) and call it after every mutation while BYHDB_PARANOID=1. It catches off-by-ones the tests cannot localize.

[ 02 ]

Implement leaf search and insert without splitting: binary search the slot array, shift slots, append the cell. An existing key overwrites its value.

hint

Get insert three keys out of order, read them back sorted working before you even think about splits.

[ 03 ]

Implement the leaf split: move the upper half of the cells into a fresh page and hand the separator key and new page id back to the caller.

hint

Split at half the byte usage, not half the key count. Variable-length keys make counts lie.

[ 04 ]

Add interior nodes and recursive insert: descend to the right child, and if the child split, insert the separator here, which may split this node too. When the root splits, allocate a new root and record it in the meta page.

hint

Have recursive insert return an optional separator and new page id. Did my child split then propagates cleanly as a return value rather than shared state.

[ 05 ]

Wire set and get in the REPL, plus byhdb tree, which prints depth, node types and key count per node.

hint

byhdb tree is how the harness proves you actually split instead of growing one giant page. Build it honestly.

Go deeper (after it passes)

DDIA's B-trees section is the natural companion now that you have mud on your boots, especially the parts about page size and fanout. If you want the contrast, skim how an LSM tree handles the same insert-heavy workload and ask which one your file format would prefer.