The LSM Tree

Updating a B-tree may modify pages at several locations in a file. These random writes are expensive on disks and still have latency and write-amplification costs on SSDs.

An LSM tree instead batches updates and writes them sequentially before organizing them in the background.

The on-disk index is not rearranged after every write. Updates accumulate in memory, are appended to a durability log, and are flushed to disk in sorted batches.

Reads check recent data before older files. Background compaction merges the files and limits the number of places a read must inspect.

A log-structured merge tree is not a tree of pointers. It is a pipeline: a mutable in-memory table, immutable sorted files on disk, and compaction jobs that merge those files before they become unmanageable.

LevelDB, RocksDB, Cassandra, HBase, and Bigtable all use this pattern to turn scattered updates into long sequential writes.

Patrick O’Neil, Edward Cheng, Dieter Gawlick, and Elizabeth O’Neil published the LSM-tree paper in 1996. It addressed indexed files with high insertion rates, where conventional indexes perform many small random updates.

Buffering updates and merging them in sorted order converts those updates into longer sequential writes.

Appending updates without reorganization increases the number of files that reads must inspect. Reorganizing after every update increases foreground write latency.

An LSM tree balances these costs by flushing updates quickly and compacting the resulting files in the background.

A write first enters a write-ahead log, which can be replayed after a crash. It then goes into an in-memory sorted structure called the memtable — a skip list in LevelDB.

Once full, the memtable becomes an SSTable: a sorted file of key-value entries with an index and usually a Bloom filter. Compaction gradually folds newer files into older, larger levels.

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 from newer components to older ones: the active memtable, immutable memtables awaiting flush, and then successive disk levels.

For a point lookup, the first matching entry is the current version. If a file’s Bloom filter reports that the key is absent, the engine skips that file without a disk read.

A delete cannot immediately remove every older copy because the key may appear in several immutable files.

The LSM tree writes a tombstone, which is a deletion marker with a sequence number. Reads use the newest entry for the key. Compaction later removes the tombstone and older values when they are no longer visible.

Compaction selects overlapping sorted files, reads their entries in key order, merges them, discards safely hidden versions, and writes new files into a lower level.

This process reduces the number of files involved in reads, reclaims space from old versions and tombstones, and keeps each level within its configured size.

Foreground write performance depends on sufficient background compaction capacity.

If compaction falls behind, reads inspect more files, old versions occupy more disk space, and writes may stall because there is insufficient space for new flushes. Compaction scheduling is therefore a major part of an LSM-tree implementation.

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.

Compared with a B-tree, an LSM tree generally handles write bursts better and performs more sequential I/O. Reads may check several locations, and compaction may rewrite the same data multiple times as it moves between levels.

The design exchanges higher read and compaction costs for greater write throughput.

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.

An SSTable can include a compact Bloom filter for its keys. Before searching the file, the engine checks whether the key may be present.

A negative result skips the file without a disk read, while a positive result proceeds to the file index. This reduces the number of SSTables accessed during point lookups.

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 use LSM trees in embedded key-value engines. Cassandra and HBase use them in distributed storage systems, and Bigtable applies the design at large scale.

The approach is well suited to workloads with frequent writes, key-ordered data, and enough background resources for compaction.

New entries are stored in the memtable and upper levels, while older entries remain in lower levels until compaction processes them.

Reads proceed from newer components to older ones so that the first matching entry is the current value.

The write-ahead log provides durability, the memtable maintains sorted in-memory data, and SSTables store immutable sorted data on disk. Bloom filters reduce unnecessary file reads, while compaction merges files and removes obsolete entries.

Overall performance depends on configuring compaction to keep pace with the write workload.