LSM-Trees vs B-Trees: Storage Engine Internals

LSM-Trees vs B-Trees: The Storage Engine Architecture Deep Dive

At the lowest foundation of every database system, key-value store, and persistent message broker lies a Storage Engine—the fundamental software subsystem responsible for mapping abstract data models (rows, documents, keys, values) onto physical, non-volatile storage media.

For nearly four decades, the computing landscape was dominated by the B-Tree (and its universal variant, the B+ Tree), invented by Rudolf Bayer and Edward M. McCreight in 1970. B+ Trees became the canonical indexing engine powering relational titans like PostgreSQL, MySQL (InnoDB), Oracle, and SQLite.

However, as dataset sizes exploded into petabytes, cloud workloads demanded sustained multi-gigabyte-per-second ingestion rates, and storage hardware shifted from spinning magnetic platters to solid-state NAND Flash NVMe SSDs, the fundamental architectural assumptions of B+ Trees began to buckle. In 1996, Patrick O'Neil, Edward O'Neil, and Gerhard Weikum published their seminal paper: "The Log-Structured Merge-Tree (LSM-Tree)".

Today, LSM-Trees form the high-throughput backbone of modern distributed databases and storage platforms, including RocksDB (Meta), LevelDB (Google), Apache Cassandra, ScyllaDB, CockroachDB (Pebble), TiKV, and ClickHouse.

This technical deep dive explores the mechanical internals of LSM-Trees versus B-Trees: from NAND flash physics, memory-mapped write-ahead logs, and concurrent SkipList MemTables, to binary SSTable block layouts, Bloom filter mathematics, Leveled vs. Size-Tiered compaction algorithms, and the fundamental trade-offs governed by the RUM Conjecture.

---

1. The Mechanical Sympathy of Storage: Random vs. Sequential I/O

To understand why LSM-Trees exist, one must first analyze the physical constraints of storage hardware: Spinning Disks (HDDs) and NAND Flash Solid-State Drives (SSDs).

The Physics of NAND Flash & The Flash Translation Layer (FTL)

Unlike volatile RAM, where any single byte can be overwritten at will in $\mathcal{O}(1)$ time ($t_{RAM}\approx 50\text{ns}$), NAND Flash memory operates under strict physical and electrochemical constraints:

1. Read & Write Granularity: Flash memory is divided into Pages (typically $4\text{KB}$, $8\text{KB}$, or $16\text{KB}$). You can only read and write data in units of whole pages.
2. Erase Granularity: Flash pages cannot be overwritten in-place. Once a page contains charges, it must be erased before it can be written again. However, erase operations can only be executed on entire Erase Blocks (typically 128 to 512 pages, totaling $2\text{MB}$ to $8\text{MB}$).
3. Erase Latency & Wear: Erasing an erase block requires high-voltage pulses that physically degrade the silicon oxide insulation layer. NAND flash cells can only endure $1,000$ to $10,000$ Program/Erase (P/E) cycles before hardware failure. Furthermore, block erasure takes $1.5\text{ms}-3.0\text{ms}$—orders of magnitude slower than a page read ($10\mu \text{s}-50\mu \text{s}$) or page program ($200\mu \text{s}-500\mu \text{s}$).

When a classical database engine like InnoDB executes an in-place update of a 100-byte row inside an 8KB page:

• The SSD controller's Flash Translation Layer (FTL) cannot rewrite the physical flash page.
• The FTL must allocate a new, empty flash page elsewhere, write the modified 8KB page, and mark the old physical page as stale / garbage.
• Over time, the SSD runs out of free erase blocks. The FTL's internal Garbage Collector (GC) must kick in: it reads all valid pages from a fragmented block, copies them to a newly erased block, and erases the old block.

This phenomenon causes Device-Level Write Amplification: updating 100 bytes of data at the application layer can trigger tens of kilobytes of internal NAND flash writes, exhausting SSD endurance and triggering massive tail-latency spikes ($p99.9$).

The B+ Tree Axiom: In-Place Updates & The Doublewrite Bottleneck

In a B+ Tree storage engine:

• Data is stored in fixed-size Pages / Blocks (e.g., 8KB in PostgreSQL, 16KB in MySQL InnoDB).
• Inner nodes store routing keys and child page pointers; leaf nodes store actual keys and data payloads (or heap tuple pointers) linked in a doubly-linked list for sequential range scans.

When inserting or updating random keys:

1. Tree Traversal: The engine traverses the tree from root to leaf in $\mathcal{O}({\log }_{B}N)$ steps to locate the target page.
2. Dirtying the Buffer Pool: If the page is in the in-memory Buffer Pool, it is updated in place and marked dirty.
3. Page Splits: If the leaf page is full, it must split into two 50% occupied pages. This requires acquiring exclusive locks ($X$-locks) up the tree spine, creating severe lock contention.
4. Flushing & Torn Pages: When the background flusher writes the dirty page back to disk, a system crash midway through an 8KB/16KB page write causes a torn page (corrupted half-written page). To prevent this, engines must write entire pages twice: first to a sequential Doublewrite Buffer (InnoDB) or log full-page images to WAL (Postgres full_page_writes = on), doubling disk write overhead!

The LSM-Tree Axiom: Append-Only Immutable Runs

The LSM-Tree completely discards in-place updates.

Instead of modifying pages on disk:

1. Writes are strictly sequential: Every insert, update, or delete is written sequentially to an append-only in-memory buffer (MemTable) and backed by an append-only disk log (Write-Ahead Log).
2. Deletes are represented as Tombstones: A deletion does not physically erase data immediately; it inserts a special deletion marker called a Tombstone for that key.
3. Flushes produce Immutable Files: When the in-memory buffer reaches capacity, it is flushed sequentially to disk as an immutable Sorted String Table (SSTable).
4. Asynchronous Reconciliation: Reconciliation of duplicate updates and tombstone deletions is completely offloaded to asynchronous background worker threads via Compaction.

By converting all random writes into high-bandwidth sequential stream writes, LSM-Trees achieve near-theoretical maximum write throughput on both NVMe SSDs and spinning disks.

---

2. The In-Memory Ingestion Pipeline: WAL & MemTable

Let us trace the lifecycle of a write request (PUT key, value) inside an LSM-Tree engine (e.g., RocksDB).

The Write-Ahead Log (WAL) & Group Commits

Because the MemTable resides in volatile RAM, any power loss or kernel panic would cause data loss unless changes are durably recorded.

Before any key-value pair is inserted into the MemTable:

1. It is appended to the active Write-Ahead Log (WAL) file on disk.
2. The log entry contains a header (CRC32 checksum, record length, entry type: PUT, DELETE, MERGE, RANGE_DELETE), the sequence number ($SeqNum$), the key, and the value.

Group Commit & Sync Flags

Calling fsync() on every single write imposes severe latency penalties ($1\text{ms}-10\text{ms}$). High-performance LSM engines utilize Group Commits:

• Multiple concurrent client write threads queue their requests in a lock-free ring buffer.
• The leading thread (the leader) collects all batched requests from the queue, performs a single unified write() syscall, issues a single fdatasync(), and notifies all waiting follower threads.
• If the application opts for sync = false, the OS page cache buffers the writes, trading a tiny crash-vulnerability window for millions of operations per second.

---

The MemTable: Why SkipLists Rule Database Internals

The MemTable must fulfill three stringent requirements:

1. Constant Sorting: Keys must be maintained in strictly sorted lexicographical order so they can be flushed to disk as an SSTable without needing an expensive sort phase.
2. Concurrent Reads and Writes: Ingestion threads must insert keys while reader threads scan the data concurrently without coarse-grained mutex locking.
3. Predictable $\mathcal{O}(\log N)$ Performance: Low latency for point lookups, insertions, and range scans.

Why Not a Self-Balancing Binary Search Tree (Red-Black or AVL Tree)?

In a Red-Black or AVL tree, an insertion often triggers recursive tree rotations. In a concurrent multi-threaded environment, rotating nodes alters pointers across multiple levels of the tree hierarchy. This necessitates locking large subtrees or using complex latch-crabbing protocols, destroying multi-core concurrency scaling.

The SkipList: Probabilistic Balancing with Lock-Free Read Concurrency

A SkipList (invented by William Pugh in 1990) is a probabilistic, multi-level linked list that delivers $\mathcal{O}(\log N)$ search, insertion, and deletion without ever needing tree rotations.

In a SkipList:

• Every node is assigned a random height $h$ based on a geometric distribution with probability $p$ (typically $p=1/2$ or $p=1/4$). The probability that a node has height $k$ is $p^{k-1}$.
• Searching begins at the highest level of the Head sentinel node. The search moves forward along the current level until the next key is greater than the target; it then drops down one level and resumes moving forward.
• Lock-Free Concurrency: Inserting a new node only requires updating forward pointers at each level using atomic Compare-And-Swap (CAS) primitives or memory barriers. Readers can traverse the list completely lock-free, reading consistent pointer snapshots without acquiring a single lock or mutex!

---

3. On-Disk SSTable Binary Layout Anatomy

When an immutable MemTable is flushed to disk, it is written as a self-contained, immutable Sorted String Table (SSTable) file (typically named <file_number>.sst or <file_number>.ldb).

An SSTable is designed to allow fast binary searches over sorted key-value pairs while maximizing compression efficiency and minimizing disk read amplification.

1. Data Blocks & Prefix Compression (Delta Encoding)

Within each Data Block, keys are stored in sorted order. Because database keys often share long common prefixes (e.g., user:1001:profile, user:1001:settings, user:1001:timeline), storing full keys repeatedly wastes massive amounts of memory and disk space.

LSM engines employ Prefix Delta Compression:

• Every key is split into:
  1. shared_len: Number of bytes shared with the immediately preceding key.
  2. unshared_len: Number of unique suffix bytes.
  3. value_len: Length of the value payload.
  4. key_delta: The actual unshared key bytes.
  5. value: The raw value bytes.

Restart Points & Binary Search

Because delta-compressed keys cannot be decoded without reading all preceding keys from the start of the block, doing a binary search across every key would require scanning from byte zero.

To solve this, the engine establishes Restart Points every $K$ keys (typically $K=16$):

• At each restart point, delta compression is reset, and the full key is written (shared_len = 0).
• An array of 32-bit offsets pointing to all restart points is stored at the very end of the Data Block.
• To find a key inside a Data Block, the engine performs a binary search across the restart points, jumps directly to the nearest restart offset, and only scans sequentially through at most $K-1$ delta-encoded records.

---

2. The Index Block: Two-Level Indexing

The Index Block maps keys to the physical file offsets and sizes of individual Data Blocks:

• For every Data Block $i$, the Index Block contains a key $K_{sep}$ such that $K_{sep}$ is $\ge$ the highest key in Data Block $i$ and $<$ the lowest key in Data Block $i+1$.
• The value associated with $K_{sep}$ is a BlockHandle consisting of:
  • offset: The starting byte position of the block in the file (varint64).
  • size: The byte length of the block (varint64).

When an SSTable grows to gigabytes, the Index Block itself is partitioned into a Two-Level Index to ensure the primary root index fits permanently in CPU L1/L2 cache.

---

3. The Footer: The SSTable Anchor

When opening an SSTable file, the storage engine reads the last 48 bytes of the file—the Footer:

1. The engine checks the 8-byte Magic Number (in RocksDB: 0xdb4775248b80fb57ULL) to verify file integrity and engine format compatibility.
2. It decodes the Index Handle BlockHandle to locate the Index Block on disk.
3. It decodes the Metaindex Handle to locate the Filter Block (Bloom Filter) and Properties Block.
4. With these handles cached in RAM, the engine can execute point reads and range scans without reading the entire file into memory.

---

4. The Read Path, Bloom Filters & Point/Range Lookups

Because an LSM-Tree does not update data in place, a specific key might exist in the active MemTable, an immutable MemTable, or any of the hundreds of SSTables spread across multiple levels on disk.

The Read Penalty (Read Amplification)

In a worst-case scenario where a requested key does not exist in the database (a negative point lookup), a naive LSM engine would be forced to open and search every single SSTable file on disk. This is known as Read Amplification ($RA$): the ratio of physical bytes read from disk to the logical bytes requested by the application.

To make LSM read latency competitive with B+ Trees, two fundamental optimization layers are deployed: Bloom Filters and the Block Cache.

---

Bloom Filters: Mathematical Foundations & Space Tuning

A Bloom Filter is a space-efficient probabilistic data structure used to test set membership. It provides a definitive guarantee:

• Negative Result: The key is guaranteed NOT to be in the SSTable. The engine completely skips reading the file from disk.
• Positive Result: The key might be in the SSTable (with a tunable false positive probability $p$). The engine proceeds to read the SSTable index and data blocks.

Mathematical Proof of False Positive Probability

Given:

• $m$: Number of bits in the filter array.
• $n$: Number of keys inserted into the filter.
• $k$: Number of independent hash functions.

After inserting $n$ keys, the probability that a specific bit is still $0$ is: $P(\text{bit}=0)={\left(1-\frac{1}{m}\right)}^{kn}\approx e^{-\frac{kn}{m}}$

Therefore, the probability that a bit is $1$ is $1-e^{-\frac{kn}{m}}$. For a query on a key that is not in the set, the probability that all $k$ hash locations are set to $1$ (a False Positive) is: $p={\left(1-e^{-\frac{kn}{m}}\right)}^k$

To minimize $p$ for a given ratio of bits-per-key ($\frac{m}{n}$), we take the derivative with respect to $k$ and set it to $0$, yielding the optimal number of hash functions: $k_{\text{opt}}=\frac{m}{n}\ln 2\approx 0.693\cdot \frac{m}{n}$

Substituting $k_{\text{opt}}$ back into the probability formula: $p=2^{-k_{\text{opt}}}\approx {\left(\frac{1}{2}\right)}^{\frac{m}{n}\ln 2}\approx (0.6185{)}^{\frac{m}{n}}$

With just 10 bits per key in RAM, over 99% of unnecessary disk I/O operations are eliminated during point lookups!

---

Range Queries: Multi-Way Merge Iterators

While Bloom filters optimize point lookups (GET), they cannot assist with Range Queries (SCAN [key_start, key_end]), because a hash function destroys key ordering.

To execute a range scan across an LSM-Tree:

1. The engine constructs a Merging Iterator wrapping an internal Min-Heap (Priority Queue).
2. An individual sorted iterator is opened on the active MemTable, all immutable MemTables, and every overlapping SSTable file across all levels.
3. The smallest key is popped from the top of the Min-Heap.
4. Deduplication & Shadowing: If the same key appears in multiple iterators (e.g., an updated value in MemTable and an older value in Level 2), the Min-Heap yields the version with the highest Sequence Number ($SeqNum$) and advances the older iterators without emitting stale data.
5. Tombstone Processing: If the newest version is a Tombstone, the key is omitted from the result set.

---

5. Compaction Strategies Deep Dive

As writes continue, thousands of immutable SSTables accumulate on disk. Without intervention:

1. Disk space would fill with obsolete row versions and deleted tombstone records.
2. Read amplification would skyrocket, as queries would have to search across thousands of files.

Compaction is the background engine process that reads multiple SSTables, performs a merge-sort, eliminates overwritten keys and expired tombstones, and writes out fresh, densely packed SSTables.

There are two primary compaction paradigms: Size-Tiered Compaction and Leveled Compaction.

---

Size-Tiered Compaction Strategy (STCS)

Commonly used in Apache Cassandra and ScyllaDB, Size-Tiered Compaction groups SSTables into "tiers" based on file size.

How It Works:

1. When several SSTables of roughly equal size (e.g., four 100MB files) accumulate in a tier, a background thread merges them into a single larger SSTable (one 400MB file).
2. As multiple 400MB files accumulate, they are merged into a 1.6GB file, and so forth.

Architectural Trade-offs:

• Low Write Amplification: Fast merge passes with minimal intermediate write steps. Ideal for write-heavy append-only telemetry or time-series logging.
• Severe Space Amplification ($SA$): During a major compaction of a 500GB tier, the engine must write a new 500GB file before deleting the old files. The database requires 50% or more free disk headroom just to execute compactions!
• High Read Amplification: Because keys in the same tier are not partitioned into disjoint ranges, a single key could exist in any SSTable within that tier.

---

Leveled Compaction Strategy (LCS)

Pioneered by Google's LevelDB and perfected by Meta's RocksDB, Leveled Compaction organizes disk storage into discrete, exponentially sized levels ($L_0,L_1,L_2,\dots ,L_k$).

Invariant Rules of Leveled Compaction:

1. Level Sizing Factor ($T$): Each level has a fixed maximum aggregate capacity that grows exponentially by a factor $T$ (typically $T=10$). $\text{Cap}(L_1)=256\text{MB},\text{Cap}(L_2)=2.56\text{GB},\text{Cap}(L_3)=25.6\text{GB},\text{Cap}(L_4)=256\text{GB}$
2. Level 0 Exception: $L_0$ contains raw flushes directly from the MemTable. SSTables in $L_0$ have overlapping key ranges.
3. Disjoint Key Invariant ($L_1\dots L_k$): In every level $i\ge 1$, all SSTables have strictly disjoint, non-overlapping key ranges! $\text{MaxKey}({\text{SST}}_j)<\text{MinKey}({\text{SST}}_{j+1})$

The Leveled Compaction Merge Step:

When Level $i$ exceeds its configured byte capacity:

1. The compaction thread selects one SSTable from Level $i$.
2. It identifies all SSTables in Level $i+1$ whose key ranges overlap with the chosen file.
3. It performs a streaming $k$-way merge sort across these files.
4. It writes new 64MB SSTables into Level $i+1$, ensuring the disjoint key invariant is maintained, and atomically unlinks the old input files.

Architectural Trade-offs:

• Guaranteed Low Space Amplification ($SA\approx 1.1-1.2$): Because each level is 10x larger than the previous one, over 90% of the entire database's data resides in the highest level ($L_{\text{max}}$). Temporary space required for compaction is bounded by a single level's files ($\le 10\%-20\%$).
• Bound Read Amplification: For any point query on Level $i\ge 1$, the engine only needs to check at most one SSTable per level (using a binary search over the level's file metadata index).
• Higher Write Amplification ($WA\approx 10-30$): A single key may be read and rewritten to disk multiple times as it migrates from $L_0$ down to $L_k$.

---

6. The RUM Conjecture & Amplification Metrics

In database systems engineering, there is no silver bullet. Storage engine architectures are bound by the RUM Conjecture (formulated by Manos Athanassoulis et al. in 2016).

The RUM Conjecture: When designing a storage engine access method, optimizing for any two of the three fundamental dimensions—Read Overhead ($R$), Update/Write Overhead ($U$), and Memory/Space Overhead ($M$)—inevitably degrades the third.

---

The Three Fundamental Amplification Metrics

1. Write Amplification Factor ($WAF$)

The ratio of total bytes written to non-volatile storage relative to the logical bytes written by the user application: $\text{WAF}=\frac{\text{Bytes Written to Disk (WAL + Flush + Compaction)}}{\text{Logical User Bytes Ingested}}$

• In a B+ Tree updating random keys on 16KB pages: ${\text{WAF}}_{\text{B-Tree}}\approx \frac{16\text{KB Page Write}\times 2(\text{Doublewrite})}{100\text{ Byte Payload}}\approx 320\times$
• In a Leveled LSM-Tree with growth factor $T=10$ and $L$ levels: ${\text{WAF}}_{\text{LSM-Leveled}}\approx 1(\text{WAL})+1(\text{Flush})+T\cdot L\approx 15\times -30\times$

---

2. Space Amplification Factor ($SAF$)

The ratio of physical disk space occupied by the database files to the actual raw size of the latest, uncompressed live data: $\text{SAF}=\frac{\text{Physical Disk Space Consumed}}{\text{Size of Live Data}}$

• B+ Trees: Suffer from page fragmentation (internal page fill factor is typically $67\%-75\%$), leading to $\text{SAF}\approx 1.33-1.50$.
• Leveled LSM-Trees: SSTables are 100% densely packed and block-compressed with ZSTD or Snappy. Inactive versions in lower levels account for $\le 10\%$, leading to $\text{SAF}\approx 1.10-1.20$.
• Size-Tiered LSM-Trees: Stale overwritten data across tiers can cause $\text{SAF}\ge 2.0-3.0$.

---

3. Read Amplification Factor ($RAF$)

The ratio of physical bytes read from disk per logical byte retrieved by the application: $\text{RAF}=\frac{\text{Physical Bytes Read from Disk}}{\text{Logical User Bytes Returned}}$

• B+ Trees: Excellent for point queries. Following $H={\log }_{B}N$ tree levels (where root and internal nodes are cached in the Buffer Pool) requires reading exactly one 8KB/16KB leaf page from disk.
• LSM-Trees: Must probe the active MemTable, immutable MemTables, multiple $L_0$ SSTables, and up to one SSTable per level $L_1\dots L_k$. Without Bloom filters, $\text{RAF}$ can exceed $50\times$. With 10 bits/key Bloom filters, effective point lookup $\text{RAF}$ drops to near $1.0\times -1.05\times$.

---

Comparative Architecture Matrix

---

7. Production Failure Modes, Edge Cases & Performance Tuning

Running LSM-based storage engines at scale introduces distinct operational and architectural challenges that do not exist in B-Tree systems.

1. Write Stalls & Ingestion Backpressure

In high-throughput write workloads, client ingestion can easily outpace the I/O bandwidth of background compaction worker threads.

If writes continue unchecked:

1. $L_0$ files multiply into hundreds of overlapping SSTables.
2. Read latency degrades catastrophically because every point lookup must evaluate every single $L_0$ file.
3. The engine runs out of memory buffers.

The RocksDB Backpressure Algorithm

To protect system stability, the storage engine dynamically injects artificial micro-delays (write stalls) into client threads:

---

2. Tombstone Saturation & The Range Scan Penalty

A common misconception is that deleting data in an LSM-Tree frees up resources. In reality, a DELETE is an insert of a Tombstone record.

The Problem:

Imagine a table containing 10,000,000 keys where keys $1$ to $9,000,000$ are deleted.

• A range scan executing SCAN [1, 10000000] LIMIT 10 must iterate through all 9,000,000 tombstones, evaluating each one in the Min-Heap merge iterator to verify no older version exists in lower levels.
• This can turn a sub-millisecond query into a multi-second CPU-bound loop!

Mitigations:

1. Range Deletion Tombstones (DeleteRange): Instead of inserting millions of individual point tombstones, engines write a single DeleteRange(K_start, K_end) marker stored in a dedicated SSTable metadata sub-block.
2. Compaction Filters: Custom application hooks (e.g., RocksDB CompactionFilter) that inspect and purge expired TTL keys directly during compaction before they reach lower levels.

---

3. Block Cache Contention & Kernel Page Cache Double-Buffering

LSM engines utilize an uncompressed user-space Block Cache (storing hot uncompressed 4KB data blocks in RAM) alongside the OS Kernel Page Cache (which buffers raw compressed SSTable file blocks).

The Fix: Direct I/O (O_DIRECT)

By configuring use_direct_reads = true and use_direct_io_for_flush_and_compaction = true, the engine bypasses the OS page cache entirely, eliminating redundant memory buffering and preventing background compaction reads from evicting hot user-space cached blocks.

---

8. Summary & Architectural Decision Framework

Choosing between a B+ Tree and an LSM-Tree storage engine comes down to the fundamental mechanical characteristics of your workload:

Executive Summary Checklist

1. Write Performance & Flash Endurance: LSM-Trees convert random write patterns into high-throughput sequential writes, dramatically reducing write amplification and extending the hardware lifespan of enterprise NVMe SSDs.
2. Read Complexity: B+ Trees excel at point reads and sequential leaf scans with zero read amplification. LSM-Trees require layered Bloom filters, Block caches, and $k$-way merge iterators to achieve competitive read latencies.
3. Space Efficiency: Through dense block compression and Leveled Compaction, LSM-Trees achieve space amplification factors near $1.15\times$, compared to $1.4\times -1.6\times$ for fragmented B+ Trees.
4. Engineering Reality: Modern storage engines like RocksDB bridge the gap using sophisticated engineering: Ribbon filters, two-level indexes, prefix delta compression, and dynamic write-stall backpressure algorithms.

---

Interactive InitNode Challenge

Test your mastery of storage engine internals with this architectural problem:

Scenario: You are architecting a distributed metrics platform that ingests $2,000,000$ metric updates per second. Each metric key is formatted as sensor:<tenant_id>:<timestamp>:<metric_id>.

1. Which compaction strategy (Leveled vs. Size-Tiered vs. FIFO) would you select if disk space is cheap but ingestion rate is the absolute bottleneck?
2. Why does prefix delta compression in SSTable data blocks provide an asymmetric compression advantage for this key schema?
3. If you run a query for sensor:tenantA:2026-09-01:*, why does a standard Bloom filter fail to help, and what index structure in the SSTable handles this scan?

(Explore and discuss your solution in the InitNode community forum or build a prototype in the InitNode Arena!)