Pages

From the small database this series builds, one of the six programs the From Scratch build makes from real ones. Follows Database 02: The Index, which turned a lookup into a single byte offset in the file.

Before you start. This series builds a small database of our own: a program that stores rows of data on disk and can find any one of them again on demand. So far it does two things. It writes every new row onto the end of a file, one after another, so nothing already there gets overwritten. And it looks up a row instantly, because a table kept in memory turns a key straight into the exact byte where that row starts, instead of reading the whole file to find it.

The idea in 30 seconds

Nothing under your program moves single bytes; the disk and filesystem move fixed folders, so even the smallest read is billed for a whole one.
A file built the same way is an array of pages, numbered from zero, and a record’s real address is two numbers: a page, and a slot inside it.
The pager turns a page number into an actual read or write, and keeps recently used pages in the buffer pool so a repeat read costs nothing.
A page holds its own directory of slots, so a record can move inside the page, get compacted, without the address pointing at it ever changing.
A slot number is handed out once and never reused, because reusing one turns an old, correct pointer into a wrong answer with no error.
A page can look perfectly valid and still be lying, holding half of a write that lost power partway, which is why the next lesson stops trusting the page to protect itself.

Read the story · Skip to the numbers