builds / database / stage-3SHEET 3 / 6 · REV ASIGN IN
ASSEMBLY DIAGRAM — YOUR DATABASESCALE: LEARNING
querythe outside worldPAGE DECK✓ builtB-TREE✓ builtLEAF WALKWAY⚙ buildingWAL TAPEstage 4CARD CATALOGstage 5SQL DECKstage 6
BUILTUNDER CONSTRUCTIONNOT YET IMAGINED INTO EXISTENCE
STAGE 3 · THE LEAF WALKWAY

The Walkway

Stitch the leaves together and a point lookup becomes a range scan.

What you're wiring up

Real queries are rarely give me exactly key X. They are everything between A and B, or the last fifty orders. A B-tree becomes a B+-tree when its leaves are chained with sibling pointers: seek once to the start of a range, then walk right and never climb the tree again.

The cursor makes that walk explicit: seek, next, valid. It is the abstraction every layer above will use. Stage 5's typed range scans and Stage 6's LIMIT are both this same trolley riding the same chain with a different label on it.

Delete is where textbooks and reality part ways. Textbook B-trees borrow and merge to keep every node at least half full. Real engines, SQLite included, mostly remove the cell, let sparse pages ride, and reclaim only pages that empty completely. Build the honest practical version, and know exactly what you skipped.

Assembly steps

[ 01 ]
Add a right-sibling page id to the leaf header and maintain it during splits: the new leaf inherits the old leaf's sibling, the old leaf points at the new one.
hint

Splits are the only place the chain can break. Add a walkChain check that compares the chain walk against a root-down in-order walk.

[ 02 ]
Build the cursor: Seek descends and positions at the first key greater than or equal to the target, Next advances and hops the sibling pointer at the end of a leaf, Valid gates the loop.
hint

Seeking past the last key must land in a clean invalid state, not a panic. The harness probes exactly this edge.

[ 03 ]
Add scan lo hi in the REPL on top of the cursor: inclusive low, exclusive high, and say so in help.
hint

Test the two edges yourself first: the empty range and the full-table range.

[ 04 ]
Implement delete: remove the cell and compact the slot array. If a leaf empties, unlink it from the chain, drop its separator from the parent, and push the page onto a free list rooted in the meta page.
hint

The free list is a singly-linked list of pages: the first 8 bytes of each free page point at the next free page. No extra structure needed.

[ 05 ]
Make AllocatePage pop the free list before extending the file, so a delete wave followed by inserts reuses space.
hint

The harness watches file size across a delete and reinsert cycle. This is where a free list that only pretends to work gets caught.

Go deeper (after it passes)

The margin note here is a real fork in the road. Read DDIA on B-tree maintenance to see what borrow-and-merge rebalancing buys you, then look at why production engines often decline to pay for it and ship a free list instead.