Concepts
LSM-tree versus B-tree (log-structured storage)
Intuition
Imagine a notebook where, instead of looking up the right page in the index every time new information arrives, you quickly jot it down on a scratch sheet on the desk. When the scratch sheet fills up, you copy everything over at once, in order, into the main notebook. Writing becomes much cheaper, because you don't run to a different page for every note. The price is that, to find something, you sometimes need to look in the scratch sheet and also in more than one place in the notebook.
How it works
A B-tree on disk keeps the index up to date in place: each insertion can land on a different page, which requires several disk interactions and a lot of disk-arm movement. The LSM-tree paper (1996) states that, for a history table with constant inserts, maintaining a real-time B-tree index can roughly double the I/O cost of each transaction. The LSM-tree splits the index into components: C0, small and entirely in memory, and C1 on disk, shaped like a B-tree optimized for sequential access (fully packed nodes, neighbors in contiguous blocks). New entries always go to C0; when it approaches its size limit, a background rolling merge takes a contiguous range out of C0 and merges it into C1, block by block, writing the resulting nodes to new locations. This trades many small, random writes for a few large, sequential ones, in the spirit of a merge sort. The design generalizes to a series C0...CK of increasing sizes, and the paper concludes that the total merge I/O rate is minimal, for a fixed C0, when the sizes form a geometric progression. The cost shows up on reads: a lookup consults C0 and then the on-disk components, and deletions are recorded as entries that filter results, so lookup performance is similar to a B-tree's, but with some overhead. More components reduce write cost, but increase merge CPU, buffer memory, and the number of places to check.
In practice
Bigtable adopts this pattern: every write goes first to a commit log and to the memtable (a sorted in-memory buffer); when it fills up, the memtable is written as an immutable SSTable (minor compaction), merging compactions run in the background, and the major one rewrites everything into a single SSTable. Reads operate over the merged view of the memtable and SSTables, with optional Bloom filters to avoid useless disk accesses. Secondary technical sources point out that LevelDB, RocksDB, Cassandra, and HBase follow the same line. Choose log-structured storage when the workload has many writes and few later reads (logs, histories, time series); prefer a B-tree when reads are very frequent, since the LSM-tree brings no advantage in that scenario.
Use it in a design
Practice the cases that rely on this concept in the System Design school.