Part 7 of 8 · 4 min read
Choosing between them
A rule of thumb and the questions that decide which engine suits a workload.
Choosing between them
Think of a delivery depot. One kind of depot sorts each parcel into its exact shelf on arrival. It is slower to receive, but any parcel is found at once. Another stacks arrivals quickly and sorts in the quiet hours. It receives fast, but finding a parcel can mean checking several stacks.
The book gives the rule of thumb: LSM-trees are typically faster for writes, and B-trees are thought to be faster for reads. Reads on an LSM-tree check several structures. It also warns that benchmarks are often inconclusive and depend on the workload, so a real test with your own data is the only reliable comparison.
Advantages of LSM-trees, from the book: higher write throughput, sometimes lower write amplification, sequential writes, better compression and less fragmentation.
Advantages of B-trees, from the book:
- Predictable response times, with no background compaction competing for the disk.
- Each key lives in exactly one place. This suits transactions, since in many relational databases isolation is done with locks on key ranges, and in a B-tree those locks attach directly to the tree.
- Maturity: B-trees have been in use since 1970 and remain the standard index structure in almost all relational databases.
| Question | Leaning |
|---|---|
| Heavy writes, such as logs, events and time series | LSM-tree |
| Mostly reads and point lookups with moderate writes | B-tree |
| Strict latency at the 99th percentile | B-tree |
| Need for strong transactions on ranges | B-tree |
| Data larger than memory with high write volume | LSM-tree |
| Disk wears out quickly under heavy writes | LSM-tree, with care |
Typical products:
| Engine | Products that use it |
|---|---|
| B-tree | PostgreSQL, MySQL (InnoDB), SQL Server, Oracle, LMDB |
| LSM-tree | Cassandra, HBase, RocksDB, LevelDB, parts of Lucene |
A worked example. A system stores 50,000 events a second, each 200 bytes, and reads them mostly by user and time range.
- Write volume: 50,000 × 200 = 10,000,000 bytes per second = 10 MB per second.
- With a B-tree, each insert is a random page write: 50,000 random writes a second, with write amplification of about 40 (section 3). Disk writes: 10 MB × 40 = 400 MB per second. That is heavy.
- With an LSM-tree and a write amplification of 10: 10 MB × 10 = 100 MB per second, mostly sequential.
- The LSM-tree gives about four times less disk write volume (400 ÷ 100), and sequential access. So a wide-column store on an LSM engine is a natural fit, as module 1 suggested.
Ending on the book's caution: there is no quick rule for which engine is better, and testing with the real workload is worth the time.
Interview angle
Answer in your head first, then open it.
Why is Cassandra good at writes?
It uses an LSM engine. A write is a log append and a memory insert, with sorted files merged later. Name the cost: read work across files and compaction load.
Why does a relational database keep a write-ahead log?
The page changes of a B-tree touch several pages, and a crash could leave the tree broken. The log is replayed to repair it.
What is write amplification?
The extra disk writes caused by logs, page rewrites and compaction. It limits write throughput and wears out SSDs.
How do you check whether a key exists quickly in an LSM-tree?
A Bloom filter for each file, so most files are skipped.
Check yourself:
- Which design suits predictable latency better, and why?
- Why is an LSM-tree a good fit for a stream of 50,000 events a second?
Words you will meet
| Word | Plain meaning |
|---|---|
| Storage engine | The part that lays out and finds data on disk |
| Page | A fixed-size block, traditionally 4 KB |
| B-tree | A tree of pages that keeps keys sorted |
| Branching factor | The number of children a page points to |
| Leaf page | The bottom level that holds the keys |
| Page split | Dividing a full page in two |
| Write-ahead log (WAL) | An append-only file written before the pages change |
| Copy-on-write | Writing a changed page to a new place instead of overwriting |
| LSM-tree | Log-structured merge-tree: memtable plus sorted files |
| Memtable | A sorted in-memory table of the newest writes |
| SSTable | A sorted file of key-value pairs |
| Compaction | Merging files and dropping old values |
| Tombstone | A marker that records a delete |
| Bloom filter | A small structure that says a key is definitely absent, or maybe present |
| Write amplification | Disk bytes written per application byte |
| Sequential, random write | Adding at the end, or writing far from the last place |