Build Your Own Database - From Scratch

The whole build, laid out in the order its own walls forced it.

Boards

Code: teaching/code/from-scratch/database/ - one Go module, go run ./NN-stage. Real files, a real B-tree (verified: 1000 keys, height 6, in-order sorted), real crash recovery, real MVCC snapshots, a tiny SQL planner.

Before you start. This series builds a small copy of a database - a program that keeps rows of data on disk, finds any one of them in an instant, survives the machine dying mid-write, and lets more than one program read and write at once without corrupting each other’s work. It’s the fourth build in the From Scratch track; if you built the small cache or the small message log earlier in it, you already know the shape - start from the plainest file that could work, and add exactly one new mechanism each time it hits a wall it can’t get past on its own.

The idea in 30 seconds

A database is files on disk, plus three things bolted on: something that finds a row fast, something that survives a crash mid-change, and something that keeps readers and writers from corrupting each other.
An append-only file is crash-safe by default, but finding one row means reading all of them.
An index is a second, smaller list mapping a key straight to where its row lives - but disk moves whole pages, not bytes, so a real one (a B-tree) packs rows and keys into pages and stays only a few pages deep even at millions of rows.
A write-ahead log survives a crash by writing the plan down and flushing it before doing the work; a commit marker decides whether recovery finishes a change or throws it away.
A transaction keeps readers and writers apart by never overwriting a row, only adding a new version, so a reader’s snapshot never changes underneath it.

Read the story · Skip to the numbers