LSM Trees vs B-Trees

The 30-second version

That one design choice decides almost everything else. Editing in place means scattered little writes all over the disk. Appending new files means big, neat writes at the end, which disks love, so LSM trees can swallow far more writes per second. The price is paid at read time and in background work: a value might be in any of several files, and someone has to keep merging them.

Where you'll meet them

By the end of this topic you'll know how the write path, the read path, Bloom filters and compaction work; you'll have built a tiny LSM tree in Go and JavaScript; and you'll be able to say when to pick which, and what goes wrong with each in production.

Why random writes hurt

Disks read and write whole pages

A disk never writes “one row”. It reads and writes fixed-size blocks called pagesPage (storage)The fixed-size block (often 4–16 KB) a database or OS reads and writes as one unit. Reading one byte means reading its whole page., usually 4–16 KB (Postgres uses 8 KB). To change 100 bytes, the database reads the 8 KB page that holds them, changes the 100 bytes in memory, and later writes the whole 8 KB page back.

Worked example: you update one user's last_seen timestamp, a 100-byte row. The database writes an 8 KB page for it: 80× more bytes than you changed, plus a small record in its log (more on that log in §03). Do that for 10 000 different users per second and the disk is rewriting ~80 MB/s of pages to store ~1 MB/s of actual changes. (Real databases soften this by waiting and writing a page once after several changes, but the shape stays.)

A one-minute B-tree recap

A B-treeB-treeA wide, shallow, always-sorted tree that most databases use for tables and indexes. Each node fills one disk page and holds hundreds of keys, so finding one row among millions takes only 3–4 page reads. keeps keys sorted in a short, wide TreeTree (data structure)Data shaped like an upside-down tree: one root node, each node has zero or more children, and nothing loops back. Nodes with no children are called leaves. Folders and files, HTML elements and React components are trees. of pages. The top page says “keys a–f are down this way, g–o that way…”, and after 3–4 hops you reach the leaf page that holds your key. That makes reads fast and predictable. The full story, with a diagram, is in Database indexes.

The catch is in how a B-tree writes. It updates the leaf page in place, at whatever spot on the disk that page happens to live. Your next update is for a different key, so it lands on a different page, somewhere else. And when a page is full, a Page splitPage splitWhen a B-tree page is full and a new key must go into it, the database splits it into two half-full pages and adds a pointer to the new page in the parent. If the parent is full too, it splits as well. turns one page into two and updates the parent too: even more scattered writes.

Why “scattered” is slow

Sequential and random I/OSequential vs random I/OSequential I/O reads or writes one long run of neighbouring bytes; random I/O touches small pieces scattered all over the disk. Disks (especially spinning ones) are many times faster at sequential I/O. cost very different amounts, and the gap depends on the hardware:

• Spinning disk (HDD). A metal arm must physically move to the right track before each scattered write: a seek of about 5–10 ms. That limits you to roughly 100–200 random page writes per second (~1–2 MB/s), while the same disk can stream ~150–250 MB/s sequentially. A ~100× gap (approximate, varies by drive).
• Solid-state drive (SSD). No arm, so random writes are far faster (see SSD vs HDDSSD vs HDDSolid-state drives read a random block in ~0.1 ms; spinning hard disks need ~5–10 ms because a head must physically move. Both are far slower than RAM (~0.0001 ms).). But flash has a quirk: it writes small pages and can only erase big erase blocksErase block (SSD)SSDs can write small pages (~4–16 KB) but can only erase much bigger blocks (often several MB). To change a page in place, the drive must copy the still-valid pages elsewhere first, so one small write can cause many internal writes. of several MB. Overwriting scattered small pages forces the drive to shuffle data internally, which costs speed and wears the drive out sooner. Large sequential writes avoid most of that. The gap is smaller than on HDD (often a few times, depending on the drive), but it's still there.

The write path: log, memtable, flush

function put(key, value) {
  wal.append({ key, value });          // 1. one sequential append on disk (+ fsync)
  memtable.set(key, value);            // 2. sorted insert in RAM
  if (memtable.size >= LIMIT) flush(); // 3. now and then: write it all out as a new file
}

That's the whole write path. No existing data is read, no file is edited. Let's take the three lines one at a time.

1. The write-ahead log: so a crash loses nothing

The table in memory would vanish in a power cut. So before touching it, the write is appended to a Write-ahead logWrite-ahead log (WAL)An append-only file where a database records each change before applying it. After a crash it replays the log to recover; replicas can follow it to copy changes.: a plain file that only ever grows at the end. Appending is sequential, the fast kind of write from §02. After the append the database calls fsyncfsyncA system call that forces data the OS has buffered in memory to actually be written to the disk. Slow (often milliseconds), but without it a power cut can lose “written” data., which forces the bytes onto the physical disk instead of leaving them in the operating system's memory. Only then does it answer “OK”.

After a crash, the database reads the WAL from the start and redoes every write in it. (Durability and WALs in general are covered in Transactions; here we only need “append first, so we can replay”.)

2. The memtable: a sorted table in RAM

Next, the write goes into the MemtableMemtableThe in-memory, always-sorted table where an LSM tree puts every new write. When it reaches a size limit (often 64 MB) it is frozen and written to disk as one SSTable., which keeps keys in sorted order at all times. Inserting into memory takes well under a microsecond, so it's never the slow part. Most engines build the memtable as a Skip listSkip listA sorted linked list with extra “express lane” links that skip over many nodes, so finding or inserting a key takes about log(n) steps — like a balanced tree, but simpler to make safe for concurrent writers. Most memtables are skip lists., a sorted structure that's easy to make safe for many writers at once; a balanced tree or a sorted map works too.

Why sorted? So that step 3 can write it to disk already in order, front to back, with no extra work.

3. Flush: the memtable becomes a file

When the memtable reaches its size limit (RocksDB's default is 64 MB), the engine freezes it (it becomes ImmutableImmutableCan't be changed after it's created. To “change” an immutable value you make a new one. Immutable objects can be shared freely, because nobody can modify them under you.), starts a fresh empty memtable for new writes, and a background thread writes the frozen one to disk as a new SSTableSSTable (sorted string table)An immutable file of key–value pairs sorted by key, plus a small index so a lookup can jump to the right spot. An LSM tree is made of many of them. Once written, an SSTable is never changed, only replaced.: a sorted, never-to-be-changed file. Once that file is safely on disk, the WAL records it covered are no longer needed and get deleted.

Freshly flushed files form level 0 (L0). §06 explains what happens to them next.

Updates and deletes are just more writes

• Update = put the same key again. The new version goes into the memtable; the old version stays in whatever older file it's in. Reads will simply prefer the newest one (§04).
• Delete = write a TombstoneTombstoneA marker meaning “this key was deleted”, left in place of actually erasing it. An LSM tree writes one because it can't edit its immutable files (compaction removes both later); an open-addressing hash table leaves one in the slot so lookups for later keys keep probing past it., a marker that says “this key is deleted”. The old value can't be erased because files are never edited, so the tombstone hides it instead. Try delete(dog) above: the ☠ entry travels through the WAL and memtable into an SSTable like any other write.

SSTables and the read path

(One detail from §03: while a frozen memtable is still being flushed, reads check it too, right after the active memtable and before any file.)

Inside an SSTable

An SSTableSSTable (sorted string table)An immutable file of key–value pairs sorted by key, plus a small index so a lookup can jump to the right spot. An LSM tree is made of many of them. Once written, an SSTable is never changed, only replaced. isn't one big list you scan from the top. Its sorted records are packed into small data blocks of about 4 KB, and the end of the file holds a Block indexBlock index (SSTable)A small table at the end of an SSTable listing the first key of every data block (~4 KB each) and where that block starts in the file. A lookup binary-searches it to find the one block that could hold the key. listing the first key of each block. To look up a key, the engine does a Binary searchBinary searchFinding a value in a sorted list by checking the middle, then throwing away the half it can't be in, again and again. 1,000,000 items need only about 20 checks. on that index to pick the one block that could hold it, then reads just that block.

The index and the Bloom filter (§05) are small (well under 1% of the file), so engines keep them in a Block cacheBlock cacheMemory the storage engine reserves for recently read SSTable blocks (data, index and Bloom filter blocks), so hot data doesn't need a disk read. in RAM. Then checking one file costs at most one disk read. Each file also records its smallest and largest key, so a key outside that range skips the file for free.

Walking the read path

1function get(key) {
2  const m = memtable.get(key);         // 1. newest data first
3  if (m) return m.deleted ? null : m.value;
4  for (const t of sstables) {          // 2. newest file → oldest
5    if (key < t.minKey || key > t.maxKey) continue; // can't be here
6    const block = t.index.search(key); // binary search, in memory
7    const e = block.find(key);         // read ONE block from disk
8    if (e) return e.deleted ? null : e.value;
9  }
10  return null;                         // in no file at all
11}

Why newest → oldest? Because the same key can live in several places: an old value in an old file, a newer value or a tombstone in a newer file. The newest one is the truth. Inside the engine every write also gets a Sequence numberSequence numberA counter the storage engine stamps on every write (1, 2, 3, …). When two records have the same key, the one with the higher number is newer and wins. (1, 2, 3…). When two entries for the same key meet in one place (say, two overlapping L0 files, or during a merge), the one with the higher sequence number is newer and wins.

Try it yourself

Here's the write-path simulator again, now with get and a crash button. Fill a couple of files, put cat again, delete dog, then use get and watch the numbered badges show the order in which places were checked. Then crash: the memtable vanishes, and restart rebuilds it from the WAL.

The cost: read amplification

Every file that might hold the key costs a disk read. That's read amplificationRead amplificationHow much work one lookup costs: how many files or disk pages must be checked to answer one read. One page read = read amplification of 1.: how many reads one lookup really takes.

Worked example: 20 SSTables whose key ranges all overlap. Looking up a key that doesn't exist means checking all 20, so up to 20 disk reads, ≈ 2 ms on an SSD at ~0.1 ms each. A B-tree answers the same question with about one read. Missing keys are the worst case, and they're common: “does this username exist yet?” is usually a no.

Two fixes, and both are essential parts of every real LSM engine: Bloom filters let a read skip files that definitely don't hold the key (§05), and compaction keeps the number of files small (§06).

Bloom filters: skipping files for free

If the answer is “definitely not”, the read skips that file. Only “maybe” costs a disk read. That turns §04's worst case, one read per file, into about one read in total.

How it works

1. Start with m bits, all 0.
2. Pick k hash functionsHash function (for lookups)A function that turns a key like "cat" into a number that looks random but is always the same for the same key — e.g. "cat" → 108 289 031 with the common FNV-1a hash. Taking the remainder after dividing by the number of slots (for a Bloom filter: the number of bits) picks a position.. Each turns a key into a bit position, always the same position for the same key.
3. Add a key: set its k bits to 1.
4. Check a key: compute its k positions. Any 0 → definitely not added. All 1 → maybe.

Worked example with m = 24 and k = 2: cat hashes to bits 23 and 16, dog to bits 1 and 0. Add both, and bits 0, 1, 16 and 23 are set. Check ant (bits 22 and 19): both 0, so ant is definitely not there. Check hen (bits 0 and 23): both happen to be set already, by dog and cat. The filter says maybe, yet hen was never added. That's a False positiveFalse positiveA test saying “yes” when the true answer is “no”. For a Bloom filter: it says “maybe here” for a key that was never added, so the database reads a file for nothing.. Try it:

Things to notice while you play:

• A Bloom filter never says “no” to a key that's there: adding only ever sets bits to 1, so an added key's bits are always all 1.
• More keys in the same bits → more 1s → more false positives. Give it more bits per key and the rate drops fast.
• Too few hash functions and each key leaves too faint a mark; too many and the array fills with 1s. The best k is about 0.7 × (bits per key).

In code

// FNV-1a: a simple, fast hash. Math.imul multiplies as 32-bit integers.
function fnv1a(s, seed = 0x811c9dc5) {
  let h = seed;
  for (let i = 0; i < s.length; i++) {
    h ^= s.charCodeAt(i);
    h = Math.imul(h, 16777619) >>> 0; // >>> 0 keeps it an unsigned 32-bit number
  }
  return h;
}

class BloomFilter {
  constructor(m, k) {
    this.m = m;                    // number of bits
    this.k = k;                    // number of hash functions
    this.bits = new Uint8Array(m); // all 0 to start
  }
  #positions(key) {                // k positions from 2 hashes: h1 + i·h2
    const h1 = fnv1a(key), h2 = fnv1a(key, 0x9747b28c) | 1;
    return Array.from({ length: this.k }, (_, i) => ((h1 + Math.imul(i, h2)) >>> 0) % this.m);
  }
  add(key) {
    for (const p of this.#positions(key)) this.bits[p] = 1;
  }
  mayContain(key) {                // false = definitely not; true = maybe
    return this.#positions(key).every((p) => this.bits[p] === 1);
  }
}

const f = new BloomFilter(24, 2);
f.add("cat");
f.add("dog");
console.log(f.mayContain("cat"), f.mayContain("ant"), f.mayContain("hen"));
// true false true   ← "hen" is a false positive

The key idea in #positions/positions is a standard trick: instead of k separate hash functions, compute two hashes and combine them as h1 + i·h2 for i = 0…k−1. It works as well as k independent hashes in practice.

How many bits?

With the best k, the false-positive rate is roughly 0.62 ^ (bits per key):

10 bits per key is the classic default (LevelDB and RocksDB examples use it). With it, a lookup across 20 files expects 1 real read plus 20 × 1% = 0.2 wasted reads, instead of up to 20.

Here's the LSM simulator with Bloom filters switched on. Each file gets a deliberately tiny 16-bit filter (the strip under each file), so you'll see some false positives (“bloom lied”) along with the skips:

Compaction: merging files in the background

Without it, an LSM tree slowly falls apart. Every flush adds a file, so reads check more and more files (§04). Every overwritten value and every deleted one still takes up disk space. Compaction fixes both, in the background, while reads and writes carry on.

Merging two sorted files

Because every SSTable is already sorted, merging needs no sorting at all: walk all inputs front to back at the same time, always writing out the smallest key next. That's a K-way mergeK-way mergeCombining several already-sorted lists into one sorted list by repeatedly taking the smallest front item among them. Each list is read once, front to back — sequential I/O.. It reads every input once and writes the output once, all sequentially, the kind of disk work §02 said is cheap.

1function merge(older, newer, isBottomLevel) {
2  const out = []; let a = 0, b = 0;
3  const emit = (e) => { if (!(isBottomLevel && e.deleted)) out.push(e); };
4  while (a < older.length || b < newer.length) {
5    const x = older[a], y = newer[b];
6    if (!y || (x && x.key < y.key)) { emit(x); a++; } // key only in older
7    else if (!x || y.key < x.key)   { emit(y); b++; } // key only in newer
8    else { emit(y); a++; b++; }  // same key: newer wins, older is dropped
9  }
10  return out; // one sorted file, written front to back
11}

Which files to merge? Two classic strategies

Merging everything every time would be far too much work. Real engines choose a few files at a time, and the rule they use to choose is the compaction strategy.

Size-tieredSize-tiered compactionA compaction strategy that waits until there are several SSTables of about the same size, then merges them into one bigger file. Cheap on writes; reads may check many files and big merges need lots of free disk space. (the long-time default in CassandraCassandraA distributed database built for huge write volumes spread across many machines. Data is grouped by a partition key and sorted within each partition, which suits “latest messages in this chat” queries. Internally it stores data in LSM trees.; also ScyllaDB): wait until there are about 4 files of similar size, then merge them into one file about 4× bigger. Those pile up until there are 4 of them, which merge into one 16× file, and so on.

• ✓ Each byte gets rewritten only once per size tier, so little write work: low write amplificationWrite amplificationWhen one logical write causes many physical writes. Inserting one row into a table with 6 indexes writes the row plus 6 index entries, each possibly splitting a page. (bytes the disk writes ÷ bytes you asked it to write; §07 digs in).
• ✗ At any moment there may be many files of different sizes whose key ranges overlap, so reads may check many files.
• ✗ Merging the biggest tier needs as much free disk space again as those files take, so plan for ~2× disk space at worst.

LeveledLeveled compactionA compaction strategy that keeps each level a fixed size (each ~10× the one above) with non-overlapping files, pushing data down level by level. Fast reads and little wasted space; costs more disk writes. (LevelDB, and RocksDBRocksDBAn embeddable key-value storage engine (a library, not a server) built on an LSM tree; used inside many databases.'s default): files are arranged in levelsLevel (L0, L1, …)In a leveled LSM tree, SSTables are grouped in levels. L0 holds fresh flushes (their key ranges may overlap); each deeper level is ~10× bigger and its files never overlap, so a lookup checks at most one file per level.. L0 holds fresh flushes. Every level below has a size limit about 10× bigger than the one above (in RocksDB with static level sizing: L1 ≈ 256 MB, L2 ≈ 2.5 GB, L3 ≈ 25 GB…; recent versions size levels from the bottom up instead, see §11), and within one level the files' key ranges never overlap.

When a level grows past its limit, the engine picks one of its files and merges it into the overlapping files of the next level down, replacing them.

• ✓ A lookup checks the L0 files plus at most one file per level: fast, predictable reads.
• ✓ Almost all data sits in the last level and old versions get cleaned up quickly, so wasted space is only ~10%.
• ✗ One file from level N can overlap up to ~10 files in level N+1, so pushing it down rewrites up to ~10× its size (about half that on average). Repeat for every level, and each byte is rewritten many times on its way to the bottom: roughly 5–10 times per level.

Watch them work

Press “flush ×10” a few times under each strategy and compare the write amp and the most files a read ever had to check. (The current file count jumps up and down as merges happen, so look at the maximum.) Size-tiered keeps write amp low but lets the file count climb higher between merges. Leveled keeps it low by rewriting data more often. Neither is free. You're choosing which cost to pay, and §07 puts numbers on it.

Compaction debt

Compaction has to keep up with the incoming writes. If writes arrive faster than compaction can merge, unmerged files pile up. That backlog is called Compaction debtCompaction debtThe amount of merging an LSM tree still owes: files that have been flushed but not yet compacted. If it keeps growing, reads get slower and eventually writes stall.. Reads slow down as it grows, and eventually the engine has to slow down or pause writes until compaction catches up: a Write stallWrite stallWhen compaction falls too far behind (too many files piled up), the storage engine deliberately slows down or pauses new writes so compaction can catch up.. §11 shows how that looks in production and how to avoid it.

The amplification triangle

The three amplifications

Where does a write amp of ~20 actually come from? Follow one record:

Researchers call this the RUM conjecture (Read, Update, Memory): a design can be very good at two of the three, but not all three at once. B-trees, size-tiered and leveled LSM trees are three different points in that triangle.

Rough numbers

These are ballpark figures for typical setups, not measurements. Real values depend heavily on the workload, cache size and tuning.

Notice that the B-tree's write amp depends on the access pattern. Rewriting an 8 KB page to change 100 bytes is expensive, but if many updates hit the same page before it's written, they share the cost. LSM trees are less sensitive to that: they always write in big sequential chunks, but they rewrite the data several times over.

Play with the trade-off

Things to try:

• Size ratio up (say 4 → 20): leveled gets fewer levels but rewrites more per level, so its write amp climbs. Size-tiered gets fewer tiers but more files waiting in each one, so its read amp climbs.
• Bloom bits to 0: LSM read amp jumps to “one read per file”. That's why no serious LSM engine runs without filters.
• More data: one more level or tier for every ~10× growth. Write amp grows slowly (with the logarithm of the data size), not linearly.
• B-tree row size down to 64 B: the worst case for in-place updates explodes, because each tiny change can mean a full page write.

Why write amp matters even on fast SSDs

Disk bandwidth is shared. Compaction writes compete with your reads and writes for the same disk. With a write amp of 20, an app writing 50 MB/s keeps the disk busy writing 1 GB/s.

SSDs wear out. Flash cells survive a limited number of writes. A typical 3.84 TB data-center SSD is rated for roughly 7 000 TB written over its life (approximate; check your drive's spec sheet). An app writing 10 MB/s with write amp 20 puts 200 MB/s on the drive, about 17 TB per day: ~1 year of life. With write amp 5, about 4 years.

Build a toy LSM tree in Go and JavaScript

Each piece maps to a section you've already read:

To keep it short, the memtable is a plain map that's sorted at flush time, and each “SSTable” is a text file with one JSONJSONJavaScript Object Notation: a text format for data — {"id": 7, "tags": ["a"]}. Readable by humans and every language; the default body format for web APIs. object per line (.jsonl), so you can open it and look. Real engines use binary files with a block index and a Bloom filter, but the logic is the same.

package main

import (
	"bufio"
	"encoding/json"
	"fmt"
	"os"
	"path/filepath"
	"slices"
)

// entry is one record. Deleted == true makes it a tombstone.
type entry struct {
	Key     string `json:"k"`
	Value   string `json:"v,omitempty"`
	Deleted bool   `json:"del,omitempty"`
}

type LSM struct {
	dir    string
	limit  int              // flush when the memtable holds this many keys
	mem    map[string]entry // memtable (real engines use a sorted skip list)
	wal    *os.File
	tables []string // SSTable file names, oldest first
	seq    int      // number for the next SSTable file
}

func Open(dir string, limit int) (*LSM, error) {
	if err := os.MkdirAll(dir, 0o755); err != nil {
		return nil, err
	}
	db := &LSM{dir: dir, limit: limit, mem: map[string]entry{}}
	db.tables, _ = filepath.Glob(filepath.Join(dir, "sst-*.jsonl")) // sorted by name = by age
	if n := len(db.tables); n > 0 {
		fmt.Sscanf(filepath.Base(db.tables[n-1]), "sst-%d.jsonl", &db.seq)
	}
	walPath := filepath.Join(dir, "wal.jsonl")
	for _, e := range readLines(walPath) { // crash recovery: replay the WAL
		db.mem[e.Key] = e
	}
	wal, err := os.OpenFile(walPath, os.O_CREATE|os.O_APPEND|os.O_WRONLY, 0o644)
	if err != nil {
		return nil, err
	}
	db.wal = wal
	return db, nil
}

func (db *LSM) Put(k, v string) error { return db.write(entry{Key: k, Value: v}) }
func (db *LSM) Delete(k string) error { return db.write(entry{Key: k, Deleted: true}) }

func (db *LSM) write(e entry) error {
	line, _ := json.Marshal(e)
	if _, err := db.wal.Write(append(line, '\n')); err != nil { // 1. append to the WAL
		return err
	}
	if err := db.wal.Sync(); err != nil { // fsync: now it survives a crash
		return err
	}
	db.mem[e.Key] = e // 2. update the memtable
	if len(db.mem) >= db.limit {
		return db.flush()
	}
	return nil
}

func (db *LSM) flush() error {
	db.seq++
	name := filepath.Join(db.dir, fmt.Sprintf("sst-%04d.jsonl", db.seq))
	if err := writeSorted(name, db.mem); err != nil {
		return err
	}
	db.tables = append(db.tables, name)
	db.mem = map[string]entry{}
	return db.wal.Truncate(0) // everything in the WAL is now safe in an SSTable
}

func (db *LSM) Get(k string) (string, bool) {
	if e, ok := db.mem[k]; ok { // 1. memtable: the newest data
		return e.Value, !e.Deleted
	}
	for i := len(db.tables) - 1; i >= 0; i-- { // 2. SSTables, newest first
		for _, e := range readLines(db.tables[i]) { // (a real one binary-searches)
			if e.Key == k {
				return e.Value, !e.Deleted // a tombstone means "deleted": stop here
			}
		}
	}
	return "", false
}

// Compact merges every SSTable into one. Newer versions win; tombstones are dropped
// because no older file is left that they would need to hide.
func (db *LSM) Compact() error {
	merged := map[string]entry{}
	for _, t := range db.tables { // oldest → newest, so newer entries overwrite older
		for _, e := range readLines(t) {
			merged[e.Key] = e
		}
	}
	for k, e := range merged {
		if e.Deleted {
			delete(merged, k)
		}
	}
	db.seq++
	name := filepath.Join(db.dir, fmt.Sprintf("sst-%04d.jsonl", db.seq))
	if err := writeSorted(name, merged); err != nil {
		return err
	}
	for _, t := range db.tables {
		os.Remove(t)
	}
	db.tables = []string{name}
	return nil
}

// writeSorted writes entries as one JSON object per line, sorted by key.
func writeSorted(name string, m map[string]entry) error {
	keys := make([]string, 0, len(m))
	for k := range m {
		keys = append(keys, k)
	}
	slices.Sort(keys) // ← the "S" in SSTable: sorted
	tmp := name + ".tmp"
	f, err := os.Create(tmp)
	if err != nil {
		return err
	}
	defer f.Close() // safety net for the early returns below
	for _, k := range keys {
		line, _ := json.Marshal(m[k])
		if _, err := f.Write(append(line, '\n')); err != nil {
			return err // e.g. disk full: never rename a half-written file
		}
	}
	if err := f.Sync(); err != nil {
		return err
	}
	if err := f.Close(); err != nil {
		return err
	}
	return os.Rename(tmp, name) // appears all at once: never half-written
}

func readLines(name string) []entry {
	f, err := os.Open(name)
	if err != nil {
		return nil // no file yet = no entries
	}
	defer f.Close()
	var out []entry
	sc := bufio.NewScanner(f)
	for sc.Scan() {
		var e entry
		if json.Unmarshal(sc.Bytes(), &e) == nil {
			out = append(out, e)
		}
	}
	if err := sc.Err(); err != nil { // e.g. a line longer than 64 KB
		panic(err) // a toy shortcut: real code would return the error
	}
	return out
}

func main() {
	os.RemoveAll("data")     // start fresh (errors ignored below to keep the demo short)
	db, _ := Open("data", 3) // flush after 3 keys
	db.Put("cat", "meow")
	db.Put("dog", "woof")
	db.Put("ant", "tiny") // 3rd key → flush to sst-0001
	db.Put("cat", "purr") // a newer version of cat
	db.Delete("dog")      // a tombstone
	db.Put("eel", "zap")  // flush to sst-0002
	db.Put("fox", "yip")  // stays in the memtable (and the WAL)

	show(db)
	for _, k := range []string{"cat", "dog", "fox", "owl"} {
		v, ok := db.Get(k)
		fmt.Printf("get %s → %q found=%v\n", k, v, ok)
	}

	// Simulate a crash: forget everything in memory and reopen from disk.
	db.wal.Close() // a real crash would close it for us
	db, _ = Open("data", 3)
	v, ok := db.Get("fox")
	fmt.Printf("after restart: get fox → %q found=%v\n", v, ok)

	db.Compact()
	show(db)
}

// show prints every SSTable file, line by line.
func show(db *LSM) {
	for _, t := range db.tables {
		data, _ := os.ReadFile(t)
		fmt.Printf("%s:\n%s", filepath.Base(t), data)
	}
}

Run it (for Go: in an empty folder, go mod init toy, save the file as main.go, then go run .; for Node: node lsm.mjs). The Go version prints this; the Node version prints the same files and answers, written as get cat → purr and get dog → undefined:

sst-0001.jsonl:
{"k":"ant","v":"tiny"}
{"k":"cat","v":"meow"}
{"k":"dog","v":"woof"}
sst-0002.jsonl:
{"k":"cat","v":"purr"}
{"k":"dog","del":true}
{"k":"eel","v":"zap"}
get cat → "purr" found=true
get dog → "" found=false
get fox → "yip" found=true
get owl → "" found=false
after restart: get fox → "yip" found=true
sst-0003.jsonl:
{"k":"ant","v":"tiny"}
{"k":"cat","v":"purr"}
{"k":"eel","v":"zap"}

Read the output against the code:

1. Flush #1 wrote ant, cat, dog, sorted, even though they were inserted as cat, dog, ant.
2. Flush #2 holds the newer cat=purr and a tombstone for dog. The old cat=meow and dog=woof are still sitting in sst-0001, untouched.
3. get cat found purr because it checked the newer file first. get dog hit the tombstone and stopped: not found.
4. fox was never flushed. After the “crash” (a fresh Open that knows nothing in memory), the WAL replay brought it back.
5. Compaction merged both files into sst-0003: meow and woof are gone, and so is the tombstone. That's safe here because we merged every file, so nothing older is left for it to hide.

Who uses what

Many of these are embedded storage enginesEmbedded database / storage engineA database that runs as a library inside your own program, with no separate server to connect to. RocksDB, LevelDB, SQLite and bbolt are examples; bigger databases are often built on top of one.: libraries that store keys and values on one machine, inside your program. Full databases are built on top of them. Your app rarely talks to RocksDB directly, but the database you talk to may well be using it.

The LSM family

Several time-series and analytics databases use the same idea under different names. ClickHouse's MergeTree writes sorted “parts” and merges them in the background. Older InfluxDB versions had a Time-Structured Merge tree. VictoriaMetrics merges sorted parts too.

The B-tree family

Choosing: LSM or B-tree?

In practice you rarely choose a data structure directly. You choose a database, and the structure comes with it. Knowing what's underneath tells you how that database will behave under your workload.

Workload → choice

HDD vs SSD changes the gap

On spinning disks, random writes are ~100× slower than sequential ones (§02), so an LSM tree's advantage on writes is enormous. That's the world LSM trees were invented for.

On SSDs, random I/O is fast, and a well-cached B-tree handles a lot of writes comfortably. The LSM tree still writes in big chunks, which suits flash and can reduce wear, but the speed gap is much smaller. With fast NVMe drives, the bottleneck often moves to the CPU (compaction, compression) instead of the disk.

Don't trust a 5-minute benchmark

LSM trees are easy to benchmark wrong, because the bill arrives late:

• Run until compaction reaches a steady state. The first minutes are pure memtable and L0 flushes, with no compaction debt yet. Run for hours, with more data than RAM, or you're measuring the honeymoon.
• Look at p99, not the average. An LSM tree's average can look great while compaction spikes hurt the slowest 1%.
• Use your real key pattern. Sequential keys (timestamps) and random keys (UUIDs) behave very differently in both structures.
• Mix reads and writes the way production does. Compaction competes with reads for the disk.
• Fill the disk to realistic levels. SSDs slow down as they fill, and size-tiered compaction needs free space.

Production: stalls, tombstones, tuning

1. Compaction shows up in your p99

Compaction reads and rewrites gigabytes in the background, on the same disks and CPUs that serve your queries. While a big compaction runs, reads queue behind it, and the freshly written files aren't in the Block cacheBlock cacheMemory the storage engine reserves for recently read SSTable blocks (data, index and Bloom filter blocks), so hot data doesn't need a disk read. yet. Averages barely move, but the slowest requests (p99p99 (99th percentile)The value that 99% of measurements are below — i.e. how bad the slowest 1% is. Averages hide slow outliers; p99 shows them.) get spikes every time a large merge runs.

What helps:

• Rate-limit compaction so it never takes all of the disk: RocksDB's rate_limiter, Cassandra's compaction_throughput. Too low and debt builds up, though, so this is a balance.
• Give it enough threads. RocksDB's max_background_jobs defaults to 2, which is low for a big server with fast NVMe drives.
• Watch compaction debt, not just latency: pending compaction bytes (RocksDB), pending tasks (nodetool compactionstats in Cassandra).

2. Write stalls: the engine protects itself

If writes outrun compaction for long enough, files pile up in L0 and every read must check all of them. To stop that spiral, the engine throttles writes on purpose: a Write stallWrite stallWhen compaction falls too far behind (too many files piled up), the storage engine deliberately slows down or pauses new writes so compaction can catch up..

RocksDB's defaults: compaction starts at 4 L0 files, writes are slowed at 20 and stopped at 36. It also stalls when too many memtables are waiting to be flushed (max_write_buffer_number, default 2), or when pending compaction bytes pass a soft or hard limit (64 GB / 256 GB). The log line to look for is Stalling writes because….

3. See it in a real engine

Here is real output from Pebble (CockroachDB's LSM engine, written in Go). The program writes 2 million random 100-byte values over 1 million keys, as fast as it can, with a tiny 1 MB memtable so that a lot happens quickly:

package main

import (
	"fmt"
	"log"
	"math/rand/v2"
	"os"

	"github.com/cockroachdb/pebble/v2"
)

func main() {
	os.RemoveAll("demo-db")
	db, err := pebble.Open("demo-db", &pebble.Options{
		MemTableSize:          1 << 20, // 1 MB memtable (default 4 MB) so flushes happen quickly
		L0CompactionThreshold: 4,       // compact L0 once it has 4 files
	})
	if err != nil {
		log.Fatal(err)
	}
	defer db.Close()

	value := make([]byte, 100)
	for range 2_000_000 {
		key := fmt.Appendf(nil, "user:%07d", rand.IntN(1_000_000)) // random keys: lots of overwrites
		for j := range value {
			value[j] = byte(rand.IntN(256)) // random bytes don't compress
		}
		if err := db.Set(key, value, pebble.NoSync); err != nil {
			log.Fatal(err)
		}
	}
	db.Flush()
	fmt.Println(db.Metrics())
}

Trimmed output from one run (Pebble v2.1.7; your numbers will differ from run to run):

level | tables   size |   in   | written | r-amp  w-amp
    0 |     32  6.0MB |  263MB |  220MB |    9   0.84
    5 |     20   69MB |  109MB |  803MB |    1   7.35
    6 |     18   67MB |  105MB |  911MB |    1   8.67
total |     70  141MB |  263MB |  2.1GB |   11   8.35
WAL: in: 242MB  written: 263MB
Flushes: 290   Compactions: 81   estimated debt: 94MB

How to read it:

• Write amp ≈ 8. The app wrote 242 MB; the engine wrote 2.1 GB, counting flushes and compactions, plus 263 MB of WAL.
• Read amp = 11. We wrote faster than compaction could merge, so L0 holds 32 files in 9 overlapping layers (each layer counts as one place to check), plus one place each in L5 and L6 (their files don't overlap, so a lookup touches only one file per level). That's compaction debt (94 MB) made visible.
• L1–L4 are empty. Pebble, like RocksDB's level_compaction_dynamic_level_bytes (on by default in recent versions), sizes levels from the bottom up, so a small database skips the middle levels entirely.
• Space amp ≈ 1.45. About 865 000 distinct keys × ~112 bytes ≈ 97 MB of live data takes 141 MB on disk, because older versions waiting in L0 haven't been merged away yet.

4. Tombstones: Cassandra's classic trap

In a distributed database, a delete has to reach every replica (see Replication). If one replica was down during the delete and compaction drops the tombstone on the others, that replica's old copy can later be copied back: the deleted data comes back. So Cassandra keeps tombstones for gc_grace_secondsgc_grace_seconds (Cassandra)How long Cassandra keeps a tombstone before compaction may remove it (default 10 days), so that every replica has time to learn about the delete. Remove it too early and the deleted data can come back. (default 10 days) before compaction may drop them. You must run repairsRepair (Cassandra)A background job that compares the replicas of the same data and copies over any writes or deletes one of them missed, so they agree again. (a background job that makes replicas agree) more often than that, so every replica has seen the delete before the tombstone goes.

The trap: using a Cassandra table as a queue. Insert jobs into one partitionPartition (Cassandra)All the rows that share one partition key, e.g. every message in one chat. They are stored together, sorted, on the same replicas. A partition tombstone deletes the whole group with one record. (the rows sharing one partition key, stored together), delete each when it's done. A week later, reading “the first pending job” means scanning past hundreds of thousands of tombstones before reaching one live row. Cassandra logs a warning at 1 000 tombstones scanned in one query (tombstone_warn_threshold) and aborts the query at 100 000 (tombstone_failure_threshold).

Fixes: don't build queues on LSM tables (use a real queue, see Worker pools); split such data into time-bucketed partitions you drop whole; prefer one range tombstone (deletes every row between two keys) or partition tombstone (deletes the whole partition) over thousands of single-row ones.

5. TTLs and why time-series fits LSM trees

A TTLTTL (time to live)An expiry time attached to a piece of data: “delete this row 7 days after it was written.” Caches and DNS use TTLs so stale entries disappear on their own. marks data to expire, say after 30 days. In an LSM tree, expired data is only really removed when compaction rewrites the file it's in. That can be weeks later if the file sits in a deep, rarely compacted level.

Time-series data dodges most of this, which is why LSM trees and Time-series dataTime-series dataMeasurements stamped with a time — sensor readings, metrics, prices. Written constantly, almost never updated, and read back by time range. fit so well:

• Keys arrive in order. Each flush covers a new, later time range, so files hardly overlap. RocksDB can then push a file down a level by just recording the move, with no rewrite (a “trivial move”), so write amp drops.
• Old data expires in whole files. Cassandra's TimeWindowCompactionStrategy groups SSTables by time window (e.g. one per day). When a window's TTL passes, the whole file is deleted without merging anything. RocksDB has FIFO compaction and DeleteRange for the same idea.

6. The knobs that matter

Change one knob at a time, under a realistic load that runs long enough for compaction to settle (§10), and watch write amp, stall counters and p99 together.

7. Crash recovery and “durable” writes

After a crash, the engine replays the WAL to rebuild its memtables (§03). Two production details:

• Replay time grows with memtable size. Several large memtables plus their WAL can mean a long startup. Bigger memtables trade restart time for fewer flushes.
• “Written” doesn't always mean fsynced. RocksDB's WriteOptions.sync is false by default. A write survives a crash of your process (the OS still holds it), but not a power cut of the machine. Cassandra's default commitlog_sync: periodic fsyncs the commit log every 10 seconds and relies on other replicas to cover the gap. Know which one you're running, and decide whether that's acceptable for your data.

Pitfalls

Check yourself

Predict the answer before you click. Q1 is covered in §04, Q2 in §05, Q3 in §02–§03, Q4 in §06 and §11, Q5 in §10, and Q6 uses the toy LSM tree from §08.

memtable:  (empty)
sst-2 (newer):  cat=purr   dog=☠ (tombstone)
sst-1 (older):  ant=tiny   dog=woof

get("dog") → ?

L1:  dog=☠ (tombstone, written today)
L2:  (nothing about dog)
L3:  dog=woof (written last year)

A compaction merges L1 into L2 and DROPS the tombstone.
Then: get("dog") → ?

db, _ := Open("data", 2)
db.Put("a", "1")
db.Put("b", "2")
db.Delete("a")
db.Put("c", "3")
v, ok := db.Get("a")
fmt.Println(len(db.tables), v == "", ok)

Cheat sheet