LSM Tree vs B+ Tree: the Same Writes and Reads, Side by Side

The idea: update in place, or append and merge later

A storage engine keeps sorted keys on disk so that it can find one key, or a range of keys, without reading everything. There are two classic ways to keep them sorted while new writes arrive:

• B+ tree (InnoDB, PostgreSQL's btree, SQLite, Oracle, SQL Server): the keys live in fixed-size pages, and each write goes to the one leaf page that owns the key and changes it in place. The tree is always sorted and there is always exactly one copy of each key. The price is that the disk sees small random writes of whole pages, even for a one-byte change.
• LSM tree (log-structured merge tree: RocksDB, LevelDB, Cassandra, ScyllaDB, HBase, MyRocks, TiKV): a write is appended to a log and inserted into a sorted buffer in memory. When the buffer is full it is written out as an immutable sorted file, and background compaction merges those files into bigger ones. The disk only ever sees large sequential writes; the price is that the same entry is rewritten several times, and a read may have to look in several files.

The page runs both engines on the same operations, in lockstep: step i of both sides is drawn at the same time, and the shorter side waits. Under each side the counters add up what the disk did, in entries (one key-value pair is the unit of every counter):

• write amplification = entries written to disk ÷ entries the user wrote,
• read amplification = blocks read per point lookup (GET),
• space amplification = entries on disk ÷ live keys.

Keys are 1–40. Values are v1, v2, …, a global write counter, so an old version of a key is visible as an older v.

How to read the canvas. B+ tree: grey = inner page (cached in RAM, free to read), blue = leaf page read (1 block), orange = page written by this operation, yellow = changed in RAM but not yet written; the leaves are chained left → right in key order. LSM tree: each SSTable shows its name and fence keys (min–max), its keys with their version v# underneath, grey = an older version, red ✝ = a tombstone, and its 16 bloom-filter bits. The two lines under each side are the totals since Reset and this operation's cost; the bars below compare the three amplifications.

The B+ tree side

This is the same structure as the B+ tree page and the B+ tree as a database index page, with max degree 5: a leaf page holds up to 4 entries and splits 2 | 3 when a fifth arrives, copying the new right leaf's first key up into the parent; an inner page with 5 keys splits and moves its middle key up. Leaves are chained left to right, which is what makes range scans cheap.

• Reads. Inner pages are few and hot, so the page assumes they are always cached (grey, 0 reads). A point read costs exactly one leaf read, found or not.
• Writes. A write costs one WAL entry plus every page it dirtied, each written whole (4 entries): 1 page normally, 3 on a leaf split (both halves and the parent). The B-tree flush select chooses when pages are written: after every write, or at a checkpoint every 4 writes, which writes each dirty page once however many times it changed. Real databases do the second (PostgreSQL's checkpointer, InnoDB's page cleaner); the WAL is what makes delaying the page write safe after a crash.
• Deletes remove the entry from its leaf. Pages never merge on this page, as in PostgreSQL, where empty pages are only recycled by VACUUM.

The LSM write path

1. WAL. The write is appended to the write-ahead log: one sequential entry, so the memtable can be rebuilt after a crash.
2. Memtable. The entry goes into a sorted in-memory structure (a skiplist in RocksDB and LevelDB). A write of a key already in the memtable replaces it. A delete is a new entry too: a tombstone (✝) that hides older versions.
3. Flush. When the memtable is full it becomes immutable (a new one takes the writes) and is written out as an SSTable (sorted string table) into level 0, in one sequential write. The WAL segment that protected it is then deleted. Here the memtable holds 4 entries and the flush happens inside the write that filled it.
4. SSTable format. A real SSTable is a sequence of data blocks (a few KB of sorted entries each), an index block with the first key of each data block (the fence pointers), a filter block with a bloom filter, and a footer. It is never modified after it is written. On the page each file has at most 4 entries in one block, so reading a file costs 1 block, and it shows its fence min–max and its 16 bloom bits.

Compaction: leveled vs size-tiered

Files pile up, and old versions and tombstones pile up with them. Compaction reads some files, merges them by key (a k-way merge: one iterator per file, always taking the smallest key, and keeping only the newest version of each), and writes new files. The page uses leveled compaction, RocksDB's default:

• L0 files may overlap each other, because each is a memtable. When L0 holds 2 files, all of them are merged with every L1 file their key range overlaps, and the result is written as new L1 files of 4 entries.
• Every level below L0 is one sorted run: its files never overlap. When L1 holds more than 3 files, the next L1 file in key order (a round-robin cursor, as RocksDB's compaction pointer) is merged with the L2 files it overlaps. L2 is the last level here.
• An older version is dropped whenever a newer one is in the same merge. A tombstone is dropped when nothing below the output level can still hold an older version of its key; until then it must be kept, or the old value would come back.

The other classic policy is size-tiered (Cassandra's default, RocksDB's universal compaction): files of similar size are merged together into one bigger file, without a fixed level structure. The page only animates leveled; the trade-off, roughly, for a size ratio T between levels or tiers and L levels:

	Leveled	Size-tiered
Write amplification	higher: about T per level (an entry is rewritten each time its level merges into the next)	lower: about 1 per tier
Space amplification	low, about 1.1 (most data sits in the last level, already deduplicated)	high: up to 2× during a big merge, more with many overwrites
Point read	one file per level (plus every L0 file)	up to T files per tier
Used by	RocksDB, LevelDB default; Cassandra LCS	Cassandra STCS default, ScyllaDB, RocksDB universal

Compaction debt. Compaction runs in background threads and must keep up with the write rate. If it falls behind, L0 fills up and every read has to check more overlapping files; RocksDB then slows down writes (level0_slowdown_writes_trigger) and finally stops them (level0_stop_writes_trigger): a write stall. The page runs compaction synchronously inside the write that triggered it, so you can see the burst in the per-operation counter.

Reads: where the LSM pays

A key can be in the memtable, in any L0 file (they overlap), or in one file per deeper level. A point read checks them newest first and stops at the first hit; a tombstone means "not found". Most files can be skipped cheaply: first by the fence (the file's key range, kept in memory), then by the bloom filter. Without bloom filters, a read must open every file whose fence covers the key (Demo 3: 2 reads where the B+ tree needs 1).

A range scan cannot use bloom filters. It opens an iterator on the memtable and on every file that overlaps the range, and merges them (Demo 4). The B+ tree finds the first leaf and follows the leaf chain, already in order.

Bloom filters

A bloom filter is m bits and k hash functions. Adding a key sets its k bits; a lookup checks the k bits of the key: if any is 0, the key is definitely not in the file; if all are 1 it may be, and the block is read. There are no false negatives, but there are false positives, bits set by other keys. With n keys the false-positive rate is about

(1 − e−kn/m)k

RocksDB's default of 10 bits per key with k ≈ 7 gives about 1%. The page uses m = 16 bits, k = 2, with h1(k) = k mod 16 and h2(k) = (3k + 5) mod 16, so the bits can be checked by hand. For 4 keys the formula gives (1 − e^−0.5)² ≈ 15%.

Worked example (Demo 2): after Load 12 Keys, L0 file e holds 3, 8, 20, 27, which set bits h1 = 3, 8, 4, 11 and h2 = 14, 13, 1, 6, so its filter is {1 3 4 6 8 11 13 14}. GET 19: e's fence 3–27 covers 19, h1 = 19 mod 16 = 3 is set, h2 = 62 mod 16 = 14 is set: "maybe", so e is read, and 19 is not there: a false positive (bit 3 came from key 3, bit 14 from key 3 as well). Then L1 file d (14–30) has h1 = 3 clear: skipped. One wasted read. GET 23 skips e because bit 7 is clear, and reads only d.

Updates, deletes and space

A B+ tree overwrites in place, so it holds exactly one entry per live key (its waste is half-empty pages instead). In an LSM tree an update or a delete is a new entry: the old version and the tombstone take disk space until compaction brings them together. In Demo 5, after PUT 9, PUT 5, DEL 17, PUT 40 and the flush, the disk holds 16 entries for 12 live keys (space amplification 1.33); the compaction that follows drops the two old versions, the dead 17 and its tombstone, back to 12. During a compaction the new files are written before the old ones are deleted, so space briefly grows further (the page counts the compaction output in its space counter). Entries still in the memtable are not on disk yet, so the ratio can also dip below 1.

Deleting a whole range key by key would write one tombstone per key; real LSMs have range tombstones (RocksDB DeleteRange) that cover a key range in one entry. Many tombstones that compaction has not reached yet also slow reads down, a known Cassandra problem.

Two WALs for two reasons

Both engines log every write first, but for different reasons. The B+ tree's WAL lets it change pages in memory and write them later (at a checkpoint): after a crash, redo from the log repairs the pages. The LSM's WAL only protects the memtable, and is truncated after each flush, because the SSTable is then the durable copy. (On this page the B+ tree's WAL is counted but never truncated.)

Write amplification, SSDs and the RUM conjecture

Write amplification matters twice on flash: every rewritten byte costs bandwidth that user writes could have used, and SSDs wear out after a limited number of writes per cell. Small random page writes are also what SSDs (and much more so hard disks) do worst. That is why write-heavy systems (time series, logs, message queues, metrics) favour LSM trees.

The RUM conjecture (Athanassoulis et al., 2016) says an access method can optimise at most two of Read overhead, Update overhead and Memory (space) overhead. A B+ tree is read-optimised with moderate update cost; an LSM tree buys cheaper updates with more read work and temporary space; compaction policies move an LSM along the curve between them.

The page's tiny sizes exaggerate some effects: a real B+ tree page holds hundreds of entries, so a one-entry change costs far more than 4× the entry, and a real LSM has 5 to 7 levels with a size ratio of 10, so its write amplification is typically 10–30, not 2 or 3. What the page shows faithfully is the shape: the B+ tree pays a steady cost on every write and 1 block per read; the LSM pays little per write, then in bursts, and more per read.

Where each is used

	B+ tree	LSM tree
Systems	InnoDB (MySQL), PostgreSQL, SQLite, Oracle, SQL Server, LMDB, most file systems	RocksDB, LevelDB, Cassandra, ScyllaDB, HBase, MyRocks, TiKV, CockroachDB (Pebble)
Writes	random page writes, steady cost	sequential, cheap now, compaction later (bursty)
Point reads	one leaf	memtable, then one file per level (bloom filters skip most)
Range scans	walk the leaf chain	merge an iterator per overlapping file
Space	one copy per key, pages partly empty	old versions and tombstones until compaction
Good for	read-heavy, OLTP with many point reads and short scans	write-heavy, ingest, time series, key-value stores

What the page leaves out

A block cache (every leaf or block access counts as a read here); compression; prefix bloom filters and partitioned index and filter blocks; the immutable memtable and background flush and compaction threads; the size ratio between levels (limits are counted in files, not bytes); universal and size-tiered compaction; B+ tree page merges, fill factor and free-space maps; B^ε-trees, which buffer writes inside the inner nodes of a B-tree; and WiscKey-style key-value separation (BlobDB, Titan), which keeps large values out of compaction.

See also WAL and crash recovery for what the B+ tree's log is for, and MVCC and isolation levels for how PostgreSQL keeps old row versions for a different reason.

References

P. O'Neil, E. Cheng, D. Gawlick, E. O'Neil: The Log-Structured Merge-Tree (LSM-Tree), Acta Informatica, 1996

RocksDB wiki: Leveled Compaction

RocksDB wiki: RocksDB Tuning Guide (write, read and space amplification)

M. Athanassoulis et al.: Designing Access Methods: The RUM Conjecture, EDBT 2016