Build Your Own LSM Tree

The Data Systems board on the two honest ways to put bytes on a disk and find them again. The B-tree is one of them. This build is the other. Head of the LSM series, after the Database build (Build Your Own Database - From Scratch).

Before you start. This series builds a small copy of a storage engine: the part of a database that stores keys and values on disk and finds them again. The Database build made one kind, a B-tree that edits pages in place. This one makes the other kind, which never edits anything: it only appends, sorts in batches, and merges in the background. You need Storage Engines for the two-engine picture and Write-Ahead Log for why a write must reach a log before anything else. Storage Extras: richer indexes, warehouse schemas, column tricks covers Bloom filters and compaction in prose; this build writes them. The lab lsm-vs-btree puts a dial on the trade between the two engines.