Storage Engines - B-Tree vs LSM-Tree

At the core of every database management system lies a storage engine responsible for organizing data on persistent storage (SSDs, NVMe drives, or HDDs). The two dominant storage paradigms in modern software architecture are B-Trees (and B+ Trees) and Log-Structured Merge-Trees (LSM-Trees).

The choice between them reflects a fundamental trade-off in computer science: In-Place Updates (optimized for reads and predictable point lookups) versus Append-Only Writes (optimized for write throughput and sequential I/O).

B-Tree & B+ Tree Architecture (In-Place Updates)

Invented by Rudolf Bayer and Edward McCreight in 1970, B-Trees and their ubiquitous variant, B+ Trees, have been the standard foundation of relational databases (PostgreSQL, MySQL InnoDB, SQLite, Oracle) for over four decades.

How B+ Trees Work

A B+ Tree organizes data into fixed-size blocks called pages (typically 4KB, 8KB, or 16KB), matching the underlying disk block or operating system page size:

• Root & Internal Nodes: Contain routing keys and child pointers to direct searches down the tree hierarchy.
• Leaf Nodes: Store actual data rows or key-pointer pairs. All leaf nodes are linked sequentially in a doubly-linked list, enabling efficient range scans.
• In-Place Modification: When updating an existing record, the storage engine reads the target page into memory (the Buffer Pool), modifies the record in-place, and marks the page as dirty.
• Write-Ahead Log (WAL): Because modifying a disk page in-place is not atomic, the engine first writes changes sequentially to a WAL on disk before touching pages in memory. If a crash occurs, the WAL is replayed to restore consistency.
• Checkpointing: Background flush threads periodically flush dirty pages from the Buffer Pool back to their fixed locations on disk.

Trade-offs of B+ Trees

• Strengths:
  • Predictable read performance: point lookups require strictly $O(\log N)$ page accesses.
  • Low read amplification: a single point read retrieves only the exact page containing the record.
  • Simple concurrency control: page-level latches (locks) isolate concurrent transactions.
• Weaknesses:
  • High Write Amplification: modifying a single 50-byte column requires writing the entire 16KB page to disk during checkpointing, plus writing to the WAL.
  • Random Disk I/O: dirty pages scattered across the tree must be written back to non-contiguous sectors on disk.

LSM-Tree Architecture (Append-Only)

Introduced by Patrick O'Neil, Edward O'Neil, and Gerhard Weikum in 1996, the Log-Structured Merge-Tree (LSM-Tree) powers write-intensive distributed databases and key-value stores such as RocksDB, Apache Cassandra, ScyllaDB, ClickHouse, TiKV, and Google Bigtable.

How LSM-Trees Work

Instead of updating data in-place, an LSM-Tree treats disk storage as an append-only sequence of immutable files:

1. MemTable (In-Memory Buffer): All incoming writes (inserts, updates, deletes) are written sequentially to an in-memory sorted data structure (usually a Concurrent SkipList or Red-Black Tree).
2. Write-Ahead Log (WAL): Simultaneously, the write is appended to an on-disk WAL to ensure durability across power failures.
3. Flushing to SSTable: Once the MemTable reaches a threshold (e.g., 64MB), it becomes read-only and a background thread flushes its sorted contents to disk as an SSTable (Sorted String Table). A fresh MemTable is created for new writes.
4. SSTables (Immutable Disk Files): SSTables on disk are sorted by key and divided into blocks. Because they are immutable, they require no locking during concurrent reads. Deletes are handled by appending a special "tombstone" marker.
5. Bloom Filters: Because a key could reside in any of the SSTables, each SSTable has an in-memory Bloom filter. If the Bloom filter returns false, the engine skips reading the SSTable entirely, avoiding wasted disk seeks.
6. Compaction: Over time, multiple SSTables accumulate duplicate updates and tombstones. Background compaction processes merge overlapping SSTables together (similar to merge sort), discarding obsolete versions and reclaiming space.

Compaction Strategies

• Size-Tiered Compaction (STCS): Merges SSTables of similar size into larger ones. Great for write throughput, but requires significant temporary disk headroom (up to 50% free space).
• Leveled Compaction (LCS): Divides disk storage into levels (L0, L1, L2...), where each level is 10x larger than the previous one. Keys within any level (L1+) are strictly non-overlapping. Great for fast point lookups and low space amplification, at the cost of higher write amplification during compactions.

The Three Amplifications (RUM Conjecture)

Every database engine balances three competing resource costs:

1. Write Amplification (WA): Bytes written to underlying storage divided by bytes written by the user application.
   • B-Trees: High (writing a full 16KB page for small record updates).
   • LSM-Trees: Moderate to High during compaction, but initial writes are purely sequential.
2. Read Amplification (RA): Number of disk reads required to satisfy a single user query.
   • B-Trees: Low ($O(\log N)$, usually 3 to 4 page reads from root to leaf, with internal nodes cached).
   • LSM-Trees: Moderate to High (must check MemTable and potentially multiple SSTables unless caught by Bloom filters).
3. Space Amplification (SA): Total disk space consumed divided by actual size of active, valid data.
   • B-Trees: Low to Moderate (fragmentation from internal page splits leaves pages 50% to 75% full).
   • LSM-Trees: Low in Leveled Compaction; Higher in Size-Tiered Compaction due to lingering tombstones awaiting compaction.

Comparison Matrix

Dimension	B+ Tree	LSM-Tree
Primary Workload	Read-heavy, balanced OLTP	Write-heavy, streaming, telemetry
Update Pattern	In-place overwrite	Append-only / Out-of-place
Write Speed	Slower (random I/O + page flushing)	Extremely fast (sequential append to MemTable + WAL)
Read Speed (Point)	Fast and deterministic	Fast with Bloom filters; slower on misses
Range Queries	Fast (leaf nodes sequentially linked)	Fast (iterates over multiple merged iterators)
Hardware Affinity	Traditional HDDs, cached SSDs	Modern Flash / NVMe SSDs (favors sequential writes)
Concurrency Model	Page latches / Lock manager	Lockless writes (SkipList), immutable disk reads
Popular Engines	InnoDB (MySQL), Postgres, SQLite, WiredTiger	RocksDB, LevelDB, Cassandra, ScyllaDB, TiKV

When to Choose Which?

Choose a B-Tree / B+ Tree Engine when:

• Strict ACID Transactions & Predictable Latency: You run classic transactional workloads where 99th percentile read latency must remain rock-solid without compaction jitter.
• Read-Dominated Workloads: Read-to-write ratios exceed 80:20, and point queries must return with minimal CPU overhead.
• Relational Integrity: Foreign keys, unique constraints, and row-level locking require immediate in-place validation.

Choose an LSM-Tree Engine when:

• Massive Ingestion Rates: You are capturing time-series metrics, IoT sensor data, append-heavy audit logs, or financial tick streams.
• Distributed Scale-Out Storage: You are building distributed storage clusters where data immutability simplifies snapshotting, cloud object storage offloading (S3), and replication.
• Maximizing SSD Lifespan: By transforming random writes into contiguous sequential writes, LSM-Trees reduce SSD write wear and wear-leveling overhead.