Log-Structured Merge-Tree (LSM Tree)

What is an LSM-tree?

A Log-Structured Merge-tree is a storage engine optimized for writes. Instead of updating data in place like a B-tree, an LSM-tree buffers writes in an in-memory structure (the memtable), and when it fills, flushes it as an immutable sorted file (an SSTable) to disk. Writes become sequential appends — the fastest thing a disk does — which is why LSM-trees power write-heavy stores: Cassandra, RocksDB, LevelDB, ScyllaDB, and the engines under many time-series and NoSQL databases.

The trade: fast writes, complicated reads

Nothing is free. Because updates never overwrite, a single key can exist in the memtable and several SSTables, so a read may check multiple places — the read amplification LSM-trees fight with Bloom filters (a probabilistic “is this key definitely not here?” that skips most SSTables). Old versions and tombstones (deletion markers) accumulate, so a background process called compaction merges SSTables, discards superseded data, and keeps reads bounded. Compaction is the LSM-tree’s defining operational reality: it’s necessary, it consumes I/O and CPU, and a database falling behind on compaction degrades read latency and bloats disk — the classic Cassandra incident. Write amplification (data rewritten repeatedly during compaction) is the cost paid for the write speed.

LSM-tree vs B-tree — the choice under every database

The fundamental storage-engine fork. B-trees (Postgres, MySQL/InnoDB, most relational stores) update in place — excellent read performance and range scans, but random writes. LSM-trees turn writes sequential — superb write throughput and compression, at the cost of read/space amplification and compaction overhead. The rule of thumb: write-heavy, high-ingest workloads (time-series, logs, event streams, wide-column at scale) favor LSM; read-heavy transactional workloads favor B-trees. Knowing which engine your database uses explains its performance personality.

What people get wrong

• Ignoring compaction tuning — the wrong compaction strategy for your workload is the root of most LSM performance incidents.
• Underestimating space amplification: LSM stores need headroom for compaction; a nearly-full disk is a crisis waiting.
• Expecting B-tree read latency from a write-optimized engine — point reads may touch multiple SSTables.

Primary source: The Log-Structured Merge-Tree (O’Neil et al., 1996)

Why Write-Optimized Databases Choose LSM Trees

Log-Structured Merge (LSM) trees are the storage engine design underlying many databases optimized for high write throughput — Cassandra, RocksDB, and LevelDB among others — because they convert random writes into sequential ones: rather than updating data in place on disk (which requires slower random disk access), writes are first buffered in memory and periodically flushed to disk as new, immutable sorted files, with a background compaction process later merging and cleaning up these files over time. This design trades some read performance (a read might need to check multiple files before finding the most recent version of a value) and background compaction overhead for dramatically better write throughput compared to update-in-place storage structures like B-trees, which is exactly the tradeoff that makes LSM trees the right choice for write-heavy workloads like time-series ingestion, logging, and high-volume event data.