Vibe Engines Learn
Systems · Databases

Update in Place, or Append and Merge.

Under every database is a storage engine, and almost all of them make one of two bets about how to put data on disk — a choice that quietly decides whether the system is fast at writes or fast at reads. A B-tree (Postgres, MySQL/InnoDB, most classic databases) keeps data sorted in fixed pages and updates them in place: a lookup is a short, predictable walk down the tree, so reads are cheap and stable — but every write has to find and rewrite a page wherever it lives, which on disk means a random write. An LSM-tree (RocksDB, Cassandra, LevelDB, most write-heavy stores) makes the opposite bet: it appends every write to a small in-memory buffer, and when that fills it flushes the buffer to disk as one sorted run — a single sequential write — then merges runs together in the background (compaction). Writes become cheap and sequential, but a read may have to check the buffer and several runs to find the newest value (read amplification, tamed by bloom filters). Stream the same writes into both engines and watch the trade-off happen in real time.

B-tree: in-place, cheap stable reads, random writes · LSM: append+flush+compact, cheap sequential writes, read amp
B-tree

Sorted pages updated in place. Reads walk down the tree (cheap, stable); writes rewrite a page wherever it lives (random I/O).

LSM-tree

Writes append to an in-memory memtable, flushed to disk as sorted runs, merged by background compaction.

write amplification

Compaction rewrites data multiple times as runs merge — the cost LSM pays for cheap incoming writes.

read amplification

A read may check the memtable plus several runs to find the newest value. Bloom filters cut the misses.

engine.js — random writes vs append & merge
Ready
Send the same writes into a B-tree (updates in place) and an LSM-tree (appends, flushes, compacts). Watch the B-tree do a random disk write every time, while the LSM buffers in memory and flushes in batches. Then read a key and compare the cost.
0
writes sent
0
B-tree random writes
0
LSM disk writes

How it works

The two engines are mirror images because they optimise opposite sides of the same tension: disks (and SSDs) love sequential writes and hate scattered random ones. A B-tree keeps one authoritative, sorted copy of the data in pages, so a read is a clean O(log n) descent and always touches roughly the same small number of pages — beautifully stable. The price is on writes: to change a key you must locate its page and rewrite it wherever it already sits, which is a random I/O, and high write rates turn into a storm of scattered page writes. An LSM-tree refuses to do random writes at all. Incoming writes land in a sorted in-memory memtable; when it fills, the whole thing is flushed to disk in one shot as an immutable sorted run — pure sequential I/O — so ingesting writes is extremely cheap. The catch is that the data for one key can now live in the memtable or in any of several runs (with newer runs shadowing older ones), so a read must consult them newest-first until it finds the key: that’s read amplification, which LSM engines fight with per-run bloom filters (skip a run that definitely lacks the key) and with compaction — background merging of runs into fewer, larger ones to keep the number a read must check bounded. Compaction is the hidden cost: it rewrites the same data several times over its lifetime (write amplification). So the rule of thumb is simple — write-heavy workloads favour LSM; read-heavy or range-scan-heavy workloads favour B-trees — and real engines tune where they sit on that spectrum.

1

A write arrives

The B-tree finds the key’s page and rewrites it in place — a random disk write. The LSM-tree just appends the write to its in-memory memtable — no disk I/O at all yet.

2

The memtable fills → flush

When the LSM memtable is full, it is flushed to disk as one immutable sorted run: a single sequential write for a whole batch of updates. The B-tree, meanwhile, has already paid a random write per update.

3

Runs pile up → compaction

Flushed runs accumulate, and a read must check several of them. Background compaction merges runs into fewer, larger ones — rewriting data (write amplification) to keep read cost bounded.

✓

Read the key — count the cost

A B-tree read is a short, stable descent. An LSM read checks the memtable plus each run newest-first (read amplification), skipping runs via bloom filters. Write-heavy? LSM wins. Read/scan-heavy? B-tree wins.

B-tree write
random, in place
LSM write
append → sequential flush
B-tree read
stable O(log n)
LSM read
memtable + runs (amp)

The code

# LSM-tree write path (the write-optimised bet) def put(key, val): memtable[key] = val # in-memory, ~free if len(memtable) >= MEMTABLE_CAP: run = sorted(memtable.items()) flush_sequentially(run) # ONE sequential write for the batch runs.append(run); memtable.clear() if len(runs) >= COMPACT_THRESHOLD: merge(runs) # compaction: rewrite → write amplification def get(key): # read amplification if key in memtable: return memtable[key] for run in reversed(runs): # newest first; bloom filter skips misses if bloom[run].maybe(key) and key in run: return run[key]

Quick check

1. Why are writes cheap on an LSM-tree but relatively expensive on a B-tree?

2. What is read amplification in an LSM-tree?

3. What is the purpose of compaction, and what does it cost?

FAQ

What is the difference between a B-tree and an LSM-tree?

Two storage-engine designs with opposite trade-offs. A B-tree keeps sorted pages updated in place: cheap stable reads, but each write is a random disk write. An LSM-tree appends writes to memory, flushes sorted runs, and compacts in the background: cheap sequential writes, but reads may check several runs (read amplification) and compaction rewrites data (write amplification). B-trees suit read/scan-heavy workloads; LSM-trees suit write-heavy ones.

Which databases use LSM-trees and which use B-trees?

B-tree engines: PostgreSQL, MySQL/InnoDB, most traditional relational databases, and SQLite — where stable reads and range scans matter. LSM engines: RocksDB and LevelDB, Cassandra, ScyllaDB, HBase, and many time-series/write-heavy stores. Some databases let you choose (MongoDB’s WiredTiger offers both), since the right choice depends on the workload’s read/write mix.

What are write amplification and read amplification?

The two hidden costs of an LSM-tree. Write amplification is bytes physically written versus bytes the app asked to write — compaction rewrites data several times as runs merge. Read amplification is how many places a read must check — the memtable plus each run that might hold the key. Bloom filters cut read amplification (skip runs missing the key) and compaction cuts it (fewer runs), but aggressive compaction raises write amplification — so the two are traded off.

When should I choose an LSM-tree over a B-tree?

Favour an LSM-tree for write- or ingest-heavy workloads — logging, metrics, event streams, time-series, anything absorbing a firehose of writes — since appending and sequential flushing keep write cost low. Favour a B-tree for read-heavy, point-read-latency-sensitive, or range-scan/ordered-iteration workloads, where its stable in-place structure gives predictable reads. Mixed workloads are why some engines are tunable and why LSM engines lean on bloom filters and compaction.

Keep going

Lab

SQL Query Planner →
Algorithm

B-Tree →
Algorithm

LSM-Tree →
Handbook

SQL →
▶  Watch it explained

B-tree vs LSM-tree: Sort Now, or Sort Later?

Finished this one? 0 / 61 Labs done

Explore the topic

See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.

Databases & Storage

More Labs

Explore more from Vibe Engines

Handbooks →
Roadmaps →
System Designs →
AI System Designs →
Algorithms →
Paper Breakdowns →
Challenges →