LSM 03-04: Table Files and the Sparse Index

The Data Systems board that adds the pieces around the two storage engines, including how a log-structured engine keeps its files findable. This lesson builds the file and the index into it. Part of the LSM series, Build Your Own LSM Tree.

Before you start. This series builds a small copy of a storage engine that never edits a file in place. LSM 01-02: The Memtable and the Log built the sorted memtable and the log that protects it. Both live in memory and a log that only grows. This lesson builds the step the whole design is named for: writing the memtable to disk as a sorted file, and finding a key in that file without reading all of it.