Database 02: The Index

The address book sitting over last lesson’s file. Follows Database 01: The Append-Only File, which left every read scanning the whole file, and hands off to Pages.

Before you start. This series builds a small database of our own: a program that saves pairs of a key (a name you look something up by) and a value (what’s stored under that name). Ours already saves every change safely, by adding a new line to the end of a file on disk (the disk being the part of the computer that keeps data after the program stops running), so a crash mid-write loses nothing already saved; and it deletes a key by writing a marker over it rather than erasing anything. But asking it “what is the value for this key” has no shortcut yet: it reads the file one byte (one unit of stored data) at a time from the start, checking every line until it finds the answer or runs out of file.

The idea in 30 seconds

An index is a small, separate structure that tells you where something is, never a copy of the thing itself - Dewey’s card, not the book.
Ours maps each key to a byte offset plus a length in the file, so a lookup does one read at a known spot instead of a scan.
The map is a hash map: checking whether a key exists costs about one step regardless of size, and a miss costs zero disk reads.
Nothing writes the index to disk, so every restart rebuilds it by replaying the file once - the old scan, moved to start-up instead of gone.
Every key sits in memory forever, so key count, not value size, is what this design can run out of room for.
A hash map has no order, so it answers “where is this key” but never “what’s near it” - that needs a different index, next.

Read the story · Skip to the numbers