Topic 13B.1
Storage Engines: B-Trees, LSM Trees & the WAL
In one line
Under every database is a storage engine that decides how bytes hit the disk. B-trees update data in place and excel at reads; LSM trees append and merge later and excel at writes. Knowing which one you're on explains most performance behaviour.
Think of it like this
Two ways to keep a phone book up to date. B-TREE: keep one perfectly sorted book and, for each change, find the right page and edit it in place (fast lookups, slower edits). LSM TREE: write every change on a sticky note in the order it arrives (super fast), and every night merge the notes into a new sorted book (compaction). Lookups may need to check the recent notes and a few books.
Key ideas
- 01
Both start with a WRITE-AHEAD LOG (WAL): every change is appended to a log and fsynced before it's acknowledged, so a crash can be replayed (Stateful Systems course, Unit 0.1). The engines differ in what happens next.
- 02
B-TREE (PostgreSQL, MySQL InnoDB, most relational databases): data lives in fixed-size pages organised as a balanced tree only 3–4 levels deep. Reads are a few page lookups; writes modify pages in place (random I/O) and may split pages. Predictable read latency, efficient range scans, the natural fit for transactions and secondary indexes.
- 03
LSM TREE (Cassandra, RocksDB, ScyllaDB, HBase, and many time-series and key-value stores): writes go to an in-memory sorted MEMTABLE; when full, it's flushed as an immutable sorted file (SSTABLE). Background COMPACTION merges SSTables and discards overwritten or deleted data (deletes are TOMBSTONES). Writes are sequential and very fast; reads may check several SSTables, helped by BLOOM FILTERS (Topic 13B.3) and caches.
- 04
The trade-off triangle: READ amplification (how many places a read checks), WRITE amplification (how many times data is rewritten), and SPACE amplification (obsolete data kept until compaction). B-trees favour reads; LSM trees favour writes; compaction strategy (size-tiered vs levelled) tunes the balance.
Code & diagrams
Explain without notes
Why are LSM trees faster for writes than B-trees?
Practice
You're storing 200,000 IoT sensor readings per second, mostly appended and queried by device and time range. Which engine family and why?
Trade-offs
- ↔
B-trees: fast, predictable reads and range scans, costlier writes. LSM: excellent write throughput and compression, read and space amplification plus compaction I/O to manage.
Run it in production
You've designed it. Now build, operate, and break the same idea hands-on in the DevOps courses:
Completion checklist
I can explain memtable, SSTable, compaction, and tombstones
I can say which engine a database uses and what that implies