Every node is a fixed-size page from lesson one, so the index genuinely lives on disk and never leans on host pointers or the garbage collector. Grow it one durable piece at a time - pages, nodes, search, splits, deletes, range scans - then move it to a real file and make writes crash-safe with copy-on-write and an atomic double-meta swap. The capstone crashes it mid-write and proves every committed key survived.
Over 45 lessons you build a working B+Tree index that lives on disk and survives a crash. From the very first lesson a tree node IS a fixed-size 4096-byte page addressed by an integer page id and reached through a pager (AllocPage, ReadPage, WritePage, FreePage), so nothing ever relies on in-memory pointers or the garbage collector. You serialize leaf and internal nodes to exact bytes, search by descending page to page, insert with leaf and internal splits that keep every leaf at equal depth, delete with borrow-and-merge rebalancing, and answer ordered range scans by walking leaf sibling links.
The core runs on an in-memory pager, so the move to disk is a pager swap, not a rewrite: a file-backed pager maps page id to file offset, a meta page names the root and a free list recycles pages, and the index reopens from its file with every key intact. Then you make writes crash-safe with copy-on-write and a double meta page - a write copies every page it touches to a fresh page, never overwriting a live one, then publishes atomically by fsyncing a new meta slot chosen by sequence number and checksum. The capstone writes a batch, simulates a crash with no clean close, reopens the file, and proves every committed key is present with the tree invariants intact.
This is a teaching-grade index built around the real design used by SQLite and LMDB: a single-writer, crash-safe on-disk B+Tree you import as a library (Open, Get, Put, Delete, Scan, Close). It stops short of what a production engine adds - concurrent transactions and MVCC readers, variable-length keys and overflow pages, and the write-ahead-log durability path this project deliberately leaves as the alternative to copy-on-write.
A B+Tree that lives on disk is made of fixed-size pages, and every tree node will be exactly one page. Today you define that page and the integer id that names it, so from the very first line nothing depends on host pointers.
Define a fixed page size, a page buffer, and a page-id type, and confirm a fresh page is all zeros.
A disk is not a graph of objects; it is a flat array of bytes you read and write in fixed blocks. A B+Tree that intends to live there has to be built the same way, so the first decision is the page: a fixed-size chunk of bytes (4096 here, a common disk block size) that is the unit of everything. Every node in the tree - leaf or internal - will be exactly one page, serialized into that buffer.
The other atom is the page id: a plain integer that names a page. Today it
names a slot in memory; in the on-disk chapter the same id becomes a file offset
(id * PageSize). Because nodes will refer to each other by page id rather than
by pointer, the tree is already shaped for disk from this first lesson - nothing
downstream ever leans on the garbage collector to hold a node in place.
const PageSize = 4096// a page id names a page; it will map to a file offset latertype PageID uint32// a page is just a fixed-size byte buffer - a node lives inside onefunc newPage() []byte { return make([]byte, PageSize) }
A genuinely crash-safe on-disk B+Tree index - copy-on-write writes published through a checksummed double meta page, proven by tests to survive a crash mid-write with every committed key present and all invariants intact - but single-writer, built at a small teaching fanout, with a simplified durable delete and free-page reclamation, so it is a teaching-grade index rather than a production one.
The classic 1979 survey that names the B-tree and B+Tree variants, the fanout math, and the split and merge rules this project implements.
A production on-disk B+Tree file format: fixed-size pages, a header page naming the root, leaf and interior page layouts - the concrete counterpart to the format you build.
How the pager, the B-tree module, and the file interact - the layered design this project mirrors, pager underneath and tree on top.
The copy-on-write plus double-meta-page design the crash-safety chapter follows: never overwrite a live page, publish atomically by fsyncing the older of two meta pages.
Part I is a deep tour of on-disk B-trees: page layout, splits and merges, rebalancing, and the durability machinery - the reference textbook for everything here.