Building a B-Tree Storage Engine From Scratch

A database hides three genuinely hard problems behind a friendly API: storing more data than fits in memory, finding a row without scanning everything, and not losing your data when the process dies mid-write. You can read about those problems, but you only really understand them once you've been forced to solve them. Building removes the hand-waving.

A database doesn't read your file one byte at a time. It reads fixed-size blocks called pages. Real engines use 4 to 8 KB, and so does PyDB; the version in the visualizer uses 256-byte pages so you can actually read them. Every tree node and every row lives inside a page, which has a short header and then a run of cells:

leaf page:
  [ roleTag:1 | keyCount:2 | rightSibling:4 | pad:1 ]  header
  [ key:4 | userLen:1 | user… | emailLen:1 | email… ]  cell 0
  [ key:4 | userLen:1 | user… | emailLen:1 | email… ]  cell 1
  … zero padding …

Fixed sizes are what make the rest possible. Page number times page size gives you an exact byte offset, so random access turns into arithmetic instead of a search.

The pager owns those raw bytes. It hands out new pages, writes a node into a page, and reads a page back. It sits on the boundary between typed objects the tree understands and a flat array of bytes. Writing a key is just its four bytes, little-endian:

writeU32(page, offset, key);          // 4 bytes, little-endian
page[p++] = user.length;             // length-prefixed string
for (const b of encode(user)) page[p++] = b;

This is the part most “learn databases” tutorials skip. But decoding those four bytes back into the exact key you wrote is the whole point, and it's literally what the byte grid in the live demo renders.

To find a row fast you need order. A B-Tree (I built a B+Tree, where the values live in the leaves) keeps keys sorted and keeps the tree short, so every leaf sits at the same depth. A lookup is a handful of comparisons no matter how much data you store, because the tree grows wide before it grows tall. Internal nodes hold only separator keys. The leaves hold the data and link left to right, which makes range scans easy.

Push enough keys into a leaf and it overflows. When it does, the leaf splits. Half the keys move to a new page, and the first key of the new page gets copied up to the parent as a separator. If the parent overflows too, it splits and pushes a key up. If that reaches the root, the tree gains a level. That single mechanism is what keeps everything balanced:

if (leaf.keys.length > LEAF_CAP) {
  const right = pager.allocate("leaf");
  right.keys = leaf.keys.splice(mid);          // move the upper half
  return { promoteKey: right.keys[0], right };  // copy up
}

In the demo, hit Insert a few times and watch a leaf fill, split, and eventually trigger a root split that bumps the height. None of that is animation. It's the real algorithm reacting to real state.

Here's the question that separates a toy from a database. What happens if the process dies halfway through a write? The answer is the Write-Ahead Log. Before touching a page you append a record saying what you're about to do. Only then do you change the page. On restart you replay the log. Because the log is written first, you can always recover to a consistent state, and commit records tell you which transactions actually finished:

wal.append({ op: "INSERT", pageId, key });   // 1. log the intent
pager.writeLeaf(pageId, keys, values);       // 2. then apply it
wal.append({ op: "COMMIT", txId });          // 3. mark it done

That ordering is necessary, but it isn't enough on its own. My first version followed it exactly and still lost every committed write when I killed the process, because it replayed the wrong transactions onto a data file that was never made durable. What you replay, and what you replay it onto, matter as much as the order you write in. I wrote that one up separately: my database lost every committed write, and one test found it.

PyDB started in Python. To make it interactive here, I built a TypeScript version on the same ideas, scaled down so you can watch it: 256-byte pages instead of 8 KB, a fanout of four, and deletes and internal-node splits that the Python engine doesn't have. It keeps a write-ahead log too, but it lives in memory, so there's nothing to recover from; the crash-recovery tests live in the Python repo. The nice side effect: the exact module the unit tests drive is the module the page renders. When a test asserts “all leaves stay at equal depth after 500 random inserts,” it's checking the code you're clicking on.

Build the smallest real version first. A B-Tree that only does insert, search, and splits, but does them correctly, teaches you more than a half-built engine with every feature stubbed out. Write the invariant tests early: sorted order, equal leaf depth, log-before-apply. Then write the one that kills the process, because that's the one that tells you whether the word “durable” is true. And serialize to real bytes, not to a convenient object. The bytes are where the understanding actually lives.