Introduction

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.

Watch It Flush and Merge

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="key (e.g. apple)" maxlength="12" />
    <input id="val-in" type="text" placeholder="value" maxlength="16" />
    <button id="btn-insert" type="button">Insert</button>
  </div>
  <div class="query-row">
    <input id="q-in" type="text" placeholder="query key" maxlength="12" />
    <button id="btn-query" type="button">Query</button>
    <button id="btn-compact" type="button" class="ghost">Compact L0 → L1</button>
    <button id="btn-reset" type="button" class="ghost">Reset</button>
  </div>
  <div id="msg" class="msg"></div>
  <div class="levels">
    <div class="level-block">
      <div class="level-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">Level 0 <span class="note">(unsorted runs)</span></div>
      <div class="run-list" id="l0-list"></div>
    </div>
    <div class="level-block">
      <div class="level-label">Level 1 <span class="note">(single sorted run)</span></div>
      <div class="run-list" id="l1-list"></div>
    </div>
  </div>
  <div class="legend">
    <span class="chip chip-mem">memtable</span>
    <span class="chip chip-l0">L0 run</span>
    <span class="chip chip-l1">L1 (merged)</span>
    <span class="chip chip-hit">query hit</span>
    <span class="chip chip-bloom">Bloom miss</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// ── LSM-tree simulator ────────────────────────────────────────────────────
// Memtable capacity: 4 entries. On flush, entries are sorted and written as
// an immutable SSTable run at Level 0.  Compaction merges all L0 runs into a single sorted Level 1 run (oldest version wins on duplicate keys).
// Bloom filter: each level stores the set of keys it contains; a query first checks the Bloom set — if absent it skips that level (simulated miss).

const MEM_CAP = 4;
let memtable = [];   // [{key,val}]  — insertion order
let l0 = [];         // array of runs; each run = [{key,val}] sorted
let l1 = [];         // single sorted run [{key,val}]
let bloomL0 = [];    // one Set per L0 run
let bloomL1 = new Set();

function setMsg(text, cls) {
  const el = document.getElementById('msg');
  el.textContent = text;
  el.className = 'msg ' + (cls || '');
}

function renderEntry(key, val, level, highlight) {
  const d = document.createElement('span');
  d.className = 'entry entry-' + level + (highlight ? ' hit' : '');
  d.textContent = key + ':' + val;
  return d;
}

function renderBloomBadge() {
  const b = document.createElement('span');
  b.className = 'bloom-badge';
  b.textContent = 'Bloom ✗';
  return b;
}

function render(highlight) {
  // highlight = { key, found } or null
  const memList = document.getElementById('mem-list');
  const l0List  = document.getElementById('l0-list');
  const l1List  = document.getElementById('l1-list');
  const capEl   = document.getElementById('mem-cap');
  memList.innerHTML = ''; l0List.innerHTML = ''; l1List.innerHTML = '';
  capEl.textContent = '(' + memtable.length + '/' + MEM_CAP + ')';

  // Memtable
  memtable.forEach(({key, val}) => {
    const isHit = highlight && highlight.key === key && highlight.level === 'mem';
    memList.appendChild(renderEntry(key, val, 'mem', isHit));
  });

  // L0: newest run first
  for (let i = l0.length - 1; i >= 0; i--) {
    if (i < l0.length - 1) {
      const sep = document.createElement('div'); sep.className = 'run-sep'; l0List.appendChild(sep);
    }
    l0[i].forEach(({key, val}) => {
      const isHit = highlight && highlight.key === key && highlight.level === 'l0' && highlight.runIdx === i;
      const e = renderEntry(key, val, 'l0', isHit);
      l0List.appendChild(e);
    });
  }

  // L1
  l1.forEach(({key, val}) => {
    const isHit = highlight && highlight.key === key && highlight.level === 'l1';
    l1List.appendChild(renderEntry(key, val, 'l1', isHit));
  });
}

function flush() {
  const sorted = [...memtable].sort((a,b) => a.key < b.key ? -1 : 1);
  l0.push(sorted);
  bloomL0.push(new Set(sorted.map(e => e.key)));
  memtable = [];
  setMsg(fmt('Memtable full — flushed %length% entries to L0 as a sorted run.', { length: sorted.length }), 'info');
}

function insert() {
  const k = document.getElementById('key-in').value.trim();
  const v = document.getElementById('val-in').value.trim();
  if (!k || !v) { setMsg('Enter both a key and a value.', 'miss'); return; }
  // Always append to memtable (latest write wins; older versions filtered at read/compaction)
  memtable.push({key: k, val: v});
  document.getElementById('key-in').value = '';
  document.getElementById('val-in').value = '';
  setMsg(fmt('Inserted "%k%" into memtable.', { k: k }), 'info');
  if (memtable.length >= MEM_CAP) flush();
  render(null);
}

function compact() {
  if (l0.length === 0) { setMsg('No L0 runs to compact.', 'info'); return; }
  // Merge all L0 runs + existing L1 into one sorted run.
  // Latest version of each key wins (scan L0 newest-first, then L0 older, then L1).
  const seen = new Set();
  const merged = [];
  // Process: memtable writes > newest L0 run > older L0 runs > L1
  // We want newest-first: iterate l0 newest-first, then l1
  const allRuns = [...l0].reverse().concat([l1]);
  for (const run of allRuns) {
    for (const {key, val} of run) {
      if (!seen.has(key)) { seen.add(key); merged.push({key, val}); }
    }
  }
  merged.sort((a,b) => a.key < b.key ? -1 : 1);
  l1 = merged;
  bloomL1 = new Set(merged.map(e => e.key));
  l0 = []; bloomL0 = [];
  setMsg(fmt('Compacted %length% run(s) into a single sorted L1 (%length2% unique keys).', { length: allRuns.length, length2: merged.length }), 'info');
  render(null);
}

function query() {
  const k = document.getElementById('q-in').value.trim();
  if (!k) { setMsg('Enter a key to query.', 'miss'); return; }
  // Search: memtable first (newest), then L0 newest-first, then L1
  // 1. Memtable scan (no Bloom filter needed)
  for (let i = memtable.length - 1; i >= 0; i--) {
    if (memtable[i].key === k) {
      setMsg(fmt('Found "%k%" = "%val%" in memtable.', { k: k, val: memtable[i].val }), 'ok');
      render({key: k, level: 'mem'});
      document.getElementById('q-in').value = '';
      return;
    }
  }
  // 2. L0 newest-first; Bloom filter checked per run
  let bloomMisses = 0;
  for (let i = l0.length - 1; i >= 0; i--) {
    if (!bloomL0[i].has(k)) { bloomMisses++; continue; } // Bloom says absent
    const e = l0[i].find(x => x.key === k);
    if (e) {
      setMsg(fmt('Found "%k%" = "%val%" in L0 run %i% (%bloomMisses% Bloom miss(es) skipped).', { k: k, val: e.val, i: i, bloomMisses: bloomMisses }), 'ok');
      render({key: k, level: 'l0', runIdx: i});
      document.getElementById('q-in').value = '';
      return;
    }
  }
  // 3. L1 Bloom filter
  if (!bloomL1.has(k)) {
    setMsg(fmt('"%k%" not found — Bloom filter ruled out memtable, all L0 runs, and L1 instantly.', { k: k }), 'bloom');
    render(null);
    document.getElementById('q-in').value = '';
    return;
  }
  const e1 = l1.find(x => x.key === k);
  if (e1) {
    setMsg(fmt('Found "%k%" = "%val%" in L1 (%bloomMisses% Bloom miss(es) in L0).', { k: k, val: e1.val, bloomMisses: bloomMisses }), 'ok');
    render({key: k, level: 'l1'});
    document.getElementById('q-in').value = '';
    return;
  }
  setMsg(fmt('"%k%" not found in any level.', { k: k }), 'miss');
  render(null);
  document.getElementById('q-in').value = '';
}

function reset() {
  memtable = []; l0 = []; l1 = []; bloomL0 = []; bloomL1 = new Set();
  setMsg('Reset — all levels cleared.', 'info');
  render(null);
}

document.getElementById('btn-insert').addEventListener('click', insert);
document.getElementById('btn-query').addEventListener('click', query);
document.getElementById('btn-compact').addEventListener('click', compact);
document.getElementById('btn-reset').addEventListener('click', reset);

// Allow Enter key in inputs
['key-in','val-in'].forEach(id =>
  document.getElementById(id).addEventListener('keydown', e => { if(e.key==='Enter') insert(); }));
document.getElementById('q-in').addEventListener('keydown', e => { if(e.key==='Enter') query(); });

// Seed a few entries so the demo is non-empty on load
const seed = [['apple','red'],['cherry','dark'],['banana','yellow'],['date','sweet'],
              ['elderberry','purple'],['fig','brown']];
seed.forEach(([k,v]) => {
  memtable.push({key:k,val:v});
  if(memtable.length>=MEM_CAP) flush();
});
render(null);
Result
Console

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.

The Real Complexity

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)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⋅B)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 ≈ (12)k⋅m/ln⁡2\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)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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/lsm-trees/Content licensed under CC BY-NC 4.0.