LSM Tree
A Log-Structured Merge-tree (LSM tree) is a write-optimized data structure that batches writes in memory and flushes them sequentially to disk as immutable sorted files, periodically merging (compacting) those files to control read cost…
Definition
A Log-Structured Merge-tree (LSM tree) is a write-optimized data structure that batches writes in memory and flushes them sequentially to disk as immutable sorted files, periodically merging (compacting) those files to control read cost and reclaim space.
Overview
The LSM tree was introduced by Patrick O'Neil and colleagues in a 1996 paper as an alternative to B-trees for workloads dominated by writes. Rather than updating data in place, an LSM tree accepts writes into an in-memory structure called a memtable (typically a skip list or balanced tree), also appending each write to an on-disk write-ahead log for durability. When the memtable reaches a size threshold, it is flushed to disk as an immutable, sorted file often called an SSTable (Sorted String Table). Over time many SSTables accumulate, and a background compaction process merges them, discarding overwritten or deleted keys (tombstones) and keeping the number of files a read must consult bounded. This design trades read amplification and space amplification for dramatically better write throughput, because writes are always sequential appends rather than random-access updates. Reads, however, may need to check the memtable and several SSTables before finding the most recent value for a key, which is why LSM-based systems commonly use Bloom filters to quickly skip SSTables that cannot contain a given key, and maintain sparse indexes into each SSTable to avoid scanning it fully. Compaction strategy — size-tiered versus leveled being the two dominant families — is the central tuning knob: size-tiered compaction favors write throughput at the cost of higher space and read amplification, while leveled compaction bounds space and read costs more tightly at the cost of more compaction I/O. LSM trees underpin most modern write-heavy storage engines: Google's Bigtable and LevelDB, Facebook's RocksDB, Apache Cassandra, HBase, ScyllaDB, and the storage layers of many time-series and log-oriented databases all use LSM trees rather than B-trees. They are especially well suited to workloads with high write volume, sequential or append-mostly ingestion, and where write latency matters more than worst-case read latency, which is why they are the default choice for logging, metrics, event-sourcing, and many NoSQL systems.
Key Concepts
- Writes are buffered in an in-memory memtable before being flushed to disk
- On-disk data is stored as immutable, sorted SSTable files
- Background compaction merges SSTables and removes obsolete/deleted entries
- Bloom filters accelerate reads by skipping SSTables that cannot contain a key
- Write-ahead logging provides durability for data still in the memtable
- Sequential disk writes replace random-access updates, boosting write throughput
- Tunable compaction strategy (size-tiered vs. leveled) trades off write, read, and space amplification
- Naturally supports range scans due to sorted SSTable layout
Use Cases
Frequently Asked Questions
From the Blog
What Is a Decision Tree in Machine Learning
A decision tree predicts by asking a series of yes/no questions about your data, splitting it step by step until it reaches an answer. It is simple, visual, and easy to read.
Read More AI & TechnologyReAct, Chain-of-Thought and Tree of Thoughts Compared
Chain-of-thought adds reasoning tokens, ReAct interleaves reasoning with tool calls, and Tree of Thoughts explores multiple reasoning branches with backtracking. This article compares the three on cost, latency and the problem shapes where each genuinely improves accuracy, and shows how to escalate between them so that easy inputs never pay for the expensive scaffold.
Read More ProgrammingTrees in Programming: A Complete Beginner's Guide
A tree is a hierarchical data structure of nodes linked from a single root. Learn how trees work, key types like binary search trees, and how to traverse them.
Read More AI & TechnologyWhat Is a Random Forest Explained Simply
A Random Forest is a team of decision trees that vote on the answer. Randomness makes each tree different, so their combined prediction is accurate and hard to overfit.
Read More