Yashotantra Academy logo

3 · Partitioning & Data Stores

5. Storage Engines: LSM-Trees vs B-Trees

Write amplification, sequential vs random I/O, SSTables, Bloom filters, and compaction.

10 min read · 3 MCQs

B-Trees: Optimized for Read-Heavy Workloads

Relational engines (Postgres, MySQL InnoDB) organize data into balanced multi-way tree pages on disk. In-place updates require random disk I/O, which is expensive on storage devices, but point reads require only $O(\log_B N)$ operations with high page-cache hit rates.

LSM-Trees: Optimized for High-Throughput Writes

Log-Structured Merge-Trees (RocksDB, Cassandra) append all incoming writes sequentially to an in-memory sorted buffer (MemTable) backed by a sequential Write-Ahead Log (WAL). When full, the MemTable is flushed to disk as an immutable Sorted String Table (SSTable).

Compaction & Bloom Filters

Because SSTables are immutable, updates and deletes produce duplicate or tombstone records across multiple levels. Background compaction merges and deduplicates SSTables. In-memory Bloom filters prevent unnecessary disk reads by checking if a key definitely does not exist in an SSTable.

Chapter quiz

3 questions · pass mark 75%

  1. 1. Why do LSM-Tree storage engines achieve significantly higher write throughput than B-Trees?

  2. 2. What is the purpose of a Bloom filter in an LSM-tree database?

  3. 3. What is an SSTable?