Database Indexing: B-Tree vs. Log-Structured Merge-Tree Architectures

At the lowest layer of any database management system lies the storage engine. This component is responsible for translating logical database rows and columns into physical bytes on non-volatile storage (such as NVMe SSDs or mechanical HDDs) and maintaining indexes to query those bytes quickly.

The design of a storage engine is a balancing act of trade-offs. The hardware characteristics of storage media—where sequential disk I/O is orders of magnitude faster than random disk I/O—dictate how data should be written and indexed.

Modern database architectures have coalesced around two primary index structures: B-Trees and Log-Structured Merge-Trees (LSM-Trees). B-Trees are optimized for fast read performance, making them the standard choice for relational databases (like PostgreSQL and MySQL). LSM-Trees are optimized for write throughput, making them the default storage engine for high-volume NoSQL databases (like Cassandra, RocksDB, and ScyllaDB). This systems deep dive analyzes the inner mechanics of both index structures.

---

B-Tree Storage Engine Architecture

Introduced by Rudolf Bayer and Edward M. McCreight in 1972, the B-Tree is a self-balancing search tree optimized for systems reading and writing large blocks of data. Relational databases typically implement B+ Trees, a variant where all user data is stored in the leaf nodes, while internal nodes contain only routing keys.

1. Structure and Routing

A B+ Tree consists of:

• Root Node: The entry point for queries.
• Internal Nodes: Contain pivot keys and child pointers, guiding the search down the tree.
• Leaf Nodes: Contain the actual data rows or pointers to them. These nodes are linked sequentially, allowing fast range queries.

Every node corresponds to a fixed-size block on disk, typically 4KB or 8KB, matching the page size of the underlying operating system and hardware storage.

2. In-Place Updates

B-Trees perform In-Place Updates. When a row is modified, the database retrieves the page containing that row, updates the bytes in memory, and writes the updated page back to its original location on disk. While this makes reads highly efficient (a key lookup requires traversing a constant number of parent-to-child links), updates require random writes, which can introduce write bottlenecks on high-volume write workloads.

---

LSM-Tree Storage Engine Architecture

To overcome the random-write bottleneck of B-Trees, Patrick O’Neil, Edward O’Neil, and Gerhard Weikum designed the Log-Structured Merge-Tree (LSM-Tree) in 1996. The LSM-Tree converts random writes into sequential writes, utilizing the high sequential write performance of SSDs and HDDs.

An LSM-Tree splits the index into memory-resident and disk-resident components:

                            LSM-Tree Write Pipeline
                                       |
    +----------------------------------+----------------------------------+
    |                                                                     |
    v                                                                     v
[ Write-Ahead Log (WAL) ]                                      [ MemTable (RAM) ]
(Sequential Disk Append)                                       (Sorted SkipList)
                                                                          | (Flush)
                                                                          v
                                                               [ SSTables (Disk - L0) ]
                                                               (Immutable Sorted Runs)

1. The MemTable and WAL

When a write request (insert, update, or delete) arrives:

• The raw transaction is appended to a sequential Write-Ahead Log (WAL) on disk to guarantee data durability in case of power loss.
• The record is inserted into the MemTable, a memory-resident sorted data structure (typically implemented as a SkipList).

Because writing to the WAL is sequential and inserting into the MemTable occurs in RAM, write latency is extremely low.

2. SSTable Flushes

When the MemTable reaches its capacity limit (e.g. 64MB), it is converted into an immutable Sorted String Table (SSTable) and flushed sequentially to disk as Level 0 (L0). Because SSTables are immutable, updates do not modify existing files. Instead, new values are appended to new SSTables, and deletes are recorded using a deletion marker called a tombstone.

---

Write Amplification and Disk I/O Mechanics

The sequential-write model of LSM-Trees comes at a cost: Write Amplification. Write Amplification Factor (WAF) is the ratio of bytes written to physical storage compared to the logical bytes written by the application:

WAF = (Bytes Written to Storage) / (Bytes Written by Application)

WAF Comparison

• B-Trees: Updating a single 100-byte row requires writing the entire 8KB page containing that row back to disk, resulting in a high WAF for small, random updates.
• LSM-Trees: During the flush stage, the WAF is low (close to 1.0). However, because multiple SSTables can contain duplicate or deleted records for the same keys, the database must periodically read, merge, and rewrite SSTables to disk during a process called Compaction, which increases the cumulative WAF.

---

Compaction Algorithms in LSM Storage

To reclaim storage space and keep read latency under control, LSM storage engines run background compaction routines using one of two primary algorithms:

1. Size-Tiered Compaction Strategy (STCS)

STCS groups SSTables of similar sizes into tiers. When a tier accumulates a threshold number of files (e.g., four 64MB SSTables), they are merged into a single larger SSTable (e.g., 256MB).

• Pros: Low write amplification during compaction.
• Cons: High transient disk space requirement (requires up to 50% free disk space to compile the merge) and temporary read latency spikes.

2. Leveled Compaction Strategy (LCS)

LCS organizes SSTables into levels (L1, L2, L3, …), where the capacity of each level is 10x larger than the previous one. Each level (except L0) contains non-overlapping keys. When a level exceeds its capacity, an SSTable from that level is merged with overlapping SSTables in the next level.

• Pros: Outstanding read performance and low space overhead.
• Cons: Extremely high write amplification, as data is repeatedly read and rewritten across levels.

---

Comparative Matrix: Read, Write, and Space Trade-offs

The architectural trade-offs of B-Trees and LSM-Trees are summarized in the table below:

Feature	B-Tree (PostgreSQL/MySQL)	LSM-Tree (RocksDB/Cassandra)
Write Throughput	Medium (Random writes)	High (Sequential appends)
Point Read Latency	Low (O(log N) page traversal)	Medium (Must check MemTable + SSTables)
Range Read Latency	Low (Linked leaf nodes)	Medium-High (Requires merge-sort iterator)
Write Amplification	High (Writes entire pages)	High (Driven by repeated compactions)
Space Amplification	Medium (Fragmentation overhead)	High (Duplicate values and tombstones)
Primary Use Case	Transactional (OLTP), Relational	High-volume ingestion, Time-series, NoSQL

To improve point read latency in LSM-Trees, engines use Bloom Filters—probabilistic data structures stored in memory that can quickly determine if an SSTable does not contain a requested key, avoiding unnecessary disk reads.

---

Conclusion & Key Takeaways

Choosing between B-Trees and LSM-Trees depends on the read-to-write ratio of your application’s workload.

• B-Trees: Ideal for read-heavy applications, offering constant point lookup times and efficient range scans.
• LSM-Trees: Ideal for write-heavy applications, transforming random disk updates into sequential appends.
• Optimize with Bloom Filters: For LSM-Trees, ensure Bloom Filters are tuned correctly to minimize point read latency on disk.

---

FAQ

Why are SSTables immutable in LSM-Trees?

Immutability prevents file fragmentation, simplifies concurrency control (multiple threads can read SSTables without locks), and allows sequential write performance on SSDs, as files are written once and never modified in place.

What is a tombstone in LSM-Tree databases?

Because SSTables are immutable, a record cannot be deleted by modifying the file. Instead, the database writes a special marker called a tombstone. During compaction, when the tombstone and the deleted record are merged, both are removed from the index.

How does write amplification affect SSD lifespan?

SSDs have a limited number of Program/Erase (P/E) cycles. High write amplification causes the storage controller to write more data to the flash cells than the application requests, accelerating wear and shortening the lifespan of the SSD.

---

Related Inquiries

• Explore functional programming in concurrent pipelines.
• Learn about API gateway latency in microservices.
• Read our benchmarks on WebAssembly runtime performance.