Summary
B-trees update pages in place, so a workload with a high rate of inserts causes many random disk writes. The authors targeted systems such as history tables that ingest records continuously and need an index over them without being limited by random I/O.
The LSM-tree buffers new entries in an in-memory component and merges them into larger components on disk in batches. Merges read and write data sequentially, in a process similar to merge sort. Writes become cheap and sequential, while reads may need to check several components.
This trade-off underpins LevelDB, RocksDB, Cassandra, HBase and many other engines. Modern work on compaction strategies, Bloom filters and write amplification all builds on the structure this paper introduced.