Log-Structured Merge Trees

Every database faces the same tension: disks are fastest when they write one long stream but programs want to update individual records scattered across the whole file. A B-tree handles that with in-place updates — but each update can jump to a random location on disk, and random writes are orders of magnitude slower than sequential ones.

Log-Structured Merge Trees (LSM trees), invented by Patrick O'Neil and colleagues in 1996, flip the strategy. Instead of updating data where it lives, every write is appended to an in-memory buffer called the memtable. When the memtable fills up it is sorted and flushed to disk as a compact, immutable file called an SSTable (Sorted String Table). The on-disk files accumulate across levels, and a background process called compaction periodically merges them, discarding obsolete versions and reclaiming space.

The pay-off is dramatic: what was a random write is now a sequential append. The cost is that reads may have to check multiple levels — and that the same bytes may be rewritten several times as they migrate down through the levels, a phenomenon called write amplification.

Modern storage engines — RocksDB, Apache Cassandra, HBase, LevelDB — are all built on LSM trees, making this one of the most consequential data structures of the last three decades.

Type a key and value, press Insert, and watch the entry land in the memtable. When the memtable reaches its capacity the engine automatically flushes it to Level 0 as a sorted run. Press Compact L0 → L1 to merge all Level-0 runs into a single sorted Level-1 file. Then use the Query box to look up any key — the Bloom filter instantly rules out levels that cannot contain it.

<div class="lsm-wrap">
  <div class="insert-row">
    <input id="key-in" type="text" placeholder="{{ph_key}}" maxlength="12" />
    <input id="val-in" type="text" placeholder="{{ph_value}}" maxlength="16" />
    <button id="btn-insert" type="button">{{btn_insert}}</button>
  </div>
  <div class="query-row">
    <input id="q-in" type="text" placeholder="{{ph_query}}" maxlength="12" />
    <button id="btn-query" type="button">{{btn_query}}</button>
    <button id="btn-compact" type="button" class="ghost">{{btn_compact}}</button>
    <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
  </div>
  <div id="msg" class="msg"></div>
  <div class="levels">
    <div class="level-block">
      <div class="level-label">{{label_memtable}} <span class="cap" id="mem-cap"></span></div>
      <div class="run-list" id="mem-list"></div>
    </div>
    <div class="level-block">
      <div class="level-label">{{label_l0}} <span class="note">({{note_unsorted}})</span></div>
      <div class="run-list" id="l0-list"></div>
    </div>
    <div class="level-block">
      <div class="level-label">{{label_l1}} <span class="note">({{note_sorted}})</span></div>
      <div class="run-list" id="l1-list"></div>
    </div>
  </div>
  <div class="legend">
    <span class="chip chip-mem">{{chip_mem}}</span>
    <span class="chip chip-l0">{{chip_l0}}</span>
    <span class="chip chip-l1">{{chip_l1}}</span>
    <span class="chip chip-hit">{{chip_hit}}</span>
    <span class="chip chip-bloom">{{chip_bloom}}</span>
  </div>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #1a2430; margin: 0; font-size: 14px; }
.lsm-wrap { display: flex; flex-direction: column; gap: .65rem; }
.insert-row, .query-row { display: flex; gap: .4rem; flex-wrap: wrap; align-items: center; }
input { flex: 1 1 90px; min-width: 70px; padding: .38rem .55rem; border: 1px solid #b0bec5; border-radius: 6px;
        font: inherit; font-size: 13px; }
button { padding: .38rem .8rem; border-radius: 6px; border: 1px solid #1d3557; background: #1d3557;
         color: #fff; font: 600 13px system-ui, sans-serif; cursor: pointer; white-space: nowrap; }
button.ghost { background: #fff; color: #1d3557; }
.msg { min-height: 1.3em; font-weight: 600; font-size: .88rem; }
.msg.ok { color: #0a7d33; }
.msg.miss { color: #c62828; }
.msg.bloom { color: #e65100; }
.msg.info { color: #1565c0; }
.levels { display: flex; flex-direction: column; gap: .5rem; }
.level-block { border: 1px solid #cdd9e3; border-radius: 8px; padding: .5rem .6rem; background: #f5f8fb; }
.level-label { font-weight: 700; font-size: .8rem; color: #3d5a80; margin-bottom: .3rem; }
.level-label .cap { font-weight: 400; color: #888; }
.level-label .note { font-weight: 400; color: #888; }
.run-list { display: flex; flex-wrap: wrap; gap: .35rem; min-height: 28px; }
.entry { display: inline-flex; align-items: center; gap: 3px; padding: .2rem .5rem;
         border-radius: 5px; font: 600 12px ui-monospace, monospace; border: 1px solid transparent; }
.entry-mem { background: #dbeafe; border-color: #93c5fd; color: #1e3a5f; }
.entry-l0  { background: #ede9fe; border-color: #a78bfa; color: #2d1b69; }
.entry-l1  { background: #d1fae5; border-color: #6ee7b7; color: #064e3b; }
.entry.hit { outline: 2px solid #f59e0b; background: #fef3c7; }
.bloom-badge { font-size: 10px; color: #9a3412; background: #ffedd5;
               border: 1px solid #fed7aa; border-radius: 4px; padding: 1px 4px; margin-left: 2px; }
.run-sep { border-left: 2px dashed #c4b5fd; height: 22px; margin: 0 .1rem; }
.legend { display: flex; flex-wrap: wrap; gap: .3rem; margin-top: .2rem; }
.chip { font-size: 11px; padding: 2px 7px; border-radius: 4px; }
.chip-mem { background: #dbeafe; color: #1e3a5f; }
.chip-l0  { background: #ede9fe; color: #2d1b69; }
.chip-l1  { background: #d1fae5; color: #064e3b; }
.chip-hit { background: #fef3c7; border: 1px solid #f59e0b; color: #78350f; }
.chip-bloom { background: #ffedd5; color: #9a3412; }

// Code not found

Notice how every insert is a fast sequential append, while a query has to probe the Bloom filter for each level before reading the data. The more levels that exist, the higher the read amplification — the price paid for write speed.

LSM trees make three quantities fight each other — and every tuning decision is a negotiation between them:

• Write amplification (WA): the ratio of bytes written to disk to bytes logically written by the application. A compaction that rewrites 10 GB to absorb 1 GB of new data has WA = 10. Tiered compaction minimises WA (around 10–30×) at the cost of more levels to search.
• Read amplification (RA): the number of I/O operations per logical read. In the worst case a point query must probe every level — $O(L)$ SSTables if no Bloom filter is used. Bloom filters reduce most misses to a single hash check per level, bringing average RA close to 1 for point queries. Range queries must still merge sorted iterators from all levels: $O(L \cdot B)$ where B is the block size.
• Space amplification (SA): the ratio of on-disk space to the size of the live data set. Stale versions of overwritten keys accumulate until compaction runs, so SA is typically 1.1–2×. The RUM Conjecture (Idreos et al., 2016) formalises that no structure can minimise all three simultaneously — every design point in the space is a deliberate trade-off.

Levelled vs tiered compaction is the central policy choice:

• Levelled (RocksDB default): each level is a single sorted run; compaction merges a file from level i into the overlapping files at level i+1. SA and RA are low; WA is higher.
• Tiered (Cassandra STCS): multiple sorted runs per level; compaction merges same-size runs. WA is lower; SA and RA are higher.

Bloom filters are the key optimisation for point reads. A standard Bloom filter with k hash functions and m bits per key gives false-positive rate ≈ $\left(\frac{1}{2}\right)^{k \cdot m / \ln 2}$. At 10 bits/key the false-positive rate is under 1 %, meaning almost every absent-key query skips every level in $O(1)$ time.

For more on the general write-vs-read tension see the article on B-trees and dynamic shortest paths, and for the probabilistic data structures that make Bloom filters work see Bloom Filters.

Any workload that writes far more than it reads is a natural fit for LSM trees:

• Social-media event ingestion: platforms like Meta and LinkedIn ingest billions of events per day into RocksDB-backed stores. Every "like" or "view" is a sequential append; analytical queries come later and can afford extra I/O.
• Time-series databases: InfluxDB and Apache IoTDB use LSM-style engines because sensor readings arrive in timestamp order and are rarely updated — a perfect match for sequential writes and append-only semantics.
• Wide-column stores: Cassandra and HBase store each row mutation as a new SSTable entry. Compaction merges the history and discards obsolete versions, keeping disk use bounded.
• Key-value caches and embedded stores: LevelDB (used inside Chrome's IndexedDB) and RocksDB (used in MySQL MyRocks) bring write-optimised storage to embedded scenarios where a full RDBMS is too heavy.
• Write-ahead logs and change-data-capture: the append-only philosophy of LSM trees maps naturally onto write-ahead logs, Kafka topic storage, and CDC pipelines where every mutation is a new record rather than an update.

The common thread is that the application generates data faster than it re-reads it. LSM trees exploit that asymmetry by making the common case — the write — as cheap as physically possible.

Log-Structured Merge Trees solve one of the oldest problems in systems engineering: making a disk fast when an application writes to many different locations. The answer is beautifully simple — never update in place; always append — and the consequences ripple through every layer of the design, from the in-memory memtable to the Bloom-filter-guarded levels to the compaction policies that keep space use bounded.

The RUM Conjecture reminds us that this is not a free lunch: every reduction in write amplification comes at the cost of higher read amplification or more space, and every configuration is an explicit trade-off. Understanding those trade-offs is what separates a well-tuned RocksDB deployment from one that runs out of disk space or slows to a crawl under read pressure.

The next time you insert a record into Cassandra or a RocksDB-backed service, remember: your write never touched the place where the data will eventually live. It landed in a log, was sorted into a file, and will be quietly merged with its neighbours while you have long since moved on.