Heads up: posts on this site are drafted by Claude and fact-checked by Codex. Both can still get things wrong — read with care and verify anything load-bearing before relying on it.
why → how

Why LSM trees exist

B-trees write where the key lives. LSM trees refuse to do that — and that refusal is the whole point.

Data intermediate Apr 29, 2026 · updated Aug 25, 2026 · 12 min read
On this page

The picture version

Six pictures for a reader who has never thought about how a database writes to disk. The prose below fills in the seams the pictures skip.

1 · The problem

A firehose of tiny writes, each one landing somewhere different.

one reading per second, for years and another one arriving right now where a sorted-on-disk index wants to put them a different spot every single time Jumping somewhere new to change a few bytes is the slowest thing storage does. and this workload asks for nothing else — which is the shape the whole design answers
A structure that keeps everything in sorted order on disk is ideal for mixed reading and writing, because each key goes roughly where it already lives. For an unrelenting stream of new keys, that same property is the problem: every write is somewhere else.

2 · The move

Stop filing. Everything new goes in one tray.

every write, as it arrives the tray, in memory small, kept in order, and nothing on disk moved a copy also goes straight onto the end of a journal, in case the power cuts Accepting a write no longer means finding its place. It means adding to the end of two things.
New writes land in a small in-memory buffer that keeps them in order, plus an append to a journal so nothing is lost in a crash. Neither of those requires touching the sorted data already on disk, which is what makes accepting a write cheap.

3 · When the tray fills

Staple it into a sorted booklet and put it on the shelf. Never open it again.

the tray, now full already in sorted order write out in one sweep newest bookletolderolder still One continuous sweep of the disk, not a thousand little jumps. And a booklet, once shelved, is never edited — only replaced.
The buffer is already sorted, so flushing it is one long sequential write — the fastest thing storage does. Files on the shelf are immutable, which is what removes the need to ever go back and update in place.

4 · Who pays

The writer got their convenience. The reader gets the bill.

looking up one key the traynewestolderolder found here newest first, because a newer file’s answer wins Every booklet on the shelf is somewhere the key might be hiding. So more booklets means slower reads.
A key can live in the buffer or in any file, so a lookup walks them newest-first until it finds a match. This is the trade in one picture — fast, sequential writes bought with reads that have more places to look.

5 · The night shift

Someone merges the booklets so the shelf never grows without limit.

merged one fatter booklet fewer places for a reader to look superseded values finally dropped but the same data gets rewritten again on the way down The writes you saved in the foreground are partly spent again in the background. and a delete is itself a write — a marker that shadows the old value until a merge removes both
A background process merges files into fewer, larger ones, which is what keeps reads from degrading forever. It is also where the saving is partly repaid: one logical write ends up rewritten several times as it settles, and tuning that merging is famously hard.

6 · Keep this card

The whole thing on one index card.

the design = buffer new writes in memory + flush the buffer as one whole sorted file + merge those files in the background Writes are always sequential, even when the keys arriving are not. that one sentence is the whole reason the design exists, and everything awkward about it follows
Picture to keep: a desk where you never refile anything — new notes land in one tray, a full tray is stapled into a sorted booklet and shelved, and a librarian comes by at night to merge old booklets into fewer, fatter ones. Where it breaks: the reader pays for your convenience, because until the librarian has been, looking something up means checking every booklet on the shelf, newest first.

Why it exists

Your watch records your heart rate roughly once a second and has been doing it for years. Open the fitness app and scroll back to a run last March: the chart draws instantly, even though the thing it’s reading from has swallowed tens of millions of tiny timestamped writes and is still swallowing one right now. That stream — a firehose of small, ever-newer key-value writes that you occasionally need to read a sorted slice out of — is the running example for this post.

A B-tree, the default index in most relational databases, writes a key roughly where that key already lives on disk. That’s ideal for a workload of mixed reads and writes. It’s the wrong shape for a firehose: each insert lands at a different spot in the tree, so the disk head — or the SSD’s flash translation layer — is constantly asked to go somewhere else and update a few bytes. Scattered small writes are far more expensive than sequential ones on every storage device this design targets — dramatically so on a spinning disk, still substantially on flash — and the firehose asks for nothing else.

LSM trees came out of refusing that bargain. The original 1996 paper by O’Neil, Cheng, Gawlick, and O’Neil — The Log-Structured Merge-Tree — was written for spinning disks, where a random seek meant physically moving an arm and waiting for the platter, and streaming the same number of bytes sequentially was cheaper by orders of magnitude. The idea: never update a key in place. Just append. Sort and merge later, in the background, when you can do it sequentially.

That choice is why LevelDB, RocksDB, Cassandra, ScyllaDB, HBase, Bigtable, and a good many time-series databases are LSM-based. It’s also why your Postgres tables are not. Different bargains, different workloads.

Why it matters now

Even on NVMe SSDs, where random I/O is much cheaper than it was in 1996, the LSM bargain still pays off — just for slightly different reasons. SSDs have an internal flash translation layer that dislikes small random writes, because flash can only be erased a whole block at a time, so a small overwrite means reading, modifying and rewriting a much larger region. Sequential appends line up with the erase-block grain instead of fighting it. The technique designed for spinning rust survived the move to flash almost unchanged.

Anything calling itself a “key-value store,” “time-series database,” or “embedded storage engine” plausibly has an LSM at the bottom. If you’ve ever wondered why your Cassandra cluster has a “compaction” knob, why RocksDB stalls under sustained write load, or why deleting a lot of data made a database use more disk — that’s the LSM showing through.

The short answer

LSM tree = in-memory sorted buffer + append-only sorted files on disk + background merge

Picture to keep: a desk where you never refile anything. New notes land in one tray; when the tray is full you staple it into a sorted booklet and put it on the shelf; a librarian comes by at night and merges old booklets into fewer, fatter ones. Like that desk, except the reader pays for your convenience: until the librarian has been, looking something up means checking every booklet on the shelf, newest first.

Writes hit a small in-memory structure (often a sorted skiplist), get journaled to a WAL for crash safety, and when the buffer fills, the whole thing is flushed to disk as one sorted file. Reads check the buffer, then the disk files newest-to-oldest. A background process keeps merging files so reads don’t have to check too many.

The trick: writes are always sequential, even when keys aren’t.

How it works

Build it from the failure, one constraint at a time, with the heart-rate firehose in view.

Naive attempt: just append every write to a log. This is the fastest possible thing a disk can do, and it completely solves the write problem — no seeks, ever. Why it breaks: reading. “What was my heart rate last March?” now means scanning the entire log from the beginning, because nothing is in any order.

Fix: keep the recent writes sorted in RAM. Incoming writes go into a sorted in-memory structure called the memtable — often a skiplist, because it takes concurrent inserts well. Sorting in RAM is cheap and involves no disk at all. Why it breaks: RAM is volatile and finite. A crash loses everything not yet on disk, and the watch has been writing for years.

Fix: a WAL for the crash, a flush for the size. Every write also goes to an append-only log on disk — one sequential append, no seek — purely so the memtable can be rebuilt after a crash. And when the memtable hits a size threshold (tens of MB, typically), it’s frozen and written out as a single immutable file: an SSTable. Writing it is cheap and sequential because the memtable was already sorted. That SSTable’s WAL can then be discarded. This is the whole bargain, and everything below is repair work on it.

Why it breaks: you now have hundreds of SSTables, each sorted internally, none sorted relative to the others. A single key could be in any of them, so a read has to consult files newest-to-oldest until it finds a hit — and a read for a key that doesn’t exist has to check all of them.

Fix: merge them in the background. A background process picks several SSTables, merge-sorts them (sequential reads, one sequential write), and produces fewer, larger files, discarding overwritten and deleted keys on the way. This is compaction, and it’s the piece that makes the whole design viable.

How those files get organised is the main axis along which real LSMs differ. Leveled compaction — LevelDB’s namesake, and RocksDB’s usual default — arranges SSTables into levels where level 0 is freshly flushed, level 1 is roughly 10x bigger, level 2 10x bigger again, and each level below 0 holds files with non-overlapping key ranges. Tiered compaction instead accumulates several similarly-sized files and merges them into one bigger file, doing less rewriting at the cost of more files to check on a read. The rough intuition for a leveled layout is that a point read touches about as many places as there are levels, which grows only logarithmically with your data — treat that as intuition, not a bound; the real cost also depends on how many overlapping files sit in level 0.

flowchart LR
    W[Write] -->|append| WAL[(WAL on disk)]
    W -->|insert| M[Memtable<br/>in-memory skiplist]
    M -->|full: freeze + flush| L0[SSTables · L0]
    L0 -->|compact: merge-sort| L1[SSTables · L1 ~10x]
    L1 -->|compact| L2[SSTables · L2 ~100x]

Every arrow except the WAL append is sequential I/O — that is the entire bargain. The foreground write touches only RAM plus one log append; all the sorting and rewriting happens later, in the background, moving data rightward.

A read for key K does, in order:

  1. Check the memtable.
  2. Check the immutable memtable being flushed, if any.
  3. Check the on-disk files, newest first. In a leveled layout the files below level 0 have non-overlapping ranges, so each of those levels contributes at most one candidate file; level 0 files can overlap each other, so all of them are candidates.

Why step 3 still breaks: a read for a key that isn’t there — a heart-rate sample from a day the watch sat off the charger — walks every candidate file and finds nothing in each. Fix: put a summary in RAM that can rule a file out. Every SSTable ships with a Bloom filter: a few bits per key that answers “definitely not in this file” cheaply enough to skip the disk read entirely.

Now the fitness chart. Scrolling to last March is a range scan, and it’s cheap for a different reason than the point lookup: the data inside each SSTable is already sorted by key, so a time-ordered range is a contiguous run inside each file, and the read merges a handful of sorted runs rather than searching. Bloom filters are no help here — a filter answers “is this exact key present,” not “does this file overlap this range” — so range performance depends on how many files compaction has left to merge across. That’s the same knob again.

The bill arrives as write amplification and read amplification. A single logical write is re-written several times as compaction carries it down the levels — a rough rule of thumb for leveled RocksDB configurations puts this in the 10–30x range, but it swings wildly with workload and settings and no canonical source pins it down, so treat it as an order of magnitude, not a figure. A single logical read can fan out to multiple files. That is the LSM’s deal with the devil: trade background I/O and read complexity for very fast, very sequential foreground writes.

One more seam: deletes are tombstones, which means a delete is itself a write, and the space isn’t reclaimed until compaction reaches the tombstone and every older file still holding that key. Tuning compaction is genuinely hard; the RocksDB tuning guide is famously long. How much of that complexity is essential and how much is accidental is genuinely unsettled — active research on tiered versus leveled compaction suggests the design space is still open.

You started with LSM tree = in-memory sorted buffer + append-only sorted files + background merge. What did this post add? — + the amplification you pay for the merge. The three parts explain why writes are fast. They don’t explain why your Cassandra cluster stalls, why a delete makes the disk grow, or why the same data is written to disk five times. That’s compaction — the background merge isn’t a housekeeping detail bolted onto the design, it is the design’s cost, moved somewhere you don’t have to wait for it.

Check yourself

Before you go — a team stores session data in an LSM store and deletes each session when the user logs out. Disk usage climbs steadily even though the number of live sessions is flat. Where’s the disk going?

Answer

Into the deletes. A delete in an LSM is an append like any other — a tombstone written to the memtable, flushed to an SSTable, holding the position “this key is gone.” Until compaction merges the tombstone with every older SSTable that still contains that key, both the original value and its tombstone occupy disk. A workload that’s half deletes is a workload where compaction is doing double duty, and if it can’t keep up, the garbage accumulates faster than it’s collected. The general lesson worth carrying: in an LSM, nothing you do makes the disk smaller directly. Only compaction does, and compaction is a background process with a rate limit.

And one more — someone proposes moving a read-heavy user-profile table off Postgres and onto RocksDB “because LSMs are faster.” What would you ask them?

Answer

Which direction the amplification runs for their workload. LSMs buy sequential writes by paying read amplification and write amplification; profiles are read constantly and updated rarely, so they’d be paying the LSM’s bill without collecting on it. A B-tree lookup is a handful of page reads to a known location; an LSM lookup may probe several levels, and every one of those probes is work the B-tree didn’t do. “Faster” isn’t a property of a storage engine — it’s a property of a storage engine and a workload together, and the ratio of writes to reads is the first number to ask for.

Going deeper