B-tree vs LSM-tree Storage

TL;DR. B-trees optimize reads with predictable 3-5 page I/O lookups and pay with 5-10x write amplification from whole-page rewrites¹. LSM-trees optimize writes with sequential batched flushes and pay with 10-30x write amplification from compaction plus read-path overhead across multiple sorted levels². Pick B-tree when your read:write ratio exceeds 10:1 and p99 read latency is a hard SLO. Pick LSM when writes dominate and you can tolerate compaction-driven latency variance. The deciding dimension is read:write ratio.

Learning Objectives

• Compare B-tree and LSM-tree across read amplification, write amplification, space amplification, and tail latency.
• Identify workload characteristics (read:write ratio, value size, delete frequency) that favor one engine over the other.
• Justify a hybrid approach (key-value separation, per-collection engine choice) for mixed workloads.
• Evaluate Facebook MyRocks, CockroachDB Pebble, and Cassandra compaction strategies as production decision examples.

The Core Trade-off

The RUM conjecture (Athanassoulis et al., EDBT 2016) frames the tension precisely: for any access method, optimizing two of Read overhead, Update overhead, and Memory/space overhead forces the third to be large³. B-trees sit near the Read corner: a point lookup walks 3-4 levels of an 8 KB page tree regardless of dataset size⁴, but every 50-byte update rewrites an entire page plus WAL. LSM-trees sit near the Update corner: writes are sequential and batched into memtable flushes, but reads must probe multiple sorted levels and compaction rewrites data 10-30x²⁵.

The metric that moves in opposite directions is I/O pattern. B-trees issue random writes (dirty pages flushed to arbitrary disk locations) but random reads are fast (one tree walk). LSM-trees issue sequential writes (append-only flushes) but reads fan out across levels. On flash storage, sequential writes extend SSD lifespan; random page rewrites burn write cycles on unchanged bytes.

flowchart LR
    subgraph "RUM Triangle"
        R["Read optimized<br/>B-tree: InnoDB, Postgres"]
        U["Update optimized<br/>LSM leveled: RocksDB"]
        M["Memory/space optimized<br/>LSM tiered: STCS"]
    end
    R -.->|"low read amp<br/>high write amp"| U
    U -.->|"low write amp<br/>high space amp"| M
    M -.->|"RUM conjecture:<br/>pick 2, pay the 3rd"| R

Side-by-Side Comparison

The table understates one dimension: operational surprise. B-tree databases have predictable behavior under load because updates happen in place. LSM databases have a background process (compaction) that competes with foreground reads for I/O and CPU. When compaction falls behind, writes stall⁷. This is the single biggest operational difference in practice.

Range scans are the other hidden gap. In PostgreSQL and InnoDB, B-tree leaf pages are doubly linked; a range scan is a sequential walk. LSM range scans must merge iterators across every level because bloom filters only help point lookups⁹.

When to Pick B-tree

Read-dominated OLTP with hard p99 SLOs. Web applications where the read:write ratio exceeds 10:1. User lookups, order history, session retrieval. PostgreSQL and InnoDB handle these with 3-4 page I/Os regardless of table size⁴¹⁰.

Workloads with frequent range scans. Reporting queries, pagination, time-range filters over indexed columns. B-tree leaf traversal is sequential; LSM must merge across levels.

Teams without compaction expertise. B-tree operational tooling is mature: VACUUM, pg_repack, InnoDB buffer pool tuning, online index rebuilds. The failure modes are well-documented and recoverable.

Small-to-medium datasets (under 1 TB) on provisioned IOPS. When storage is not the bottleneck, B-tree’s simpler architecture wins on debuggability and predictability.

Named systems: PostgreSQL, MySQL/InnoDB, SQLite, Oracle, SQL Server.

When to Pick LSM-tree

Write-heavy ingestion where throughput ceiling matters. Time-series, event sourcing, log aggregation, IoT telemetry. LSM sustains up to 10x or more the write rate of B-tree on the same flash¹¹¹.

Space-constrained environments where compression efficiency matters. MyRocks achieved 2x smaller on-disk size than compressed InnoDB because SSTables are not page-aligned: a block that compresses to 5 KB uses exactly 5 KB¹. Facebook cut UDB instance sizes by 62.3% migrating from InnoDB to MyRocks¹².

Append-mostly workloads with few updates or deletes. Chat messages, social-feed events, blockchain state. Tombstone accumulation is minimal when deletes are rare.

SSD-lifetime-sensitive deployments. Sequential writes reduce flash wear even when write amplification is numerically higher, because the SSD controller handles sequential patterns more efficiently than random page rewrites¹.

Named systems: RocksDB, LevelDB, Cassandra, ScyllaDB, CockroachDB (Pebble), TiKV, BadgerDB.

The Hybrid Path

Most production systems do not pick one engine for everything. The practical hybrid strategies:

Key-value separation (WiscKey). Store keys in the LSM but large values in a separate append-only value log. Compaction rewrites only keys (small), cutting compaction cost 2.5-111x versus LevelDB for large-value workloads¹³. BadgerDB and TitanDB implement this in production.

Per-collection engine selection. MongoDB’s WiredTiger supports both B-tree and LSM per collection. In practice, the LSM mode is rarely used because WiredTiger’s B-tree already uses compression and write-ahead logging. The hybrid option exists but “pick one engine” remains the right default.

Tiered compaction for writes, leveled for reads. Cassandra 5.0’s Unified Compaction Strategy (UCS) adapts between tiered and leveled behavior behind a single scaling_parameters knob, eliminating the need to choose upfront¹⁴¹⁵.

flowchart TD
    subgraph "Hybrid: Key-Value Separation"
        Write["PUT(key, large_value)"]
        LSM["LSM index<br/>keys + value pointers"]
        VLog["Value log<br/>append-only"]
        Write --> LSM
        Write --> VLog
        Read["GET(key)"]
        Read --> LSM
        LSM -->|"pointer"| VLog
    end

Real-World Examples

Facebook MyRocks (2016-present). Facebook migrated their User Database (UDB) from compressed InnoDB to MyRocks (RocksDB as a MySQL storage engine). Result: 50% storage savings in one region, 62.3% smaller instances overall, and “orders of magnitude” less flash write I/O¹¹². The motivation was space, not speed: internal SSDs were capacity-bound, not IOPS-bound¹⁶. They enabled “read-free replication” so secondaries skip the random read that InnoDB requires for secondary-index updates.

CockroachDB Pebble (2020-present). CockroachDB replaced RocksDB with Pebble, a from-scratch Go LSM (~45K LOC vs RocksDB’s ~350K LOC)¹⁷. Pebble implements L0 sublevels for concurrent compaction out of L0, reducing write-stall frequency. On YCSB workload C (100% reads), Pebble outperforms RocksDB due to better block-cache concurrency¹⁷.

Discord’s Cassandra-to-ScyllaDB migration. Discord’s trillions-of-messages workload exposed multiple Cassandra pain points: hot partitions, compaction backlogs, and JVM GC pauses that forced on-call operators to manually reboot nodes. Tombstones that were never compacted away even stalled the final migration step at 99.9999% until the affected token range was force-compacted⁸. The fix was not a single knob: Discord moved to ScyllaDB (C++, shard-per-core, no GC) and put Rust data services in front of the database to coalesce duplicate reads via consistent hash-based routing. Fetching historical messages went from p99 40-125 ms on Cassandra to a steady 15 ms on ScyllaDB; inserts went from p99 5-70 ms to a steady 5 ms. The cluster shrank from 177 Cassandra nodes to 72 ScyllaDB nodes⁸.

Common Mistakes

Decision Checklist

• Is the read:write ratio above 10:1? If yes, B-tree.
• Is p99 read latency a hard SLO that cannot tolerate compaction spikes? If yes, B-tree.
• Does the workload sustain more than 50K writes/sec per node? If yes, LSM.
• Is on-disk size the binding constraint (space-bound, not IOPS-bound)? If yes, LSM.
• Are deletes frequent (>10% of operations)? If yes, B-tree or LSM with TWCS/TTL.
• Does the team have compaction-tuning expertise? If no, B-tree is operationally safer.
• Are values large (>1 KB)? If yes, consider key-value separation (WiscKey/Titan).

flowchart TD
    Start{"Read:write ratio?"}
    Start -->|">10:1 reads"| BTree["B-tree<br/>PostgreSQL, InnoDB"]
    Start -->|"<1:5 write-heavy"| LSM["LSM-tree<br/>RocksDB, Cassandra"]
    Start -->|"mixed 1:1 to 10:1"| Q2{"Hard p99 read SLO?"}
    Q2 -->|"yes"| BTree
    Q2 -->|"no, throughput matters"| Q3{"Space-bound?"}
    Q3 -->|"yes"| LSM
    Q3 -->|"no"| Q4{"Team has LSM ops experience?"}
    Q4 -->|"yes"| LSM
    Q4 -->|"no"| BTree

Key Takeaways

• B-tree for reads, LSM for writes. The read:write ratio is the single strongest signal for engine selection.
• Write amplification is the hidden cost of both engines: B-tree pays 5-10x from page rewrites, LSM pays 10-30x from compaction. Neither is free.
• LSM operational complexity is real: compaction stalls, tombstone accumulation, and L0 backpressure are production emergencies that B-tree databases do not have.
• Facebook saved 50% storage by moving to LSM (MyRocks) because their workload was space-bound, not IOPS-bound¹. Know your binding constraint before choosing.
• The RUM conjecture guarantees no engine wins on all three axes. Accept the trade-off consciously.

Further Reading

• Facebook Engineering, “MyRocks: A space- and write-optimized MySQL database”: the canonical production migration story; 50% storage savings, orders-of-magnitude less flash I/O.
• Athanassoulis et al., “Designing Access Methods: The RUM Conjecture”, EDBT 2016: the theoretical framework for understanding why no storage engine can optimize all three axes simultaneously.
• RocksDB Wiki: Leveled Compaction: authoritative reference for the default RocksDB compaction strategy, write amplification math, and tuning knobs.
• Lu et al., “WiscKey: Separating Keys from Values in SSD-conscious Storage”, FAST 2016: key-value separation that cuts compaction cost 2.5-111x for large-value workloads.
• Discord, “How Discord Stores Trillions of Messages”: tombstone accumulation, compaction strategy failure, and the Cassandra-to-ScyllaDB migration.
• Cockroach Labs, “Introducing Pebble”: why CockroachDB rewrote RocksDB in Go; L0 sublevels, concurrent compaction, and 45K LOC vs 350K.

Flashcards

References