The Log-Structured Merge-Tree (LSM-Tree)
Random writes into a B-tree are expensive because every insert touches a disk page. The LSM-tree buffers writes in memory, flushes them as sorted runs, and merges runs in the background, trading extra read work and periodic compaction for sequential write throughput.
Key ideas
- Convert random writes into sequential ones by buffering and merging
- Reads may consult several levels, so indexes and filters matter
- Compaction cost is the price paid for cheap writes
Why read it now
RocksDB, Cassandra, and most modern write-heavy stores are LSM-trees. The course's storage-engine module builds one from scratch.
Question to keep in mind
Where does write amplification come from in an LSM-tree, and which knob trades it against read amplification?