Database 01: The Append-Only File

The first board in this database build that writes anything to disk at all. Hands off to Database 02: The Index, which fixes the read, and Pages, which fixes the file.

Before you start. This series builds a small copy of a database: a program whose only job is to remember things you hand it, and hand them back correctly later. You do not need to have built one before. You do need one fact about computers: they have two kinds of storage, one that forgets everything the moment the power goes and one that does not, and this lesson lives entirely in the second kind.

The idea in 30 seconds

A database file that only ever adds lines to the end, never rewrites one, is already correct, if not yet fast.
Reading means walking from the end and stopping at the first line for a key, because the newest line is the truth.
A delete can’t be expressed as removing a line, so it becomes a tombstone: a line that says “gone.”
A crash can only ever damage the last, unfinished line, because every write only ever lands past the end - which is why recovery is a truncate, not a search.
Reads pay for everything ever written, not for what’s still true, which is why the file needs an index next.
Compaction rewrites the file to keep only the newest line per key, using the same never-edit-in-place rule that makes the whole design safe.

Read the story · Skip to the numbers