A database write should be simple: put the bytes somewhere durable and return. It should not wander across the disk rearranging pages while the caller waits.
Tree indexes make it wander. Updating a B-tree touches pages scattered through the file. On spinning disks random writes are expensive; on SSDs they are cheaper but still not free, and they wear the device.
The LSM tree starts from the opposite bias: write sequentially now, organize later.
What if the on-disk index were not kept perfectly up to date at every moment?
Writes could accumulate in memory, append to a log for durability, and flush to disk in sorted batches. Reads would consult the newest data first, then progressively older sorted files. Background work would merge those files into cleaner shapes.
That is the bargain: move write cost out of the foreground and repay it in batches.
That structure is the log-structured merge tree. It is not a tree of pointers. It is a pipeline of sorted components: one mutable in-memory level, a set of immutable on-disk files, and background compaction that keeps the pile from growing without bound.
It is why LevelDB, RocksDB, Cassandra, HBase, and Bigtable absorb write streams that would sink a B-tree. They convert random writes into sequential ones, then merge-sort the consequences later.
Patrick O’Neil, Edward Cheng, Dieter Gawlick, and Elizabeth O’Neil published the LSM-tree paper in 1996. Their target was indexed access to files with high insert volume, where conventional access methods spend their time on small random updates.
The premise is a fact about hardware: disks write long runs far more happily than they hop between them. Buffer the updates, merge them in sorted order, and immediate placement can be traded for write throughput.
The tension is between write amplification and read simplicity. One logical update should not require expensive random I/O. A read still has to find the newest value for a key.
Append forever and reads become archaeology. Reorganize on every write and writes become slow. The LSM tree sits between the two: append and flush quickly, then compact in the background so reads do not drown in old files.
A write first enters a write-ahead log, so a crash can replay it. Then it enters an in-memory sorted structure called the memtable — in LevelDB, a skip list.
When the memtable fills, it becomes immutable and is flushed to disk as an SSTable: a sorted string table of key-value entries, plus an index and usually a Bloom filter. Compaction later merges SSTables from newer levels into older, larger ones.
Put key 42 with value “blue.” The database appends the update to the log, inserts it into the memtable, and returns once durability requirements are satisfied.
No disk page is located and rewritten. If key 42 already exists in an older SSTable, the new value simply shadows it. The newest version sits closest to the top of the structure, and compaction removes the stale copy later.
When the memtable reaches its size limit it freezes, and a fresh memtable begins accepting writes. The frozen one is written to disk as a sorted file.
That flush is one sequential pass. The memtable was already sorted, so the file is emitted in key order. Many tiny updates have become one large sorted run.
Reads proceed newest to oldest: the active memtable, then immutable memtables awaiting flush, then the youngest disk level, then older levels.
For a point lookup the first match wins, since newer entries shadow older ones. If a file’s Bloom filter reports the key definitely absent, the read skips that file without touching disk. Without those filters, a lookup would probe far too many sorted runs.
A delete cannot erase every old copy immediately. The key may live in several immutable files, and rewriting them in the foreground would ruin the write path.
So the LSM tree writes a tombstone: a deletion marker carrying a sequence number. Reads treat the tombstone as the newest truth. Later, when compaction can prove the older versions are hidden beneath it, it drops both the tombstone and the values.
Compaction is the repayment. It selects overlapping sorted files, reads them in key order, merge-sorts their entries, discards versions that are safely shadowed, and writes new sorted files into a lower level.
It reduces the number of files a read must consult, reclaims the space held by old versions and tombstones, and keeps levels within their target sizes. It is also where most of the engineering difficulty lives.
Foreground writes are fast because organization is deferred. Background compaction is what makes the deferral sustainable.
When compaction keeps up, the system is fast. When it falls behind, read amplification climbs, disk usage grows, and writes eventually stall because there is nowhere clean to flush. An LSM tree is a scheduling problem wearing a data structure’s clothes.
The knobs are level sizes, file sizes, Bloom filter bits, compression, and compaction policy. Enlarge the memtable and flushes become rarer, but recovery time and memory pressure rise. Increase the fanout between levels and writes get cheaper while reads search more data.
No setting is universally right. Point reads, range scans, write bursts, delete-heavy workloads, SSD behaviour, cache size, and latency targets each pull the knobs a different way.
An LSM tree trades read amplification and compaction work for write throughput.
Against a B-tree it writes more sequentially and absorbs bursts better. In exchange, a read may consult several places, and the same logical data may be rewritten several times on its way down the levels. That exchange rate is the design.
Under leveled compaction, each level has a target size and the files within a deeper level do not overlap. Data descends level by level into progressively larger sorted runs.
Reads benefit: below L0, a key has at most one candidate file per level. The cost is write amplification, because data is rewritten each time it moves down.
Under tiered compaction, several sorted runs accumulate at a level and are merged together in batches.
Write amplification drops, since data is rewritten less often. Reads pay for it by checking more runs. Engines choose leveled, tiered, or a hybrid depending on whether the workload is more sensitive to write cost, read cost, or space.
Every SSTable can carry a compact Bloom filter of the keys it contains. Before searching inside a file, the engine asks the filter whether the key could be present.
A “definitely not” skips the file without a disk read; a “maybe” proceeds to the file index. Since one read may face many immutable files, the filters turn most of those files into cheap no-ops. This is the single largest read optimization in the design.
Range scans are harder. Bloom filters answer point lookups; they say nothing about whether a run holds keys inside a range.
Scanning keys from 100 to 200 needs an iterator over the memtable and one over each candidate SSTable, merged while respecting sequence numbers and tombstones. This is where LSM trees feel less tidy than page-oriented trees, and why scan-heavy workloads sometimes prefer a B-tree.
LevelDB and RocksDB, as embedded key-value engines. Cassandra and HBase, as the storage layer beneath distributed databases. Bigtable, which brought the design to that scale.
The workloads share three properties: writes outnumber reads, data is sorted by key, and background maintenance is acceptable. Append now, merge later, and keep enough metadata that reads can still find the newest truth.
Time becomes layers. New facts land on top. Older facts sink. Compaction is the conveyor belt that turns messy recent history into cleaner older strata.
Reads climb that history from newest to oldest. Writes only ever touch the present. The whole design is a negotiation between now and later, and compaction is where later arrives.
A write-ahead log, a sorted memtable, immutable sorted files, and a background merge. Writes are sequential and cheap. Reads may consult several files, and Bloom filters make most of those consultations free. Compaction pays back the accumulated debt.
Deferring the work is only half the design. The other half is compaction keeping pace — which is why an LSM tree’s hardest problems are scheduling problems, not data structure problems.