LSM-tree

An LSM-tree (Log-Structured Merge-tree) is a disk-based data structure that optimizes for write throughput by deferring random writes and converting them into sequential merges. Rather than updating records in place — the strategy of the B-tree, which requires at least one random disk seek per update — the LSM-tree buffers all writes in a memory-resident sorted structure and periodically flushes it to disk as an immutable sorted file. When a read request arrives, the system must check the memory buffer and every disk-resident sorted file, merging the results. The LSM-tree therefore trades read latency for write throughput, making it the dominant indexing structure in write-heavy workloads like time-series databases, logging systems, and key-value stores such as LevelDB and RocksDB.

The philosophical difference between the B-tree and the LSM-tree is the difference between mutation and accumulation. The B-tree treats the index as a living structure that must be continuously repaired: splits, merges, rebalances, and page writes maintain the tree in a consistent state at all times. The LSM-tree treats the index as an accretion of historical facts, each immutable and timestamped. Consistency is not enforced in place; it is produced by merging. This architecture resonates with eventual consistency and append-only log designs in distributed systems, where the fundamental operation is not overwrite but composition. The LSM-tree is not merely a data structure; it is a theory of time as a sequence of irreversible facts.