A database keeps your rows on a disk that reads and writes whole blocks, and there are two common ways to organise them. A B+tree, the structure inside Postgres and InnoDB, keeps keys sorted in fixed-size pages and changes those pages in place. An LSM tree (log-structured merge tree), the structure inside RocksDB and Cassandra, never changes a file once it's written. It collects writes in memory, writes them out as new sorted files, and merges those files in the background. Both find any key quickly. They differ in where the work goes.
Chapter 18 measures that with three ratios. Write amplification is how much the engine writes to disk for each thing you asked it to write. Read amplification is how many disk reads one lookup costs. Space amplification is how much the engine stores for each piece of live data. This lab puts the same short stream of keys through both engines, small enough that you can check every number by hand.
What you're looking at
On the left is a B+tree whose pages, numbered p1, p2 and so on, hold three keys each. Real pages hold hundreds, but three makes them fill within a few clicks. Keys live in the leaf pages along the bottom, and the pages above hold separator keys that steer a search: a key at or above a separator goes right of it. When a full leaf gets another key, the engine splits it: half the keys move to a fresh page, and a separator for that page is copied into the parent. A split of the root is how the tree grows a level.
On the right is an LSM tree. New writes go into the memtable, a sorted buffer in RAM that holds four entries here. When it's full it's flushed to disk as one sorted, never-modified file, an SSTable, on level 0 (L0). L0 files come straight from memtables, so their key ranges can overlap. When L0 has two files, compaction merges them into L1, keeping the newest version of each key, in files of four entries.
The counters use one unit, an entry slot. The B+tree writes whole pages, so a page write counts as three slots; the LSM writes exactly the entries in its files. Both engines also append every change to a write-ahead log, which costs the same on both sides, so the lab leaves it out. Every page or file a lookup reads counts as a trip to disk, while the memtable is in RAM and free. Space counts the B+tree's leaf slots (in a real tree the index pages are a fraction of a percent) and every entry the LSM holds, live or not.
Things to try
Keys in increasing order
Choose Sequential and press Run to send the keys 1 to 14 to both engines, one per step.
After 14 keys in increasing order, what do the two write amplification counters say?
Every B+tree split happened at the right edge, and each left the old page full: [1 2 3], [4 5 6], [7 8 9]. Postgres does the same for its rightmost leaf, since keys arriving in order never come back to fill a half-empty page. The leaves end 93% full, a space amplification of 1.07×.
Random keys
Choose Random and run it: 14 keys from 1 to 99, picked by a seeded generator so they're the same every time.
How full are the B+tree's leaf pages after these 14 random keys?
On the LSM side, F1 covers 33 to 84 and F2 covers 5 to 80, so they overlapped and had to be merged for real: compaction rewrote all 8 entries as F3 and F4, and write amplification rose to 1.4×. The B+tree's went to 5.6×, from more splits.
Lookups and bloom filters
Keep the Random state, type 48 in the key box and press Look up. The B+tree reads three pages, root to leaf. The LSM checks the memtable for free, then F5 in L0, which covers 8 to 62, so 48 could be in it. Before reading F5 it asks the file's bloom filter, a small bit array stored with each file: every key in the file switched on two of its bits, so a key whose two bits aren't both on is definitely not in the file. F5's filter says no, F3's says maybe, and reading F3 finds 48. That's one file read. Turn the bloom filters Off and the same lookup reads both files.
Now look up 20, a key that was never inserted, with the filters back on. How many files does the LSM read?
Now look up 77. F4 covers 60 to 84 and its filter says maybe, so the LSM reads it and finds nothing. That's a false positive, and the card says so. These filters are tiny, four bits per key, so false positives turn up often. The RocksDB filters in chapter 18 use ten bits per key and were wrong 0.94% of the time.
Updates and deletes
Choose Updates & deletes and step through it slowly. Step 9 puts 47 again. The B+tree overwrites 47 in its leaf and writes that page back. The LSM can't change F4, so a new 47 goes into the memtable and the old one in L1 becomes a stale version, faded on its card: on disk, never to be read again. Steps 10 and 11 delete 33 and 81. An LSM can't remove a key from a file either, so a delete writes a tombstone, a marker that says "this key is gone", shown struck through. Step 12 deletes 40, which was never stored. The B+tree looks, finds nothing, and writes nothing. The LSM writes a tombstone anyway, because checking would cost a read, and its writes never read.
At the end the LSM holds 14 entries for 7 live keys: 4 stale versions and 3 tombstones, a space amplification of 2.0×. The B+tree's leaves hold 12 slots for the same 7 keys, 1.7×, because it doesn't merge a page that deletes have left part empty with its neighbour, and Postgres doesn't either.
Look up 33, which was deleted at step 10. What does the LSM read?
Now put 90 and then 91. The memtable fills and flushes as F6, L0 has two files, and compaction merges them with F3 and F4: 16 entries in, 4 stale versions and 3 tombstones dropped, 9 written. Space amplification falls to 1.0×. The tombstones can go because L1 is the bottom level here, so nothing older remains that they'd need to hide.
Leveled or tiered compaction
So far the compaction has been leveled: L1 is one sorted run of non-overlapping files, so anything coming down from L0 is merged with the L1 files it overlaps. Tiered compaction (RocksDB's "universal", Cassandra's size-tiered) lets several runs pile up in a level before merging them. Here L0's files become a new run in L1, and the L1 runs merge when there are three.
Choose Random, run it, then put 90 and 91, still on Leveled. L0's two files cover 8 to 91, which overlaps both F3 and F4, so compaction rewrites all 16 entries even though only 8 are new.
Switch the toggle to Tiered. The lab replays the same operations. What happens to the LSM's write amplification?
That's the trade chapter 18's table lists: leveled pays in writes to keep reads and space tight, and tiered writes less and pays in reads and space.
What this shows
The B+tree pays at write time. Every change rewrites a whole page, and every write first reads its way down to the right leaf, as the line under its write amplification counts. In exchange a lookup costs one page per level, and its wasted space is whatever its pages leave empty. The LSM writes one sequential file per memtable and never reads to write. It pays later: compaction rewrites data already written, lookups may check a file in every place a key could be, and dead data takes up space until compaction runs. Bloom filters keep its lookups cheap.
The toy scale bends some numbers. Real pages hold hundreds of keys, so splits are rare, but each update still writes a whole 8 KB page for a few bytes of change. Real LSM trees have more levels, each about ten times the one above, and each level a key passes through is another rewrite, which is how the RocksDB tree in chapter 18 reached a write amplification of 6.8.
Where this comes from
- Chapter 18, Finding a row: the B+tree: sections 3.5, "Inserts and the page split", and 3.6, "Random keys and half-empty pages".
- Chapter 18, LSM trees: never update in place: the write path, bloom filters, compaction and tombstones, sections 6.1 to 6.4.
- Chapter 18, B+tree or LSM: section 7.1, "The three costs, side by side".