LSM Trees Explained: Why Write-Heavy Databases Use Them

LSM trees explained in one line: a log-structured merge tree is the storage design behind most write-heavy databases, and it makes writes cheap by never updating anything on disk in place. New writes land in a sorted in-memory table. When it fills up, it is written out as a sorted, immutable file, and a background process keeps merging those files together. The result is that every disk write is sequential, which is the thing disks (and SSDs) like best.

That is the whole trick. Everything else in this post is the price of the trick, and how engines try to lower it.

The write path: memtable, log, flush

In an LSM tree, a write is appended to a log and inserted into a sorted in-memory table called the memtable, and then the call returns. When the memtable fills, the engine flushes it to disk as an immutable sorted file. Nothing is read or modified in place, so every disk write is sequential.

Say you PUT user:42 = {...} into RocksDB. Three things happen.

1. The record is appended to a write-ahead log on disk (optional, but you want it).
2. The record is inserted into the memtable, an in-memory sorted structure.
3. The call returns.

That’s it. No page lookup, no random seek. If you’ve read how a write-ahead log makes a database survive crashes, this is the same log doing the same job: if the process dies, the memtable is rebuilt by replaying it.

The RocksDB overview puts the next step plainly: when the memtable fills up, it is flushed to an SST file on storage and the corresponding log file can be safely deleted. SST stands for sorted string table. The file holds keys in order, which is what makes lookups inside it fast and merging two of them cheap.

Updates and deletes follow the same pattern. Overwriting a key writes a new record with the same key. Deleting writes a tombstone, a marker that says “this key is gone.” The old versions sit in older files until compaction gets to them. This surprises people the first time a delete-heavy workload makes the disk grow.

The read path: why it gets harder

Reads are where you pay. The newest value for a key might be in the memtable, or in any of several SST files, and the engine has to find the newest one.

So it checks the memtable first, then files from newest to oldest, and stops at the first hit. A key that doesn’t exist is the worst case, since every file has to say no.

Two things keep this tolerable:

• Bloom filters. Each file carries a small probabilistic filter that can say “definitely not in here” without reading the file. If you haven’t met them, Bloom filters explained covers why a false positive costs one wasted read and a false negative never happens.
• Levels. Files are organized so a key has only a few places to be, which brings us to compaction.

Compaction: the part that bites

Left alone, flushes would pile up thousands of overlapping files and every read would crawl. Compaction merges files, drops overwritten values and tombstones, and keeps the file count bounded.

RocksDB organizes files into levels. Level 0 holds the newest flushes, and, per the RocksDB docs, files in L0 may have overlapping keys, while files in other levels generally form a single sorted run per level. A compaction picks files from one level, merges them with the overlapping files in the next level down, and writes new files.

The two common strategies optimize different things:

Strategy	Optimizes	Costs you
Leveled	Space amplification (less wasted disk)	More rewriting, so higher write amplification
Universal / size-tiered	Write amplification (fewer rewrites)	More disk space used, and more files to check per read

Both descriptions come straight from the RocksDB documentation: level style compaction typically optimizes disk footprint versus logical database size by minimizing the files involved in each compaction step, while universal style optimizes total bytes written by merging potentially many files and levels at once.

I’ll be blunt about the practical consequence. A record you wrote once may be physically written to disk many times over its life. On a busy node, compaction competes with your foreground reads and writes for disk bandwidth, and when it falls behind, the engine throttles writes on purpose (a “write stall”) to avoid drowning. If you run Cassandra or RocksDB in production, compaction lag is a graph you watch.

Three amplifications, pick two to be unhappy about

People summarize LSM tuning as a three-way trade:

• Write amplification: bytes written to disk per byte written by the app.
• Read amplification: files or blocks read per lookup.
• Space amplification: bytes on disk per byte of live data.

You can’t minimize all three. Leveled compaction pushes space and read amplification down and write amplification up. Size-tiered does roughly the opposite. There is no setting that wins everywhere, only a setting that fits your workload.

LSM tree vs B-tree: how to choose

A B-tree, the structure behind most relational indexes (see how B-tree indexes work), updates pages in place. Reads are predictable: a handful of page reads for any key. Writes are random I/O and can fragment pages.

My rule of thumb, which has held up on the systems I’ve worked on:

• Lean toward a B-tree when reads dominate, you want predictable latency on point lookups and range scans, or the dataset is small enough that write speed was never your bottleneck. This is most applications, and it’s why Postgres and MySQL are the sensible defaults.
• Lean toward an LSM engine when ingest is the problem: time-series and metrics, event logs, messaging state, high-churn key-value data, or anything where you’d otherwise be fighting write throughput on a B-tree.

The one place I’d push back on the received wisdom is “LSM is faster.” It’s faster at writing. On a read-heavy workload with a lot of misses, a well-tuned B-tree often wins, and you avoid running a compaction treadmill.

What to check before you adopt one

If you’re evaluating a database that uses an LSM engine underneath, ask these four questions:

1. What compaction strategy is the default, and can you change it per table?
2. How does it behave when compaction falls behind? (Stalls, or unbounded read latency?)
3. How are deletes handled, and how long do tombstones live?
4. What’s the disk headroom guidance? Size-tiered compaction can need substantial free space while it merges.

If the answers are vague, that’s your answer about the operational cost. For data that outgrows a single node, the next question is how you shard it, and LSM engines don’t change that problem, only what each shard does internally.

The takeaway

An LSM tree trades read simplicity and background disk work for fast, sequential writes. Choose it when ingest rate is your actual constraint, pick the compaction style that matches which amplification you can afford, and monitor compaction lag the way you’d monitor replication lag.