LSM Tree vs B-Tree

Problem

You are choosing the storage engine for a service with two very different tables:

• Events: 200,000 inserts per second of small append-mostly records, read back mostly by recent time range, retained for 30 days.
• Accounts: 5,000 updates per second to existing rows and 50,000 point reads per second by primary key, with strict latency targets on the reads.

Explain how a B-tree engine (InnoDB, PostgreSQL heap plus B-tree indexes, LMDB) and an LSM-tree engine (RocksDB, LevelDB, Cassandra, Bigtable) each lay data out on disk and handle a write, a point read, and a range scan. Quantify write amplification, read amplification, and space amplification for each. Then pick an engine per table and defend it.

• Assume SSDs, where random 4 KB reads are cheap but limited in count, and where every write eventually costs a flash erase cycle.
• Be explicit about what happens in memory versus on disk.

Examples

• B-tree point read of a hot key: the root and internal pages are cached, so one or two page reads at most, and often zero. Predictable, low tail latency.
• LSM point read of a key not in the memtable: check the Bloom filter of each level's SSTables; with 1% false positives and 6 levels, about one real disk read on average, but up to 6 or more on a miss without filters.
• B-tree write amplification: updating one 100-byte row eventually rewrites a 16 KB page, plus the write-ahead log record, plus repeated checkpoint writes while the page stays hot. The raw ratio for a single isolated change is over 100×, but a page usually collects many updates while dirty in cache, so 10× to 100× bytes written per byte changed is the practical range.
• LSM write amplification with a leveled compaction, fan-out 10, and 6 levels: each byte is rewritten roughly once per level times the fan-out, about 10 × 5 = 50× over its lifetime, but always as large sequential writes, which flash handles far better than random page rewrites.

Hints

1. A B-tree updates in place. What is the unit of I/O, and what does that mean for a 100-byte change?
2. An LSM never updates in place; it appends to a sorted run and merges runs later. Where does the cost move to?
3. Amplification has three kinds. Which one does each design trade away to gain the others?