Building a Database: Intro

Every senior engineer you ask will tell you the same thing: do not build a database. It's a tarpit. It's decades of work. Plenty of very smart people have tried to do better than Postgres and not managed it.

They're mostly right. But the last database hasn't been built yet, and working with storage is still more awkward than it should be. We paper over it with ORMs and hope the abstraction holds.

What this series is

We're going to build a small storage engine from scratch. Not a toy: something with real on-disk structure, a real B-tree, a real write path. You should be able to open the file in a hex editor and know what every byte is doing there.

Start here, because everything else (the query planner, the WAL, MVCC) is built on top of how bytes end up on disk.

Below is the page format we'll use for the rest of the series. Drag the slider, insert a row, and watch the page fill from both ends.

Why pages, why slots

A page is the unit of I/O. The disk doesn't care about your rows, it cares about blocks. So we pack variable-length records into fixed-size pages, and track where each one lives with a small slot array that grows down from the header while the data grows up from the floor.

When the two meet, the page is full. That's it. Everything more sophisticated is built on that one rule.

The query has to find the page

Storing bytes is half the job. The other half is answering questions about them quickly. Here's the same query taking two very different paths, a sequential scan and an index seek. Step through it.

Next time: the B-tree that makes the index seek possible. We'll build it node by node and watch it split.