What Is an LSM Tree? Log-Structured Merge Trees

A log-structured merge tree, or LSM tree, is a data structure that optimizes for fast writes by buffering them in memory and periodically flushing them to disk as immutable, sorted files, which are then merged together in the background. It’s the structure behind the storage engines of many modern databases — including Cassandra, RocksDB, LevelDB, and parts of ScyllaDB — wherever write throughput matters more than read latency on any single lookup.

The write problem LSM trees solve

A B-tree, the traditional structure behind databases like PostgreSQL’s default indexes, keeps data sorted on disk at all times. Every write finds the right spot in the tree and updates it in place. That’s great for reads — the tree is always ready to be queried — but each write can mean a random-access disk seek to the exact page being modified, and pages get rewritten repeatedly as data changes.

An LSM tree takes the opposite approach: never modify data on disk in place. Instead, writes accumulate in memory, and only get written to disk in large, sequential batches. Sequential writes are dramatically cheaper than random writes on both spinning disks and, to a lesser degree, SSDs, so this trades a bit of read complexity for a large write-throughput win.

How the structure works

An LSM tree has two main parts, working together across memory and disk:

1. Memtable — an in-memory, sorted structure (often a skip list or balanced tree) that holds recent writes. All writes go here first, along with an entry in a write-ahead log on disk so recent writes survive a crash before the memtable itself is flushed.
2. SSTables — Sorted String Tables, immutable files on disk that each hold a sorted run of key-value pairs. When the memtable fills up, it’s flushed to disk as a new SSTable. Because SSTables are immutable, writing one is a single sequential disk operation.

Over time, many small SSTables accumulate. A background process called compaction periodically merges them into fewer, larger sorted files, discarding overwritten or deleted keys along the way. This keeps the number of files a read has to check from growing unbounded, and reclaims space from data that’s since been overwritten.

What reads have to do

The tradeoff shows up on the read side. A key might exist in the memtable, in the most recent SSTable, or in an older one — an LSM tree doesn’t know in advance, so a naive read would have to check the memtable and then every SSTable on disk, newest to oldest, until it finds the key or exhausts every file.

Two techniques keep that manageable:

• Bloom filters — a compact, probabilistic structure attached to each SSTable that can quickly say “this key is definitely not in this file,” letting reads skip files without touching disk. See what a Bloom filter is for how that check works.
• Compaction — by periodically merging SSTables, compaction keeps the number of files a read has to consult from growing indefinitely, at the cost of extra background I/O and CPU.

Range queries and lookups for recently-written keys tend to be fast, since the memtable and newest SSTables are checked first. Lookups for old, rarely-touched keys can be slower, since they may require checking several SSTables before compaction has had a chance to consolidate them.

LSM trees vs B-trees

	LSM tree	B-tree
Write pattern	Sequential, batched	In-place, can be random
Write throughput	High	Moderate
Read path	May check multiple files	Single, direct traversal
Space amplification	Higher until compaction runs	Lower, updated in place
Background overhead	Compaction	None
Common use	Write-heavy workloads, time-series, logs	General-purpose OLTP, read-heavy workloads

Neither structure is strictly better — it depends on the workload’s write-to-read ratio, and many systems, like PostgreSQL versus MySQL storage engines, are built around one or the other.

Where LSM trees show up

LSM trees are the default choice for workloads that write far more than they read individual keys: time-series data, event logs, metrics ingestion, and wide-column stores handling high-volume inserts. They’re a natural fit for OLTP systems that need to absorb bursty write traffic without falling behind, and they pair well with database partitioning and sharding strategies that spread that write load across many nodes.

Compaction is the operational cost that comes with all of this. It consumes background CPU and I/O, and if it falls behind — write volume outpacing compaction throughput — the number of SSTables a read has to check keeps growing, and both read latency and disk usage climb until compaction catches up. Most LSM-based databases expose tuning knobs (compaction strategy, memtable size, flush thresholds) specifically to manage that tradeoff under different workloads.

The takeaway

An LSM tree buys write throughput by never updating data in place: writes land in an in-memory memtable, get flushed to disk as sorted, immutable SSTables, and get merged together later by compaction. Reads pay for that convenience by potentially checking several files, a cost that Bloom filters and regular compaction keep in check. For workloads dominated by writes — logs, metrics, high-ingest event pipelines — that tradeoff is usually the right one; for read-heavy, low-write workloads, a B-tree’s in-place updates are often simpler and faster.