Storage Engines: B-Tree vs. LSM-Tree
The problem
A database's index has to live on disk, not just in memory, and disk access is orders of magnitude slower than RAM — the data structure chosen to organize that on-disk data determines whether the database is optimized for fast reads, fast writes, or some balance between the two, and different workloads genuinely need different answers.
Why now
Indexes and query performance already established that B-trees back most relational indexes, treating the tree as a given; this topic opens that up, explaining why B-trees were chosen (in-place updates, good read performance) and introducing the LSM-tree as a fundamentally different, write-optimized alternative most NoSQL and time-series databases actually use instead.
Mental model
A B-tree keeps data sorted on disk and updates it in place — great for reads (one predictable path down the tree), but every write risks an expensive random disk seek to the right page. An LSM-tree instead never updates in place: writes go to an in-memory buffer that's periodically flushed to disk as an immutable sorted file, with older files merged (compacted) in the background — trading slightly slower, multi-file reads for dramatically faster, sequential-only writes.
Requires
- TreesComputer Science Fundamentals
A B-tree is a specific, disk-optimized balanced tree; you need general tree structure and balancing already understood before its disk-specific adaptations (large branching factor, fixed-size pages) make sense.
- Indexes & Query PerformanceDatabase Engineering
This topic opens up the storage engine already assumed as a given there; you need to already know that an index is a B-tree (or similar) before asking why that choice was made, and what the alternative costs and buys.
Unlocks
Used in
- PostgreSQL and MySQL's InnoDB, both B-tree-based storage engines optimized for balanced read/write workloads
- Cassandra, RocksDB, and LevelDB, all LSM-tree-based and optimized for write-heavy workloads
- Time-series databases, which favor LSM-trees because they're almost entirely append-heavy
- Choosing a database for a workload based on its underlying storage engine, not just its query language
Projects
- Diagram how a B-tree handles an insert (in-place page update, possible page split) versus how an LSM-tree handles the same insert (memtable write, eventual flush and compaction)
- Benchmark write throughput on a B-tree-based database versus an LSM-tree-based one under a heavy sequential-write workload, and explain the result in terms of disk seek behavior
Examples
- A B-tree insert that causes a page to overflow triggers a page split, which can cascade up the tree — a real, bounded cost paid at write time in exchange for consistently fast reads
- An LSM-tree's compaction process merging several sorted files in the background is directly analogous to merge sort's merge step — the same algorithm, running continuously on disk
Resources
Mastery checklist
- I can explain how a B-tree performs an in-place update and why that costs a random disk seek
- I can explain how an LSM-tree defers and batches writes via memtables and compaction
- I can explain the read/write tradeoff between the two storage engine families
- I can choose an appropriate storage engine family given a workload's read/write ratio