Log-Structured Merge Trees: Fast Writes Without Rewriting Pages

Your catalog API is fine until every checkout, inventory tweak, and analytics event lands as a write. Suddenly the database spends more time rearranging pages than accepting new data. Log-structured merge trees (LSM trees) exist for that kind of pressure: they turn many small random updates into sequential appends, then clean up in the background.

After this guide you will know what an LSM tree is, how writes and reads move through memory and sorted files, why compaction exists, how LSM trees compare to B-trees, and when the trade-offs are worth it.

What an LSM tree is

An LSM tree is a way to store key-value data so that writes stay fast on disk or flash. Instead of updating records in place like a classic B-tree page layout, the engine buffers new data in memory, flushes it as immutable sorted files, and later merges those files into larger sorted runs.

Think of a busy bookstore receiving returns and restocks all day. Staff do not rewrite the entire shelf map after every carton. They jot changes in a clipboard (memory), periodically photocopy that clipboard into a dated folder (a sorted file on disk), and once a week merge overlapping folders into one clean catalog (compaction). Lookups check the clipboard first, then the newest folders, then the older merged ones.

That pattern is the heart of LSM design: accept writes quickly, keep data ordered enough to find later, and pay the reorganization cost in batches.

A write walkthrough you can picture

Imagine an orders service that records every line item as a key-value pair: order id plus line number as the key, JSON payload as the value.

PUT  order:1001:1  →  {"sku":"BOOK-42","qty":1}
PUT  order:1001:2  →  {"sku":"MUG-9","qty":2}
DELETE order:1001:2
PUT  order:1001:2  →  {"sku":"MUG-9","qty":1}

In an LSM engine, those operations do not seek to an old page and overwrite bytes. They append into an in-memory structure (often called a memtable) that keeps keys sorted. When the memtable fills, the engine freezes it, writes its contents out as a sorted string table (SSTable or similar immutable file), and opens a fresh memtable for new writes.

Deletes are usually recorded as tombstones – special markers that mean "this key is gone" – rather than punching holes in older files. Compaction later drops the tombstone and any obsolete versions once it is safe to do so.

For durability across crashes, engines typically also append each write to a write-ahead log (WAL) on disk before acknowledging success. On restart, the WAL rebuilds the memtable. After a successful flush to an SSTable, that slice of the WAL can be discarded.

How the pieces fit together

Memtable (hot write buffer)

Incoming puts and deletes land in memory first. Memory is fast and easy to keep sorted (skiplist, red-black tree, or a similar structure). Point lookups for very recent keys often hit here and never touch disk.

Immutable sorted files (SSTables / SST files)

Flushed data lives in files that are append-only and never updated in place. Because keys inside a file are sorted, a lookup can binary-search or use a sparse block index. Multiple files may contain different versions of the same key until compaction resolves them.

Levels

Most production LSM stores arrange files into levels. Level 0 holds fresh flushes and may contain overlapping key ranges. Higher levels hold larger, more sorted runs with less overlap. Newer data sits near the top; older, compacted data sinks downward.

Compaction

Background jobs read overlapping files, merge them in key order, drop obsolete versions and expired tombstones, and write new files into the next level. Compaction is how LSM trees reclaim space and keep reads from checking too many files.

Without compaction, every flush would pile another overlapping file on disk. Reads would get slower, and deleted keys would never truly leave.

Bloom filters and multi-level reads

A point lookup typically:

1. Checks the active memtable (and any frozen memtables waiting to flush)
2. Asks a Bloom filter whether a given SSTable might contain the key
3. Searches Level 0 files that could overlap the key
4. Walks higher levels until it finds the newest visible version – or concludes the key is absent

Bloom filters cut wasted disk reads: if the filter says "definitely not," the engine skips that file. They can produce false positives, so a "maybe" still requires a real lookup, but they never falsely say a key is missing when it is present.

Range scans are harder than point gets because the engine must merge iterators across memtables and several files. Compaction that reduces overlap helps range queries as much as it helps space.

Why writes feel different from a B-tree

In a B-tree (the default index and heap layout in many relational engines), an update often means reading a page, changing it, and writing it back – sometimes splitting nodes and updating parents. Random writes and in-place updates are normal. Reads can be excellent because a single tree walk often reaches the current value.

In an LSM tree, the write path prefers sequential I/O: append to the WAL, insert into the memtable, later flush a whole sorted run. You avoid rewriting old pages for every change. The cost shows up elsewhere:

Neither structure "wins" in every workload. LSM trees shine when write throughput and sequential media behavior matter more than absolute minimum read latency. B-trees often feel better when reads dominate and you want predictable single-tree lookups.

Amplification: the three costs you actually tune

LSM conversations eventually land on three ratios. They are not marketing terms – they are how you explain why a knob change helped or hurt.

Write amplification – How many times a logical write gets rewritten to disk through flushes and compaction. Higher write amp means more disk wear and lower sustained ingest.

Read amplification – How many places the engine may inspect for one logical read (memtables, filters, multiple SSTables). Higher read amp means more CPU and I/O per query.

Space amplification – How much physical storage you use relative to the logical live data. Overlapping versions and pending tombstones inflate the footprint until compaction catches up.

Compaction strategy is a trade among these three. Size-tiered styles may merge similar-sized files and often favor write throughput at the cost of more temporary space and messier overlap. Leveled styles keep higher levels nearly non-overlapping, which usually helps reads and space while rewriting more bytes over time. Universal-style variants try to keep write amplification lower by merging larger sets at once, again trading temporary space and read cost.

You rarely eliminate amplification. You pick which bill you are willing to pay for your traffic shape.

A small mental model in code shape

You will not implement a production LSM in a blog snippet, but this sketch matches the control flow most engines share:

type Entry = { key: string; value: string | null; seq: number };

class TinyLsmSketch {
  private memtable = new Map<string, Entry>();
  private levels: Entry[][] = [[]]; // level 0 = newest flushed runs flattened for demo
  private seq = 0;

  put(key: string, value: string): void {
    this.seq += 1;
    this.memtable.set(key, { key, value, seq: this.seq });
	
    if (this.memtable.size >= 3) {
		this.flush();
	}
  }

  delete(key: string): void {
    this.seq += 1;
    this.memtable.set(key, { key, value: null, seq: this.seq }); // tombstone
  }

  get(key: string): string | undefined {
    const fromMem = this.memtable.get(key);
	
    if (fromMem) {
		return fromMem.value ?? undefined;
	}

    for (const run of this.levels) {
      const hit = [...run].reverse().find((entry) => entry.key === key);

      if (hit) {
		return hit.value ?? undefined;
	  }
    }

    return undefined;
  }

  private flush(): void {
    const run = [...this.memtable.values()].sort((a, b) =>
      a.key.localeCompare(b.key),
    );
	
    this.levels[0] = [...run, ...this.levels[0]];
    this.memtable.clear();
    // Real engines compact across levels; this demo only flushes.
  }
}

What to notice:

• put and delete only touch the memtable (plus a WAL in a real system)
• get prefers newer data: memory first, then newer runs
• value: null stands in for a tombstone
• Flush produces a sorted run instead of mutating old storage in place

Production engines add block indexes, compression, checksums, concurrent compaction threads, snapshots, and careful visibility rules. The sketch is only the shape of the idea.

Mistakes and misconceptions

"LSM means reads are always slow." Not necessarily. Caches, Bloom filters, leveled compaction, and prefix extractors can make point reads very fast. The risk is an untuned store with too many overlapping L0 files and compaction falling behind.

"More memtable is always better." A huge memtable batches more writes, but recovery after a crash can take longer, flush stalls can be larger, and you may delay feedback that compaction needs to keep up.

"Compaction is optional cleanup." It is part of the storage engine's correctness and performance path. If compaction stalls, writes eventually stall too – disks fill, L0 piles up, and read fan-out explodes.

"Tombstones free space immediately." Space returns when compaction drops the tombstone and older versions. Short TTL-heavy workloads can create tombstone storms if compaction and GC settings are wrong.

"One compaction style fits every cluster." Write-heavy ingest, read-heavy serving, and time-series retention each want different level targets and merge policies. Copying another team's config without measuring amplification usually disappoints.

When an LSM tree is a good fit

Reach for an LSM-backed store when:

• Ingest is high and mostly append- or update-heavy (events, messages, IoT samples, write-heavy key-value workloads)
• Storage media rewards sequential writes
• You can tolerate background compaction CPU and temporary space headroom
• Point lookups dominate over wide ad-hoc analytics (or you put analytics elsewhere)

Prefer a B-tree-oriented engine when:

• Read latency must stay tightly predictable with minimal tuning
• Updates are mixed with frequent range scans on the primary store
• You want in-place updates and simpler operational mental models
• Working sets fit well in a buffer pool and write rates are moderate

Many systems mix both worlds: an LSM engine for the hot write path, and columnar or relational stores for reporting.

What to measure once you run one

If you operate an LSM store, watch more than average latency:

• Flush and compaction lag (are background jobs keeping up with ingest?)
• Number and size of L0 files
• Read and write amplification estimates from engine stats
• Disk usage versus logical data size
• Tombstone counts and drop rates
• P99 read latency when compaction is busy

Those signals tell you whether to enlarge memtables, change level multipliers, add compaction throughput, or shed write load – before users feel a cliff.

Further reading

• RocksDB overview – memtable, SST files, WAL, and compaction styles in a widely used LSM engine
• LevelDB implementation notes – the classic small LSM design LevelDB documents in plain detail
• The Log-Structured Merge-Tree (O'Neil et al.) – the original research paper that named the structure