The Log-Structured Merge-Tree (LSM-Tree)

How can a database keep scattered incoming records searchable without paying for a separate disk-page update on every insert? The original LSM-tree batches sorted entries in memory and rolls them into larger disk trees. Read it to understand the merge, its amortized cost, and the read and recovery obligations that remain.

Reading focus: How a separately searchable memory component postpones disk placement without hiding recent entries. How a rolling merge shares page-transfer work across new entries, and why a small memory buffer can erase the advantage. Why component searches, deletion markers, recovery, and historical cost assumptions limit a simple faster-writes claim.

Acta Informatica 1996. Patrick O’Neil, Edward Cheng, Dieter Gawlick, and Elizabeth O’Neil. 32 min read, easy difficulty.