I’ve been obsessed with database internals lately 🤓. It started with Alex Petrov’s "Database Internals": one of those books where every page makes you think "wait, THAT’S how it works?!"
But there’s a gap between understanding the theory and really getting it. I could explain what a B-tree does to a 6yo, draw the diagrams and the likes. But could I actually build one? That itch needed scratching.
So I dedicated a bit of my time off coding a B-tree from scratch in Go. About 15 hours total, spread across a few days between coffee, sport, rest and debugging sessions. I definitely didn’t need one for production (PostgreSQL does this infinitely better), but I wanted to really understand what happens when I type CREATE INDEX.
And honestly? It was one of the most fun coding challenges I’ve done in a while.
What’s a B-tree, anyway?
If you’ve used a database, you’ve used a B-tree: they’re the data structure behind most database indexes. The key insight: unlike binary trees where each node has 2 children, B-tree nodes can have many children (determined by the "order"). This makes them perfect for disk storage where reading a block is expensive.
I won’t explain B-trees from scratch here: Alex Petrov’s book does that brilliantly. If you’re not familiar with the basics, start with chapter 2 of Database Internals. This article assumes you know what a B-tree is and focuses on what I learned building one.
The Implementation: Easy, Interesting, and "Wait, What?"
The Easy Part: Search
Binary search within nodes, recurse to children. With good tests, this was maybe 2 hours including edge cases. The satisfying kind of easy where you know exactly what to do.
The Interesting Part: Split
Understanding why nodes split (keep tree balanced) vs how to split them (median, two halves, promote) took some head-scratching. Drawing it out on paper helped.
The surprise: root splits are special. You create a brand new root with just the promoted key. The tree grows taller, not wider.
The "Wait, What?" Part: Cascade
Oh wow. This is where I learned the difference between "I understand B-trees" and "I can build a B-tree."
When a split cascades up, you’re not just inserting a key: you’re managing a whole graph of parent-child relationships. Split an internal node? Better redistribute its children too. And update every child’s parent pointer. Miss one? Silent corruption. The debugging session was ...fun...
The full implementation is on GitLab, but the key insight was: when you split an internal node, you’re not just moving one or two keys: you’re rewiring an entire graph. Get one pointer wrong and your tree silently corrupts. Tests caught this. A lot. And when they didn’t and I had to discover that by myself, I wrote new tests to confirm and made sure I fixed the bug.