Database 07: The Query Layer

The board where the storage engine, for the first time, gets asked a question instead of told exactly where to look.

Before you start. This series builds a small copy of a database: a program that stores rows of data in files on disk and answers questions about them. Six earlier boards got it this far, and each sentence below is one thing it can already do. It has a file it only ever adds to, never edits in place. It has an index, a shortcut that says exactly where one key sits, so it never has to check every row to find it. It groups rows into fixed-size pages, the same size the disk itself reads and writes in. It keeps keys in a tree, in sorted order, instead of a random pile. It writes down what it is about to do before doing it, in a log, so a crash mid-write never loses data. And it can hold more than one version of a row at once, so two readers working at the same moment never see each other’s half-finished changes. What it still cannot do is answer a question typed in as a plain sentence.