LSM-Trees vs. B-Trees: Storage Engine Internals Behind High-Throughput Databases

At the core of every relational database, distributed key-value store, and streaming event engine lies a fundamental software component: the Storage Engine. The storage engine dictates how bytes are physically organized on disk, how concurrent transactions acquire locks, how crash recovery is guaranteed, and how fast queries return.

For over four decades, the undisputed king of database storage has been the B-Tree (specifically the $B^+$Tree), powering classic relational workhorses like PostgreSQL, MySQL (InnoDB), SQLite, and Oracle.

However, the explosion of massive write-heavy workloads—such as distributed telemetry ingestion, financial market tick data, social media feeds, and timeseries analytics—exposed the primary weakness of B-Trees: high write amplification and random disk I/O. To solve this, Google introduced the Log-Structured Merge-Tree (LSM-Tree) with Bigtable, which now underpins modern high-throughput engines like RocksDB, Apache Cassandra, ClickHouse, TiKV, ScyllaDB, and InfluxDB.

In this technical deep dive, we dissect the internal mechanics of B-Trees vs. LSM-Trees, evaluate the RUM Conjecture, explore MemTable skip-lists, SSTables, Bloom filters, and compaction strategies, and construct a working miniature LSM storage engine in Python.

The RUM Conjecture: The Fundamental Storage Trade-Off

In 2016, database researchers formalized the fundamental trade-offs of database storage structures as the RUM Conjecture. When designing a storage engine, you cannot optimize all three dimensions simultaneously; you must prioritize two at the expense of the third:

B+Trees: The Read-Optimized In-Place Update Paradigm

In a $B^+$Tree, data is organized into fixed-size pages (typically $4\text{ KB}$, $8\text{ KB}$, or $16\text{ KB}$, aligning directly with operating system and disk block boundaries):

B+Tree Hierarchical Organization:

                     [ Root Page: Keys [20, 50] ]
                            /         |         \
                           v          v          v
    [ Internal Page: [10] ]   [ Internal Page: [35] ]   [ Internal Page: [70] ]
          /           \             /           \             /           \
         v             v           v             v           v             v
    [Leaf: 1..9] <-> [Leaf: 10..19] <-> [Leaf: 20..34] <-> [Leaf: 35..49] <-> [Leaf: 50..69] <-> [Leaf: 70+]
    (All leaf pages linked as a bidirectional linked list for blazing-fast range scans!)

Key Architectural Properties of $B^+$Trees:

1. In-Place Updates: When a record is updated or inserted, the database finds the exact leaf page on disk, modifies the bytes inside that page, and marks it as "dirty".
2. High Fan-Out: Because internal nodes only store keys and page pointers (no payload data), a single $8\text{ KB}$ page can hold hundreds of child pointers ($B \approx 500$). A 4-level $B^+$Tree can index billions of rows with only 3 to 4 page hops!
3. Predictable Read Latency: Finding any key requires exactly $H$ page lookups. With top levels cached in RAM, most reads require only 1 physical disk seek.

The Write Bottleneck: The Double-Write & Page Split Problem

The Achilles' heel of B-Trees is random disk writes. Modifying a 20-byte row requires writing the entire $8\text{ KB}$ page back to disk (a Write Amplification Factor of $400\times$). Furthermore:

• Torn Page Protection: If a power failure occurs midway through writing an $8\text{ KB}$ page, the page is corrupted. Engines like MySQL InnoDB must use a Doublewrite Buffer, writing every page twice!
• Page Splits: When an insertion hits a full page, the page must be split into two half-full pages, triggering parent node updates and cascading locks across the tree.

LSM-Trees: The Sequential Append-Only Powerhouse

The core insight of the Log-Structured Merge-Tree (LSM-Tree) is simple yet profound: Sequential disk writes are orders of magnitude faster than random disk writes, especially on spinning HDDs and Flash/NVMe SSDs where random writes induce heavy flash controller erase-block wear.

Instead of modifying pages in-place on disk, an LSM-Tree buffers all incoming mutations in memory and flushes them sequentially in immutable sorted batches.

LSM-Tree Multi-Tiered Architecture:

Incoming Writes (PUT / DELETE)
       │
       ├───> 1. Append to Write-Ahead Log (WAL on disk for crash durability)
       │
       └───> 2. Insert into In-Memory MemTable (Skip-List / Red-Black Tree)
                     │
                     │ (When MemTable reaches size threshold, e.g. 64MB)
                     ▼
             3. Flush to Disk as Immutable SSTable (Sorted String Table)
                     │
       ┌─────────────┴──────────────────────────────────────────┐
       │ Level 0: [SSTable 1] [SSTable 2] [SSTable 3]          │ (Overlapping key ranges)
       └─────────────────────────────┬──────────────────────────┘
                                     │ (Background Compaction)
       ┌─────────────────────────────▼──────────────────────────┐
       │ Level 1: [SSTable A: 0..100]  [SSTable B: 101..200]   │ (Strict non-overlapping key ranges)
       └─────────────────────────────┬──────────────────────────┘
                                     │
       ┌─────────────────────────────▼──────────────────────────┐
       │ Level 2: [SSTable C: 0..500]  [SSTable D: 501..1000]  │ (10x larger capacity)
       └────────────────────────────────────────────────────────┘

Core Components of an LSM Engine:

1. MemTable (In-Memory Buffer)

An in-memory sorted data structure (usually a Skip-List or concurrent Red-Black Tree). Incoming writes (PUT, DELETE) are inserted in $O(\log N)$ time. Deletions are recorded as special Tombstone markers.

2. Write-Ahead Log (WAL)

Because MemTables live in volatile RAM, every write is sequentially appended to an on-disk WAL before returning success. If the machine loses power, the MemTable is reconstructed by replaying the log.

3. SSTables (Sorted String Tables)

When a MemTable reaches a threshold (e.g. $64\text{ MB}$), it is frozen into an Immutable MemTable and flushed to disk as an SSTable. An SSTable consists of:

• Data Block: Key-value pairs sorted in strict ascending order, compressed with Snappy or ZSTD.
• Index Block: Sparse index storing the first key and file offset of each data block for binary search.
• Bloom Filter: A space-efficient probabilistic bitset that allows the engine to check whether a key definitely does not exist in this SSTable without performing any disk I/O!

The Compaction Engine: Leveled vs. Size-Tiered

Over time, multiple SSTables accumulate on disk. If left unmanaged, read queries would have to scan dozens of files, destroying read performance. The Compaction background process merges older SSTables, purges tombstones, and resolves duplicate keys:

Comprehensive Architectural Comparison: B+Tree vs. LSM-Tree

Hands-On: Building a Working Miniature LSM Storage Engine in Python

Below is a working implementation of a miniature LSM engine demonstrating MemTable buffering, WAL logging, SSTable flushing with binary sparse index, and Bloom filtering:

import os
import json
import zlib
from typing import Optional, Dict

class BloomFilter:
    """A lightweight Murmur/zlib Bloom Filter for fast probabilistic key checks."""
    def __init__(self, size: int = 10000, hash_count: int = 5):
        self.size = size
        self.hash_count = hash_count
        self.bit_array = [0] * size

    def _hashes(self, key: str):
        h1 = zlib.crc32(key.encode('utf-8'))
        h2 = hash(key) & 0xFFFFFFFF
        for i in range(self.hash_count):
            yield (h1 + i * h2) % self.size

    def add(self, key: str):
        for idx in self._hashes(key):
            self.bit_array[idx] = 1

    def contains(self, key: str) -> bool:
        return all(self.bit_array[idx] == 1 for idx in self._hashes(key))


class MiniLSM:
    def __init__(self, data_dir: str = "./lsm_data", memtable_limit: int = 5):
        self.data_dir = data_dir
        self.memtable_limit = memtable_limit
        self.memtable: Dict[str, Optional[str]] = {}
        self.sstables = []
        os.makedirs(data_dir, exist_ok=True)
        self.wal_path = os.path.join(data_dir, "wal.log")
        self.wal_file = open(self.wal_path, "a", buffering=1)

    def put(self, key: str, value: str):
        # 1. Append to Write-Ahead Log (WAL) for durability
        self.wal_file.write(json.dumps({"op": "PUT", "k": key, "v": value}) + "\n")
        
        # 2. Insert into in-memory MemTable
        self.memtable[key] = value

        # 3. Flush to SSTable if size threshold exceeded
        if len(self.memtable) >= self.memtable_limit:
            self._flush_memtable()

    def delete(self, key: str):
        # Insert tombstone marker
        self.wal_file.write(json.dumps({"op": "DEL", "k": key}) + "\n")
        self.memtable[key] = None
        if len(self.memtable) >= self.memtable_limit:
            self._flush_memtable()

    def get(self, key: str) -> Optional[str]:
        # Step 1: Check active in-memory MemTable
        if key in self.memtable:
            val = self.memtable[key]
            return None if val is None else val  # None represents tombstone

        # Step 2: Search SSTables from newest to oldest
        for sstable in reversed(self.sstables):
            # Check Bloom filter first!
            if not sstable["bloom"].contains(key):
                continue  # Key definitely not in this file, skip disk seek!

            # Binary search the sparse index
            val = self._search_sstable_file(sstable["path"], sstable["index"], key)
            if val is not None:
                return None if val == "__TOMBSTONE__" else val

        return None

    def _flush_memtable(self):
        sstable_id = len(self.sstables) + 1
        path = os.path.join(self.data_dir, f"sstable_{sstable_id}.db")
        sorted_keys = sorted(self.memtable.keys())
        
        bloom = BloomFilter()
        sparse_index = {}

        with open(path, "w") as f:
            for k in sorted_keys:
                bloom.add(k)
                offset = f.tell()
                sparse_index[k] = offset
                v = self.memtable[k] if self.memtable[k] is not None else "__TOMBSTONE__"
                f.write(f"{k}:{v}\n")

        self.sstables.append({
            "path": path,
            "bloom": bloom,
            "index": sparse_index
        })

        # Clear MemTable and truncate WAL
        self.memtable.clear()
        self.wal_file.close()
        self.wal_file = open(self.wal_path, "w", buffering=1)
        print(f"[LSM Flush] Created SSTable: {path} with {len(sorted_keys)} keys.")

    def _search_sstable_file(self, path: str, index: dict, key: str) -> Optional[str]:
        if key not in index:
            return None
        with open(path, "r") as f:
            f.seek(index[key])
            line = f.readline().strip()
            k, v = line.split(":", 1)
            if k == key:
                return v
        return None

# --- Demonstration of MiniLSM Engine ---
if __name__ == "__main__":
    db = MiniLSM(memtable_limit=3)
    db.put("user:100", "Alice")
    db.put("user:101", "Bob")
    db.put("user:102", "Charlie") # Triggers flush to SSTable 1

    db.put("user:103", "David")
    db.delete("user:101")
    db.put("user:104", "Eve")     # Triggers flush to SSTable 2

    print("Query user:100 ->", db.get("user:100")) # Found Alice in SSTable 1
    print("Query user:101 ->", db.get("user:101")) # Returns None (Tombstone in SSTable 2)
    print("Query user:999 ->", db.get("user:999")) # Returns None (Filtered instantly by Bloom Filter)

Architectural Decision Matrix: Which Storage Engine to Choose?

Summary & Key Takeaways

• Understand Your I/O Profile: B-Trees excel at random reads and in-place updates but suffer from write amplification due to full-page writes. LSM-Trees convert random writes into sequential disk flushes, maximizing write throughput.
• Bloom Filters are Essential: Without Bloom filters, LSM read amplification destroys performance. A well-tuned 10-bit Bloom filter provides a $< 1\%$ false positive rate while keeping disk I/O to a bare minimum.
• Tune Compaction to Match Hardware: Use Leveled Compaction (RocksDB style) when disk space and fast point reads are critical; use Size-Tiered Compaction (Cassandra style) when your workload is purely append-heavy and write latency cannot tolerate compaction stalls.