Aliases: LSM Tree
Log-Structured Merge-Tree (LSM Tree)
The write-optimized storage engine behind Cassandra, RocksDB, and most NoSQL — buffer writes in memory, flush to sorted files, compact in the background.
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)
Historical figures and technical concepts for informational purposes only. Not technical, professional, legal, or financial advice. Sources: Official Documentation.