PageId values the pager loads on demand;Pager and slotted page from episode 128 fresh in mind -- today we reuse the pager verbatim and put a tree of pages on top of it;Learn Zig Series):Last episode we built the floor of a database: a Pager that turns a flat file into an addressable array of durable 4096-byte pages, and a slotted page that packs many variable-length records into one of those pages. It worked, it persisted, and I ended by saying the honest thing -- a heap of records in pages is storage, but it is not yet a database. It is a filing cabinet with the drawers unlabeled. To find a record you either already know its exact page and slot, or you open every drawer in the building. That linear scan is fine for ten records and a catastrophe for ten million.
What turns storage into a database is an index: a searchable structure sitting on top of the pages, so you can find a record by its key in a handful of page reads in stead of a full sweep. And we already know precisely which structure does this job, because we spent an entire episode on it back in episode 108 -- the B-tree. Today we take that exact tree and change one thing about it, the thing that makes it a database index rather than an in-memory toy: every node stops being a heap-allocated struct with pointers, and becomes a page on disk, with child "pointers" that are nothing more than PageId integers the pager loads on demand. Same algorithm, disk underneath. Let's dive right in!
Everything today stands on the pager from episode 128, so let me restate its interface in one block -- this is the whole contract we depend on. A page is 4096 bytes, addressed by a u32 page id, and the pager reads a page into a buffer, writes a buffer back to a page, and grows the file by one zeroed page at a time:
const std = @import("std");
pub const PAGE_SIZE: usize = 4096;
pub const PageId = u32;
pub const Page = [PAGE_SIZE]u8;
pub const Pager = struct {
file: std.fs.File,
page_count: PageId,
pub fn init(file: std.fs.File) !Pager {
const end = try file.getEndPos();
return .{ .file = file, .page_count = @intCast(end / PAGE_SIZE) };
}
pub fn readPage(self: *Pager, id: PageId, out: *Page) !void {
if (id >= self.page_count) return error.PageOutOfRange;
const n = try self.file.preadAll(out, @as(u64, id) * PAGE_SIZE);
if (n != PAGE_SIZE) return error.ShortRead;
}
pub fn writePage(self: *Pager, id: PageId, data: *const Page) !void {
if (id >= self.page_count) return error.PageOutOfRange;
try self.file.pwriteAll(data, @as(u64, id) * PAGE_SIZE);
}
pub fn allocPage(self: *Pager) !PageId {
const id = self.page_count;
const zero: Page = [_]u8{0} ** PAGE_SIZE;
try self.file.pwriteAll(&zero, @as(u64, id) * PAGE_SIZE);
self.page_count += 1;
return id;
}
};
Nothing here is new -- it is episode 128 verbatim, minus the slotted-page layout, which we are replacing today with a B-tree node layout. The point that matters for the tree is allocPage: whenever the tree needs a new node, it asks the pager for a fresh zeroed page and gets back a PageId. That id is the pointer. A parent node stores the id of each child, and to "follow" the pointer you call readPage with that id. Disk offsets, doing the job references did in memory.
In episode 108 a B-tree node was a struct holding an array of keys, an array of values, and an array of child pointers. On disk we keep the exact same three arrays, but we serialize them into the 4096 bytes of a page. A node needs a tiny header too: a flag saying whether it is a leaf, and a count of how many keys it currently holds. Here is the layout, and a Node wrapper that borrows a *Page and reads or writes its header fields as little-endian integers -- the same discipline we used for the page header last time, and for MessagePack back in episode 91:
// A B-tree of minimum degree T: every node (except the root) holds between
// T-1 and 2T-1 keys. We use a small T so splits are easy to observe; a real
// engine picks T so a node fills the page (a few hundred keys).
const T = 3;
const MAX_KEYS = 2 * T - 1; // 5
const MIN_KEYS = T - 1; // 2
const HEADER = 4; // is_leaf(1) + pad(1) + num_keys(2)
const KEYS_OFF = HEADER; // T-2T-1 keys, u64 each
const VALS_OFF = KEYS_OFF + MAX_KEYS * 8;
const CHILD_OFF = VALS_OFF + MAX_KEYS * 8; // MAX_KEYS+1 child ids, u64 each
const Node = struct {
bytes: *Page,
fn isLeaf(self: Node) bool {
return self.bytes[0] != 0;
}
fn setLeaf(self: Node, leaf: bool) void {
self.bytes[0] = if (leaf) 1 else 0;
}
fn numKeys(self: Node) u16 {
return std.mem.readInt(u16, self.bytes[2..4], .little);
}
fn setNumKeys(self: Node, v: u16) void {
std.mem.writeInt(u16, self.bytes[2..4], v, .little);
}
};
A quick sanity check on the arithmetic, because a layout that overflows the page is a bug you want to catch by reasoning, not by crashing. With T = 3 an internal node holds at most five keys, five values, and six child ids: 4 + 5*8 + 5*8 + 6*8 is 132 bytes, comfortably inside 4096. I am deliberately using a small T so that a couple of dozen inserts already force splits and grow the tree's height -- that makes the structure visible in a test. A production B-tree does the opposite: it picks T so a node nearly fills the page (a 4KB node with 8-byte keys and values holds on the order of 200 keys), because a fatter node means a shallower tree means fewer disk reads per lookup. Same code, bigger constant.
Now the three arrays. Keys, values and child ids are all u64 on disk (a child id is a PageId, a u32, but storing it in eight bytes keeps one uniform accessor and costs a few unused bytes we can afford). Each accessor slices an eight-byte window at the right offset and hands it to readInt/writeInt:
fn key(self: Node, i: usize) u64 {
return std.mem.readInt(u64, self.bytes[KEYS_OFF + i * 8 ..][0..8], .little);
}
fn setKey(self: Node, i: usize, v: u64) void {
std.mem.writeInt(u64, self.bytes[KEYS_OFF + i * 8 ..][0..8], v, .little);
}
fn value(self: Node, i: usize) u64 {
return std.mem.readInt(u64, self.bytes[VALS_OFF + i * 8 ..][0..8], .little);
}
fn setValue(self: Node, i: usize, v: u64) void {
std.mem.writeInt(u64, self.bytes[VALS_OFF + i * 8 ..][0..8], v, .little);
}
fn child(self: Node, i: usize) PageId {
return @intCast(std.mem.readInt(u64, self.bytes[CHILD_OFF + i * 8 ..][0..8], .little));
}
fn setChild(self: Node, i: usize, id: PageId) void {
std.mem.writeInt(u64, self.bytes[CHILD_OFF + i * 8 ..][0..8], id, .little);
}
};
That self.bytes[OFF + i*8 ..][0..8] idiom is the same fixed-window trick from last episode, scaled to eight bytes: slice open-ended from a runtime offset, then re-slice [0..8] to recover a *[8]u8 with a comptime-known length, which is exactly what readInt and writeInt demand. Note the Node methods take self by value even when they mutate: bytes is a pointer, so the copy still writes through to the same page. We leaned on that same fact for the slotted page, and it keeps these helpers as light as they read.
One design choice worth naming out loud: this is a classic B-tree, not a B+tree. Every node -- leaf or internal -- carries values alongside its keys, so a key found in an internal node returns its value directly, without descending further. A B+tree pushes all values into the leaves and chains the leaves for faster range scans; it is what most production engines actually use, and it is a natural evolution once this one works. We build the simpler, self-contained B-tree first because it maps one-to-one onto episode 108.
Point lookup is the easy half, and it is a near-transcription of the in-memory search from episode 108. Start at the root page. Read it. Scan its keys for the smallest one that is greater than or equal to the target. If we land exactly on the target, we are done -- return the value stored beside that key. If the node is a leaf and we did not find it, the key is not in the tree. Otherwise follow the child pointer at the scan position, load that page, and repeat:
const BTree = struct {
pager: *Pager,
root: PageId,
fn create(pager: *Pager) !BTree {
const root_id = try pager.allocPage();
var buf: Page = [_]u8{0} ** PAGE_SIZE;
const node = Node{ .bytes = &buf };
node.setLeaf(true);
node.setNumKeys(0);
try pager.writePage(root_id, &buf);
return .{ .pager = pager, .root = root_id };
}
fn search(self: *BTree, target: u64) !?u64 {
var pid = self.root;
while (true) {
var buf: Page = undefined;
try self.pager.readPage(pid, &buf);
const node = Node{ .bytes = &buf };
var i: usize = 0;
const nk = node.numKeys();
while (i < nk and target > node.key(i)) : (i += 1) {}
if (i < nk and node.key(i) == target) return node.value(i);
if (node.isLeaf()) return null;
pid = node.child(i);
}
}
};
Count the disk reads and you see why databases love this shape. Each turn of the loop reads exactly one page and then either returns or descends one level. A B-tree holding a million keys with a healthy fanout is three or four levels deep, so a lookup is three or four page reads -- and the top levels are almost always sitting hot in the operating system's page cache, so in practice it is often a single physical read at the bottom. That is the whole promise of an index: O(log n) page touches instead of O(n). The inner while that scans keys is a plain linear walk here for clarity; with the two-hundred-key nodes a real engine uses you would swap in the binary search we wrote in episode 117, because scanning 200 sorted keys linearly is silly when you can bisect them.
Notice create mints the root as an empty leaf. A freshly allocPage-d page reads back as all zeros, which by our layout is an internal node (leaf byte 0) with zero keys -- not what we want for an empty tree -- so we explicitly setLeaf(true) and write it. Small detail, but it is the difference between a valid empty tree and a subtly broken one.
Insertion is the interesting half, and B-trees do it with a trick that feels backwards the first time you meet it: we split full nodes on the way down, before we have even reached the leaf, rather than splitting on the way back up after an overflow. This is the proactive split from CLRS, and its payoff is enormous -- because we guarantee that every node we step into has room to spare, a split never cascades back up the tree. Each insert is a single top-to-bottom pass, no backtracking.
The one node that has no parent to split it is the root, so the root gets special handling. If the root is full when a new insert arrives, we grow the tree's height by one: allocate a brand-new root, make the old (full) root its only child, split that child, and only then descend. This is the sole way a B-tree gets taller, which is exactly why every leaf stays at the same depth and the tree stays balanced:
fn insert(self: *BTree, k: u64, v: u64) !void {
var rbuf: Page = undefined;
try self.pager.readPage(self.root, &rbuf);
const root = Node{ .bytes = &rbuf };
if (root.numKeys() == MAX_KEYS) {
const new_root_id = try self.pager.allocPage();
var nbuf: Page = [_]u8{0} ** PAGE_SIZE;
const nroot = Node{ .bytes = &nbuf };
nroot.setLeaf(false);
nroot.setNumKeys(0);
nroot.setChild(0, self.root); // old root becomes child 0
try self.pager.writePage(new_root_id, &nbuf);
self.root = new_root_id;
try self.splitChild(new_root_id, 0);
try self.insertNonFull(new_root_id, k, v);
} else {
try self.insertNonFull(self.root, k, v);
}
}
There is one honest caveat here, and I want to flag it rather than hide it. When the root splits, self.root changes to a new page id -- and that id lives only in memory. Reopen the file tomorrow and you would not know which page is the root. A real engine stores the root id in a meta page (page 0, written on every root change) so the tree can be found again. We keep it in the BTree struct for brevity today; wiring the root id into a meta page is a small, satisfying extension and the obvious first thing to add. Having said that, the tree logic itself is complete.
insertNonFull is called only on nodes we have already guaranteed are not full. In a leaf, that guarantee means we can just drop the new key into its sorted position, shifting the larger keys (and their values) one slot to the right to make the gap. If the key already exists we update its value in place rather than duplicate it -- this is an index on a unique key, after all. In an internal node, we find the child the key belongs to, make sure that child is not full (splitting it first if it is), and recurse:
fn insertNonFull(self: *BTree, pid: PageId, k: u64, v: u64) !void {
var buf: Page = undefined;
try self.pager.readPage(pid, &buf);
const node = Node{ .bytes = &buf };
const nk: usize = node.numKeys();
if (node.isLeaf()) {
var s: usize = 0;
while (s < nk) : (s += 1) {
if (node.key(s) == k) { // key exists: update value in place
node.setValue(s, v);
try self.pager.writePage(pid, &buf);
return;
}
}
var j: usize = nk;
while (j > 0 and k < node.key(j - 1)) : (j -= 1) {
node.setKey(j, node.key(j - 1));
node.setValue(j, node.value(j - 1));
}
node.setKey(j, k);
node.setValue(j, v);
node.setNumKeys(@intCast(nk + 1));
try self.pager.writePage(pid, &buf);
return;
}
// internal node: find the child slot for k
var i: usize = 0;
while (i < nk and k > node.key(i)) : (i += 1) {}
if (i < nk and node.key(i) == k) { // key already a separator: update
node.setValue(i, v);
try self.pager.writePage(pid, &buf);
return;
}
var cbuf: Page = undefined;
try self.pager.readPage(node.child(i), &cbuf);
const cnode = Node{ .bytes = &cbuf };
if (cnode.numKeys() == MAX_KEYS) {
try self.splitChild(pid, i);
try self.pager.readPage(pid, &buf); // parent changed: reload it
if (k > node.key(i)) {
i += 1;
} else if (k == node.key(i)) {
node.setValue(i, v);
try self.pager.writePage(pid, &buf);
return;
}
}
try self.insertNonFull(node.child(i), k, v);
}
The shape to hold onto: a leaf insert is a sorted-array insert, plain and finite because we know there is room. The internal case never inserts directly -- it routes. And the crucial line is the reload after splitChild: splitting mutates the parent on disk (it gains the promoted median key and a new child pointer), so we re-read the parent into buf before deciding which side of the freshly promoted key our target belongs to. Forget that reload and you would be steering by a stale copy of the node -- the kind of bug that only shows up after a split, which is to say rarely and confusingly. We route into the correct child and recurse; because we just guaranteed that child is non-full, the recursion is safe all the way down.
Here is the heart of the whole thing. A child node is full -- MAX_KEYS keys -- and we need to make room before descending into it. Splitting takes that one full node and turns it into two half-full nodes plus one key promoted up into the parent. The median key (index T-1) goes up; the T-1 keys to its left stay in the original node; the T-1 keys to its right move into a newly allocated sibling. If the node is internal, its child pointers split the same way, T on each side:
fn splitChild(self: *BTree, parent_id: PageId, i: usize) !void {
var pbuf: Page = undefined;
try self.pager.readPage(parent_id, &pbuf);
const parent = Node{ .bytes = &pbuf };
const child_id = parent.child(i);
var cbuf: Page = undefined;
try self.pager.readPage(child_id, &cbuf);
const child = Node{ .bytes = &cbuf };
const sib_id = try self.pager.allocPage();
var sbuf: Page = [_]u8{0} ** PAGE_SIZE;
const sib = Node{ .bytes = &sbuf };
sib.setLeaf(child.isLeaf());
sib.setNumKeys(MIN_KEYS);
// right half (keys T..2T-1) moves into the sibling
var j: usize = 0;
while (j < MIN_KEYS) : (j += 1) {
sib.setKey(j, child.key(j + T));
sib.setValue(j, child.value(j + T));
}
if (!child.isLeaf()) {
j = 0;
while (j < T) : (j += 1) sib.setChild(j, child.child(j + T));
}
const median_key = child.key(T - 1);
const median_val = child.value(T - 1);
child.setNumKeys(MIN_KEYS); // left half keeps keys 0..T-2
try self.pager.writePage(child_id, &cbuf);
try self.pager.writePage(sib_id, &sbuf);
// make room in the parent and slot the median + new child in
var p: usize = parent.numKeys();
while (p > i) : (p -= 1) {
parent.setKey(p, parent.key(p - 1));
parent.setValue(p, parent.value(p - 1));
parent.setChild(p + 1, parent.child(p));
}
parent.setKey(i, median_key);
parent.setValue(i, median_val);
parent.setChild(i + 1, sib_id);
parent.setNumKeys(@intCast(parent.numKeys() + 1));
try self.pager.writePage(parent_id, &pbuf);
}
Walk it slowly, because there is real bookkeeping. With T = 3 the full child has five keys at indices 0 through 4. Index 2 is the median: it goes up to the parent. Indices 0 and 1 (two keys, MIN_KEYS) stay in the child, which we shrink by simply setting its key count to two -- the bytes of the moved keys are still physically there, but they are now beyond num_keys and thus invisible, the same lazy-deletion idea as last episode's tombstones. Indices 3 and 4 move into the sibling. If the node is internal, the six child pointers split three and three. Then the parent: we shift its keys, values and child pointers rightward from position i to open a gap, drop the median key and value into slot i, and point the new child slot i+1 at the sibling. Three pages written -- shrunken child, new sibling, updated parent -- and the invariant holds: a node that had 2T-1 keys is now two nodes of T-1 keys with one key lifted into the parent, and every path to a leaf is still the same length.
A point lookup is one thing, but the reason you reach for a B-tree over a hash table is order. The keys come out sorted, which is what makes range scans -- "every user id between 1000 and 2000" -- possible at all. An in-order traversal proves the tree is correctly sorted end to end: for each node, recurse into child 0, emit key 0, recurse into child 1, emit key 1, and so on, finishing with the last child. We write the keys into a caller-provided slice (no allocation) and bump a count, so a test can check them:
fn collect(self: *BTree, pid: PageId, out: []u64, n: *usize) !void {
var buf: Page = undefined;
try self.pager.readPage(pid, &buf);
const node = Node{ .bytes = &buf };
const nk: usize = node.numKeys();
var i: usize = 0;
while (i < nk) : (i += 1) {
if (!node.isLeaf()) try self.collect(node.child(i), out, n);
out[n.*] = node.key(i);
n.* += 1;
}
if (!node.isLeaf()) try self.collect(node.child(nk), out, n);
}
The buffer is a fresh Page on the stack for each recursive call, which matters more than it looks: because every node lives on disk and we read it into a local buffer, the recursion naturally holds only the pages on the current root-to-leaf path in memory at once, never the whole tree. That is the same reason this design scales to databases far larger than RAM -- you only ever hold a path's worth of pages, plus whatever the pager decides to cache. Handing in the output slice keeps collect allocation-free -- the caller owns the memory, exactly the borrowing discipline from episode 5. A real range scan would take a low and high bound and prune whole subtrees that fall outside them; the full walk here is that idea with the bounds set to infinity.
Enough prose -- does it survive the disk? The test that matters wraps a fresh BTree handle around the same pager and root id, sharing nothing with the writer but the file itself, and checks the values come back:
test "b-tree persists to disk and reopens" {
var tmp = std.testing.tmpDir(.{});
defer tmp.cleanup();
const file = try tmp.dir.createFile("index.db", .{ .read = true });
defer file.close();
var pager = try Pager.init(file);
var tree = try BTree.create(&pager);
try tree.insert(42, 4200);
try tree.insert(7, 700);
try tree.insert(99, 9900);
// a brand-new handle over the same file + root -- nothing shared but disk
var reopened = BTree{ .pager = &pager, .root = tree.root };
try std.testing.expectEqual(@as(?u64, 4200), try reopened.search(42));
try std.testing.expectEqual(@as(?u64, 700), try reopened.search(7));
try std.testing.expectEqual(@as(?u64, null), try reopened.search(1234));
}
The reopened handle never saw an insert; it only knows the root page id and reads pages off disk. It answers correctly because the tree is the bytes in the file -- keys, values, child ids, all serialized little-endian into pages. The in-memory BTree struct is a thin steering wheel over a car that lives entirely on disk. That is the property episode 128 promised and this episode cashes in.
The real stress test is many keys in a hostile order. I insert two hundred keys in reverse -- 199, 198, 197, down to 0 -- which is the pattern that would turn a naive binary search tree into a useless linked list. A B-tree does not care: proactive splitting keeps it balanced whatever the order. Then I check every key reads back, the in-order walk yields 0..199 in perfect sequence, and the root is no longer a leaf, proving the tree actually grew in height:
test "hundreds of reversed inserts stay sorted and grow the tree" {
var tmp = std.testing.tmpDir(.{});
defer tmp.cleanup();
const file = try tmp.dir.createFile("big.db", .{ .read = true });
defer file.close();
var pager = try Pager.init(file);
var tree = try BTree.create(&pager);
const N: u64 = 200;
var i: u64 = 0;
while (i < N) : (i += 1) {
const k = N - 1 - i; // reverse order: worst case for a naive tree
try tree.insert(k, k * 10);
}
i = 0;
while (i < N) : (i += 1) {
try std.testing.expectEqual(@as(?u64, i * 10), try tree.search(i));
}
var out: [256]u64 = undefined;
var n: usize = 0;
try tree.collect(tree.root, &out, &n);
try std.testing.expectEqual(@as(usize, N), n);
i = 0;
while (i < N) : (i += 1) {
try std.testing.expectEqual(i, out[@intCast(i)]);
}
var rbuf: Page = undefined;
try pager.readPage(tree.root, &rbuf);
try std.testing.expect(!(Node{ .bytes = &rbuf }).isLeaf()); // multi-level
}
This is the test that would have caught every off-by-one in splitChild. If the median went up wrong, keys would be missing or out of order and the in-order walk would not equal 0..199. If the child-pointer split were off, a whole subtree would vanish and the length check would fail. When this passes -- and it does -- you can trust the split logic, because two hundred reversed inserts exercise root splits, internal splits and leaf splits many times over. Wowzers, that is a real balanced disk index doing its job.
One last behaviour, small but important for an index: inserting a key that already exists must update its value, not shadow it with a duplicate. Both code paths handle it, and the test pins it down:
test "inserting an existing key updates its value" {
var tmp = std.testing.tmpDir(.{});
defer tmp.cleanup();
const file = try tmp.dir.createFile("upd.db", .{ .read = true });
defer file.close();
var pager = try Pager.init(file);
var tree = try BTree.create(&pager);
try tree.insert(5, 500);
try tree.insert(5, 555);
try std.testing.expectEqual(@as(?u64, 555), try tree.search(5));
}
Duplicate distinct rows under one key -- a secondary index where many rows share a value -- would store a list or a chain of row pointers instead of a single value, but the update-in-place logic is the right default for a primary-key index and it keeps the tree honest.
Every serious database on earth is, at its core, the two episodes we just wrote: pages underneath, a B-tree index on top. SQLite stores its tables and indexes as B-trees of pages, managed by exactly the pager we borrowed -- an interior page holds keys and child page numbers, a leaf page holds keys and payloads, and the whole file is that tree. Its splitting logic is our splitChild with production hardening (overflow pages for oversized rows, a free list for recycled pages). Postgres keeps its heap and its indexes separate -- tuples live in the slotted heap pages from last episode, and a B-tree index (the nbtree code) stores keys plus a TID pointing at the heap tuple, which is the B+tree variant I mentioned, values in the leaves and leaves chained for range scans.
In Rust, redb is an explicit page-and-B-tree design and leans on ownership to track which pages a live transaction has borrowed, catching at compile time the aliasing bugs a C engine chases with a debugger. In Go, bbolt -- the store behind etcd, and therefore behind every Kubernetes cluster on the planet -- is a memory-mapped, copy-on-write B+tree of pages: it mmaps the file (episode 31), treats it as an array of pages (episode 128), and navigates a B-tree over them (this episode). Four engines, four languages, one architecture, and you have now built the load-bearing half of it. We wrote a miniature, but it is a miniature of the real thing, not a cartoon of it.
Zig's contribution to this old design is the same as last time: the hazards are types, not conventions. A short read is a returned error.ShortRead, an out-of-range page is error.PageOutOfRange, a node buffer is a *Page of known size so an over-eager index is bounds-checked in safe builds, and every integer crosses the disk boundary with an explicit endianness so the format is portable by construction. A C B-tree has every one of these hazards; the difference is the compiler refuses to let a !void from writePage go unchecked, so "I forgot to handle the write failing" is not a class of bug that survives compilation.
Look at what we have standing now. A file that is an array of durable pages, and on top of it a balanced B-tree whose every node is one of those pages, that finds any key in a few page reads, keeps its keys in sorted order for range scans, splits and grows without ever unbalancing, updates in place, and -- proven -- survives being closed and reopened with nothing shared but the bytes on disk. That is an index. That is the difference between a heap of records and a database.
But an index you drive by calling insert and search from Zig is a library, not a database -- a database is something a human asks questions of, in a language. We have a store, we have an index over it, and the missing piece is the part that turns the string SELECT value FROM t WHERE key = 42 into calls to the machinery we just built. And here is the lovely thing: we already know how to do that, because we built a tokenizer and a recursive-descent parser twice in this series, for Markdown and for the search engine's query language. The next brick turns text into a plan the engine can run. Take the two modules from these two episodes, point them at a file, insert a few thousand keys, and watch a real on-disk index take shape -- then try storing the root id in a meta page so your tree reopens for real. Get that working and you understand more about how your database works than most of the people shipping on top of one. ;-)
Thanks for your time, and I'll catch you in the next episode! ;-)
@scipio