comptime minimum degree (episode 14), nodes owned by an allocator (episodes 7 and 26), searched and inserted into with nothing more exotic than array shuffles;std.testing.allocator (episode 12);T and a compile-time degree, and own every node explicitly;Learn Zig Series):Last episode I ended on a deliberate fork in the road. The skip list solved "keep an ordered collection fast under constant mutation" by cheating with coins -- randomness did the balancing, and you got O(log n) in expectation, an average over the coin flips rather than a promise. I said the other answer was deterministic: enforce a strict structural rule, pay real work to maintain it on every insert, and get balance that is guaranteed instead of merely likely. Today we walk that deterministic road, and the structure at the end of it is the single most consequential data structure in all of applied computing that nobody outside the field has heard of -- the B-tree. Every SQL database index you have ever queried is one. The filesystem holding this file is built on one. Before we build ours, let me clear the small debt from episode 107.
Exercise 1 -- count how many nodes hold a value. Since our skip-list insert permitted duplicates, equal keys sit adjacent on the bottom level (forward[0]). So we do the usual descend to land just left of the first match, then walk the ground floor counting equals until one isn't. Same descent you wrote three times last episode, with a counting tail.
// Add inside SkipList(comptime T, comptime lessThan). Descend to the greatest node
// strictly less than `value`, then walk forward[0] counting equal keys. Because the
// ground floor is sorted, the moment a node is NOT equal we are past the run and stop.
fn count(self: *Self, value: T) usize {
var node = self.head;
var i = self.level;
while (i > 0) {
i -= 1;
while (node.forward[i]) |next| {
if (lessThan(next.value, value)) node = next else break;
}
}
var total: usize = 0;
var it = node.forward[0];
while (it) |n| : (it = n.forward[0]) {
// "equal" = neither less than the other. First non-equal ends the run.
if (lessThan(n.value, value) or lessThan(value, n.value)) break;
total += 1;
}
return total;
}
Exercise 2 -- a range query. Descend to the first node whose value is >= lo, then walk forward[0] collecting until we pass hi. This is exactly the machinery behind Redis's ZRANGEBYSCORE, and it falls out of the skip list almost for free because the bottom level is a fully sorted linked list.
// Descend using `lo` as the target, which lands node just left of the first value >= lo.
// Then sweep forward[0] appending everything in [lo, hi], stopping the instant we exceed hi.
fn range(self: *Self, lo: T, hi: T, out: *std.ArrayList(T)) !void {
var node = self.head;
var i = self.level;
while (i > 0) {
i -= 1;
while (node.forward[i]) |next| {
if (lessThan(next.value, lo)) node = next else break;
}
}
var it = node.forward[0]; // first node with value >= lo
while (it) |n| : (it = n.forward[0]) {
if (lessThan(hi, n.value)) break; // n.value > hi -> done
try out.append(n.value); // lo <= n.value <= hi
}
}
Exercise 3 -- turn the multiset into a proper map. The change is small but load-bearing: store an Entry{ key, value } in each node, order the towers by .key, and on insert, if the descent lands on a node whose key equals the incoming key, overwrite its value in place and return -- so len never grows on a re-put and nothing leaks. Here are the two methods that carry the difference (they slot into a skip list whose node value type is Entry and whose comparator is keyLess over the key type):
// put: the episode's insert with ONE added early exit. If the candidate at forward[0]
// has a key equal to ours, we mutate its value and leave -- no new node, len unchanged.
fn put(self: *Self, key: K, value: V) !void {
var update: [max_level]*Node = undefined;
var node = self.head;
var i = self.level;
while (i > 0) {
i -= 1;
while (node.forward[i]) |next| {
if (keyLess(next.value.key, key)) node = next else break;
}
update[i] = node;
}
if (node.forward[0]) |cand| {
if (!keyLess(cand.value.key, key) and !keyLess(key, cand.value.key)) {
cand.value.value = value; // same key -> update in place
return;
}
}
const lvl = self.randomLevel();
if (lvl > self.level) {
var j = self.level;
while (j < lvl) : (j += 1) update[j] = self.head;
self.level = lvl;
}
const fresh = try self.createNode(.{ .key = key, .value = value }, lvl);
var k: usize = 0;
while (k < lvl) : (k += 1) {
fresh.forward[k] = update[k].forward[k];
update[k].forward[k] = fresh;
}
self.len += 1;
}
// get: the plain descent, then one equality check on the candidate.
fn get(self: *Self, key: K) ?V {
var node = self.head;
var i = self.level;
while (i > 0) {
i -= 1;
while (node.forward[i]) |next| {
if (keyLess(next.value.key, key)) node = next else break;
}
}
const cand = node.forward[0] orelse return null;
if (!keyLess(cand.value.key, key) and !keyLess(key, cand.value.key)) return cand.value.value;
return null;
}
That's the debt paid. Notice the shape of exercise 3 -- "one comparator, expressed only through lessThan, equality faked as neither-less-than" -- because that exact discipline carries straight into today's tree. On to it.
Start from the binary search tree you already half-know: one key per node, two children, and if you keep it balanced you get O(log n) everything. The height of a balanced binary tree over n keys is about log2(n). For a million keys that's around 20 levels, meaning a search touches roughly 20 nodes -- 20 separate hops through memory, and as we belaboured in episodes 107 and 34, every hop is a potential cache miss.
Now here is the B-tree's one big idea. Instead of one key per node, put many -- dozens, hundreds -- keys into a single node, kept sorted inside the node in a flat array. A node with m keys has m + 1 children, one for each gap between (and around) the keys. Because each node fans out into many children instead of just two, the tree gets dramatically shorter. The height is now about log_m(n): with, say, 100 keys per node, a billion keys fit in a tree only about five levels deep. Five hops in stead of thirty. And crucially, once you have hopped to a node, all its keys are packed contiguously, so you scan them with a cache-friendly linear or binary search over an array -- the kind of work modern CPUs devour.
That "make the node fat so the tree is short" idea is not an academic nicety. It is the entire reason B-trees exist. They were invented in 1970 at Boeing (Bayer and McCreight) for disk, where a single seek reads a whole block of thousands of bytes and the cost of that seek dwarfs the cost of examining the bytes once they're in memory. If one node maps to one disk block, then the number of nodes you visit is the number of disk seeks, and you want that number as small as physically possible. Same logic applies, one rung down, to the cache-line vs main-memory gap on a modern CPU. A B-tree is, at heart, a tree tuned to the size of whatever the expensive fetch happens to be.
The parameter that controls the fatness is the minimum degree, universally written t. The rule (Knuth's formulation, the one every textbook uses) is: every node except the root holds between t - 1 and 2t - 1 keys. The root may hold as few as one. A node is full when it has the maximum 2t - 1 keys. That single "between half and full" invariant is what guarantees the tree can never get lopsided -- there is a hard floor on how few keys a node may have, so the tree can never grow a spindly branch.
Because the capacity 2t - 1 is known at compile time, we don't need heap-allocated slices for the keys and children the way the skip list needed for its variable-height towers. We use plain fixed-size arrays, sized by the comptime degree (episode 14 again -- generics carrying real weight). Each node itself is heap-allocated (we own a variable number of nodes), but its innards are stack-flat arrays.
const std = @import("std");
fn BTree(comptime T: type, comptime t: usize, comptime lessThan: fn (a: T, b: T) bool) type {
return struct {
const Self = @This();
const max_keys = 2 * t - 1; // a full node
const min_keys = t - 1; // the floor for every non-root node
// The node: a sorted run of `n` keys and (if internal) n+1 children. keys and
// children are fixed-capacity arrays -- sized at comptime, no per-node allocation
// for them. A `leaf` node simply ignores its children array.
const Node = struct {
keys: [max_keys]T = undefined,
children: [max_keys + 1]*Node = undefined,
n: usize = 0, // how many keys are actually live
leaf: bool = true,
};
root: ?*Node,
allocator: std.mem.Allocator,
len: usize,
fn init(allocator: std.mem.Allocator) Self {
return .{ .root = null, .allocator = allocator, .len = 0 };
}
};
}
t is a compile-time constant, so [2*t - 1]T is a concrete array type the compiler lays out with zero runtime cost. Pass t = 3 and every node holds 2 to 5 keys; pass t = 128 and you get the fat, disk-block-shaped nodes real databases use. The same source compiles to both -- this is comptime generics doing exactly what episode 14 promised, specialising the layout with no boilerplate and no macros.
Searching a B-tree is the binary-search-tree walk generalised to fat nodes. Within a node, scan the sorted keys for your target. If you find it, done. If not, the scan stops at the first key greater than your target, and the child hanging in the gap just before that key is the only place the target could live -- descend into it. Fall off a leaf without a match and the key isn't present. Same "express equality with only lessThan" trick from the skip list.
// searchNode: linear-scan this node's sorted keys. `i` lands on the first key not less
// than `value`. If that key equals `value` we found it; otherwise descend children[i]
// (the subtree between keys[i-1] and keys[i]), or fail if this is a leaf.
fn searchNode(node: *Node, value: T) ?*Node {
var i: usize = 0;
while (i < node.n and lessThan(node.keys[i], value)) : (i += 1) {}
if (i < node.n and !lessThan(value, node.keys[i])) return node; // keys[i] == value
if (node.leaf) return null;
return searchNode(node.children[i], value);
}
fn contains(self: *Self, value: T) bool {
const r = self.root orelse return false;
return searchNode(r, value) != null;
}
I used a linear scan inside the node for clarity. For large t you'd swap it for a binary search over keys[0..n] -- the keys are sorted, so it's a textbook std.sort-style bisection, and it turns the per-node cost from O(t) into O(log t). For the small t I'll test with, linear is fine and honestly faster (branch predictors love short predictable loops), which is a recurring theme: the asymptotically-worse algorithm frequently wins at small sizes because the constants and the cache behaviour dominate.
Everything interesting about a B-tree is in how it stays balanced, and the whole mechanism reduces to a single move: splitting a full node. When a node fills up (2t - 1 keys), we split it into two nodes of t - 1 keys each, and push its middle key up into the parent, where it becomes a separator between the two halves. The parent gains one key and one child. That's it -- that's the entire balancing act, no rotations anywhere.
// splitChild: parent.children[i] is FULL (2t-1 keys). Split it into two half-nodes and
// promote its median key up into `parent` at slot i. The left half keeps keys[0..t-1];
// the new right node `z` takes keys[t..2t-1]; the median keys[t-1] moves up.
fn splitChild(self: *Self, parent: *Node, i: usize) !void {
const child = parent.children[i];
const z = try self.allocator.create(Node);
z.* = .{};
z.leaf = child.leaf;
z.n = min_keys;
// z takes the upper t-1 keys...
var j: usize = 0;
while (j < min_keys) : (j += 1) z.keys[j] = child.keys[j + t];
// ...and, if internal, the upper t children that hang off those keys.
if (!child.leaf) {
j = 0;
while (j < t) : (j += 1) z.children[j] = child.children[j + t];
}
child.n = min_keys; // child keeps the lower t-1 keys; the median leaves
// Open a slot in parent.children for z, right after the child we split.
var k = parent.n + 1;
while (k > i + 1) : (k -= 1) parent.children[k] = parent.children[k - 1];
parent.children[i + 1] = z;
// Open a slot in parent.keys for the promoted median.
k = parent.n;
while (k > i) : (k -= 1) parent.keys[k] = parent.keys[k - 1];
parent.keys[i] = child.keys[t - 1];
parent.n += 1;
}
Read that against the skip list's splice and you see the family resemblance: a fixed amount of array shuffling to open a slot, then a couple of assignments. The subtlety is purely the bookkeeping of which keys and children go where -- get the + t offsets right and everything else is mechanical. Nota bene: splitting requires the parent to have room for one more key, which is why the insert algorithm below is careful to only ever descend into a node after ensuring it isn't full. That precondition is the quiet genius of the whole design.
Here is the move that makes B-trees so clean. We insert in a single top-down pass, and proactively split any full node we're about to descend into. Because we split full nodes before entering them, we can guarantee that whenever we need to split a child, its parent has room to accept the promoted key -- the "parent isn't full" precondition holds by construction. The only place the tree grows taller is when the root itself is full: we make a fresh empty root, hang the old root beneath it, split, and the height goes up by exactly one. This is why a B-tree grows from the root, not the leaves, and why every leaf always sits at the exact same depth. Perfect balance, guaranteed, not hoped for.
// insertNonFull: the node is guaranteed to have room. In a leaf, shift bigger keys right
// and drop `value` into place. In an internal node, find the child to descend, split it
// first if it's full (which may bump us one slot right), then recurse.
fn insertNonFull(self: *Self, node: *Node, value: T) !void {
if (node.leaf) {
var i = node.n;
while (i > 0 and lessThan(value, node.keys[i - 1])) : (i -= 1) {
node.keys[i] = node.keys[i - 1];
}
node.keys[i] = value;
node.n += 1;
} else {
var i: usize = 0;
while (i < node.n and lessThan(node.keys[i], value)) : (i += 1) {}
if (node.children[i].n == max_keys) {
try self.splitChild(node, i);
// The median we just promoted now sits at keys[i]; if value is bigger,
// it belongs in the NEW right half, one child over.
if (lessThan(node.keys[i], value)) i += 1;
}
try self.insertNonFull(node.children[i], value);
}
}
// insert: handle the empty tree and the full-root (height-growing) case, then delegate.
fn insert(self: *Self, value: T) !void {
if (self.root == null) {
const r = try self.allocator.create(Node);
r.* = .{};
r.keys[0] = value;
r.n = 1;
self.root = r;
self.len += 1;
return;
}
const r = self.root.?;
if (r.n == max_keys) {
// Root is full: grow the tree upward by one level.
const s = try self.allocator.create(Node);
s.* = .{};
s.leaf = false;
s.children[0] = r;
self.root = s;
try self.splitChild(s, 0);
try self.insertNonFull(s, value);
} else {
try self.insertNonFull(r, value);
}
self.len += 1;
}
Trace it once in your head with t = 2 (nodes hold 1 to 3 keys) inserting 1, 2, 3, 4, 5. You add 1, 2, 3 into the root until it's full. Inserting 4 finds the root full, so insert builds a new root above it, splits the old root -- 2 goes up alone, leaving [1] and [3] as children -- and then 4 lands in the [3] leaf making it [3, 4]. Add 5 and that leaf becomes [3, 4, 5], full but not yet split. The tree is two levels deep, both leaves at the same depth. That "both leaves at the same depth, always" is the invariant a plain BST cannot promise and a B-tree gives you for free.
To prove our tree is correct we need to read every key back out in sorted order, which is the classic in-order traversal generalised to fat nodes: for each key slot, first recurse into the child to its left, then emit the key; after the last key, recurse into the final child. And because we own every node (episode 7's rule: whoever allocates, frees), teardown is a post-order walk freeing children before their parent.
// inorder: for a node with n keys and n+1 children, interleave child-then-key, then the
// last child. Over a valid B-tree this yields every key in ascending order.
fn inorder(node: *Node, out: *std.ArrayList(T)) !void {
var i: usize = 0;
while (i < node.n) : (i += 1) {
if (!node.leaf) try inorder(node.children[i], out);
try out.append(node.keys[i]);
}
if (!node.leaf) try inorder(node.children[node.n], out);
}
fn collect(self: *Self, out: *std.ArrayList(T)) !void {
if (self.root) |r| try inorder(r, out);
}
// freeNode: post-order -- free all children first, then the node itself.
fn freeNode(self: *Self, node: *Node) void {
if (!node.leaf) {
var i: usize = 0;
while (i <= node.n) : (i += 1) self.freeNode(node.children[i]);
}
self.allocator.destroy(node);
}
fn deinit(self: *Self) void {
if (self.root) |r| self.freeNode(r);
self.root = null;
}
Note the child loop runs i <= node.n, not i < node.n -- an internal node with n keys has n + 1 children, and forgetting that off-by-one leaks the last subtree on every internal node. That's precisely the class of bug std.testing.allocator catches for us, so let's put it to work.
The load-bearing invariant of a B-tree is "an in-order walk is sorted" -- if that holds, search and insert are provably placing keys in the right subtrees. So the test inserts a deliberately scrambled batch, collects them, and asserts the result is sorted and complete. Pair that with std.testing.allocator (episode 12) and we simultaneously get correctness and a guarantee that not one of those internal nodes leaked a subtree.
fn u32Less(a: u32, b: u32) bool {
return a < b;
}
test "b-tree: sorted in-order walk, membership, no leaks" {
var tree = BTree(u32, 3, u32Less).init(std.testing.allocator); // t=3: 2..5 keys/node
defer tree.deinit(); // testing.allocator fails the test if freeNode misses a subtree
// Insert out of order, with a duplicate, enough to force several splits.
const values = [_]u32{ 50, 20, 80, 10, 30, 60, 90, 5, 25, 35, 70, 85, 95, 15, 20 };
for (values) |v| try tree.insert(v);
try std.testing.expectEqual(@as(usize, values.len), tree.len);
// Membership: everything we inserted is found, and a gap value is not.
try std.testing.expect(tree.contains(35));
try std.testing.expect(tree.contains(5));
try std.testing.expect(!tree.contains(999));
// The invariant that proves the whole structure: in-order output is ascending.
var out = std.ArrayList(u32).init(std.testing.allocator);
defer out.deinit();
try tree.collect(&out);
try std.testing.expectEqual(values.len, out.items.len);
var i: usize = 1;
while (i < out.items.len) : (i += 1) {
try std.testing.expect(out.items[i - 1] <= out.items[i]);
}
}
That ascending-order assertion is the one I'd defend hardest in review, same as the skip list's forward[0] sweep last episode: it's a single check that fails loudly the instant any split misplaced a key or any descent chose the wrong child. And because a B-tree is fully deterministic -- no RNG anywhere -- this test does the same thing byte-for-byte on every run without our even having to seed anything. That determinism is the whole trade we made versus the skip list ;-)
Search, insert, and delete are all O(log n) -- and unlike the skip list, that's a worst-case guarantee, not an expectation over coin flips, because the "every node at least half full" invariant hard-caps the height at roughly log_t(n). There is no pathological input, no unlucky seed, no cosmic-ray scenario that degrades it. You pay for that guarantee with real work on every insert (the proactive splits) versus the skip list's occassional coin flip, but the ceiling is rock solid.
The cache and disk story is where the B-tree pulls decisively ahead of every pointer-per-key structure we've built. A balanced binary tree over a million keys is ~20 pointer hops, each a likely cache miss. A B-tree with t = 64 (nodes up to 127 keys) over the same million keys is three levels deep -- three node fetches, and each node is a contiguous array the CPU prefetches and scans at full speed. When the nodes are sized to a disk block, those three fetches are three disk reads instead of twenty, and since a disk seek is on the order of a hundred thousand times slower than a memory access, that difference is the whole ballgame. The B-tree doesn't win on comparisons -- it does roughly the same number as any log-n tree -- it wins by making the expensive operation (the fetch) rare.
When does a B-tree lose? When your data is small and lives entirely in fast memory, and especially when it's read-only. If you have ten thousand integers you look up constantly and never change, a plain sorted array with binary search beats a B-tree flat -- it's one contiguous block, maximally cache-friendly, zero pointer chasing. The B-tree earns its complexity exactly when the dataset is large, mutates, and lives across a slow boundary (disk, or a cache hierarchy under memory pressure). That is a narrower niche than it sounds -- it just happens to be the niche that databases and filesystems occupy.
The list is short and staggering. Every major relational database -- PostgreSQL, MySQL/InnoDB, Oracle, SQL Server, SQLite -- stores its indexes as B-trees (specifically the B+ tree variant, where all real data hangs off the leaves and internal nodes hold only separator keys, with the leaves chained together for fast range scans). When you put an index on a column and your query gets a thousand times faster, a B-tree is what you built. Filesystems run on them too: NTFS (Windows), HFS+ and APFS (Apple), ext4's directory indexing, Btrfs (the "B" is literally for B-tree), XFS -- the directory-lookup and extent-mapping structures are B-trees, because a filesystem is exactly "a huge mutable sorted map that lives on disk", the B-tree's home turf. Key-value stores that aren't LSM-based (LMDB, BoltDB) are memory-mapped B-trees. When people say the B-tree is the most important data structure in systems programming, this is why -- it silently underpins essentially all persistent, indexed storage on the planet.
The B+ tree refinement is worth knowing because it's what production systems actually use: keep all values in the leaves, use internal nodes purely as a routing directory of separator keys, and thread the leaves together in a linked list. That gives you two things our plain B-tree doesn't optimise for -- a range scan becomes "find the start leaf, then walk the leaf chain" (no bouncing up and down the tree), and the internal nodes stay tiny and fit more separators per block, making the tree even shorter. The core split-and-promote mechanics you just wrote are identical; the B+ tree just relocates where the payloads sit.
In C, the B-tree is honestly one of the nicer structures to hand-write, precisely because the node is fixed-size arrays rather than a web of individually-allocated links. You malloc one struct per node, and the keys and children live inline. The classic bugs are all in the index arithmetic -- the + t offsets in the split, the i <= n child count in traversal -- and C gives you no help: an off-by-one there is silent memory corruption or a leaked subtree with nothing to shout about it. Our Zig version is the same algorithm with the same array layout, but std.testing.allocator turns a leaked subtree into a failed test, and Zig's bounds checking in debug builds turns an index slip into a clean panic with a stack trace in stead of a corrupted heap you discover three hours later.
In Rust, the B-tree is famously the structure the standard library chose for its ordered map -- std::collections::BTreeMap is a B-tree, not a red-black tree, and the authors picked it explicitly for the cache behaviour we discussed. Writing your own in safe Rust is very tractable because the pointers all flow strictly parent-to-child with no back-references -- none of the mutual-aliasing pain that sent the doubly linked list into Rc<RefCell<>> back in episode 106. You still lean on Box for the child pointers and fight the borrow checker a little around moving keys during a split, but it's a pleasant fight compared to a doubly linked list. That the standard library's own map is a B-tree tells you how far the cache argument carries.
In Go, the standard library has no ordered map at all (its map is a hash table, unordered), so a B-tree is exactly the kind of thing you'd reach for a package like google/btree to get -- and Google's own in-memory B-tree package is widely used precisely because "sorted, mutable, cache-friendly" isn't otherwise on the menu. Go's generics (1.18+) finally let such a package be typed without interface{} boxing on every key, which for a structure whose entire value proposition is packing keys densely into cache-friendly arrays actually matters a great deal -- boxing would scatter your keys back across the heap and throw away the locality you built the tree to get. Our Zig version, with comptime T laid out inline and no GC, gives you that density by construction and pays no collector tax on the pointer-heavy internal nodes.
min(self: *Self) ?T and max(self: *Self) ?T. The smallest key lives at the far-left leaf -- from the root, keep descending children[0] until you hit a leaf, then return keys[0]. The largest mirrors it down children[node.n] returning keys[node.n - 1]. Handle the empty tree, and test both against a scrambled batch of insertions.height(self: *Self) usize that returns the number of levels, and write a test that inserts a few hundred sequential integers with a small t (say 2 or 3) and asserts the height stays within the theoretical log_t(n) bound. This is the concrete payoff of the guaranteed-balance property -- prove the tree never grows taller than the math allows.delete(self: *Self, value: T) bool. Deletion is the genuinely fiddly B-tree operation because a leaf can underflow below t - 1 keys and must borrow a key from a sibling or merge with one, which is the split in reverse. Follow the same top-down discipline as insert -- ensure a child has at least t keys before you descend into it, borrowing or merging as needed -- so you never have to walk back up. Test that after deleting an interior separator key, an in-order walk is still sorted and len is correct, and that std.testing.allocator reports zero leaks after merges free nodes.Step back and see the two answers side by side. The skip list kept an ordered collection balanced with randomness -- coins, expectation, no guarantees but wonderfully simple code. The B-tree keeps it balanced with a strict structural rule -- half-full nodes, split-on-descent, height bounded by math, balance guaranteed. Both got us O(log n); they just paid for it with different currencies.
Now notice something about that B-tree. Its power came from the fat node -- many keys, high fan-out, short tree. But what if you did the opposite? What if you squeezed the node back down toward a single key, a plain binary node like the humble BST, yet refused to give up the guaranteed balance? You'd have to smuggle the "how full is this node" information somewhere else, since the node no longer has room to hold several keys. The classic trick is to tag each node with a single bit -- think of it as a colour -- and enforce a couple of rules about how those colours may sit relative to each other, rules that turn out to be exactly a B-tree of a particular small degree wearing a binary disguise. When an insertion breaks a rule, you fix it locally with a small rotation and a recolouring rather than a full split. Same guaranteed-balance goal, reached from the binary side in stead of the fat-node side, and the two are provably the same structure viewed through different glass. That equivalence is one of the most satisfying "wait, those are the same thing?" moments in all of data structures, and it's where we go next. One node at a time, we keep climbing.
Bedankt en tot de volgende keer!
@scipio