Skip to content

Storage Engines: LSM vs B-Tree#

Problem statement (interviewer prompt)

Compare B+ tree (e.g. InnoDB) and LSM tree (e.g. RocksDB) storage engines. Explain why each exists, how writes / reads / range scans behave, and which workloads each is best for. Cover WAL, compaction, and the read/write/space amplification trade-off.

Concept illustration 
flowchart LR
  subgraph BTree[B-Tree - read optimized]
    BR([Reader])
    BP[Page cache]
    BD[(B+ tree on disk<br/>in-place update)]
  end
  subgraph LSM[LSM - write optimized]
    LW[Writer] --> WAL[WAL]
    WAL --> MEM[Memtable]
    MEM -. flush .-> SS[(SSTables<br/>levels)]
    LR[Reader] --> MEM
    LR --> SS
    COMP[Compaction] --> SS
  end
  BR --> BP --> BD

    classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
    classDef edge fill:#cffafe,stroke:#0e7490,stroke-width:1px,color:#0f172a;
    classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
    classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
    classDef cache fill:#fed7aa,stroke:#9a3412,stroke-width:1px,color:#0f172a;
    classDef queue fill:#ede9fe,stroke:#5b21b6,stroke-width:1px,color:#0f172a;
    classDef compute fill:#d1fae5,stroke:#065f46,stroke-width:1px,color:#0f172a;
    classDef storage fill:#e5e7eb,stroke:#374151,stroke-width:1px,color:#0f172a;
    classDef external fill:#fce7f3,stroke:#9d174d,stroke-width:1px,color:#0f172a;
    classDef obs fill:#f3e8ff,stroke:#6b21a8,stroke-width:1px,color:#0f172a;
    class BR,LR client;
    class LW,WAL,COMP service;
    class BD,MEM,SS datastore;
    class BP cache;
B+ tree example with leaf nodes storing all keys linked in sorted order for efficient range scans
B+ tree: internal nodes hold only keys (routing); all values live in linked leaf nodes enabling O(log N) point lookup and O(log N + K) range scans. Source: Grundprinzip, Wikimedia Commons (CC BY 3.0)
flowchart TB
  subgraph Common[Common building blocks]
    WAL[Write-Ahead Log<br/>group commit, fsync]
    PC[Page / Block Cache<br/>buffer pool]
    CKP[Checkpoint / fsync interval]
    REC[Crash recovery<br/>replay WAL]
  end

  subgraph BTree[B+ Tree engine - InnoDB, Postgres heap+btree, BoltDB]
    direction TB
    BTROOT[Root node]
    BTINT[Internal nodes]
    BTLEAF[Leaf pages<br/>sorted, linked]
    BTINS[Insert: locate leaf,<br/>split if full O log n]
    BTGET[Point read O log n,<br/>1-2 disk hops with cache]
    BTSCAN[Range scan via leaf links]
    BTFREE[Free list / FSM]
  end

  subgraph LSM[LSM Tree engine - RocksDB, Cassandra, LevelDB, ScyllaDB]
    direction TB
    LMEM[Memtable<br/>skiplist / rbtree]
    IMMU[Immutable memtable]
    L0[L0 SSTables<br/>overlap possible]
    L1[L1 SSTables<br/>non-overlapping]
    LN[L2...Ln<br/>10x size each]
    BLOOM[Bloom filter per SSTable<br/>avoid disk for missing keys]
    INDEX[Sparse index + summary]
    COMPS[Compaction strategies<br/>size-tiered / leveled / universal]
    TS[Tombstones for deletes]
    SNAP[Snapshot via seqno]
  end

  subgraph Tradeoffs[Read vs Write amplification]
    RA[Read amp: levels touched per read]
    WA[Write amp: bytes rewritten / bytes written]
    SA[Space amp: live / stored]
  end

  WAL --> LMEM
  LMEM -. seal .-> IMMU -. flush .-> L0
  COMPS --> L0
  COMPS --> L1
  COMPS --> LN
  BLOOM --- L0
  BLOOM --- L1
  INDEX --- L1
  TS --- COMPS
  WAL --- BTree
  BTROOT --> BTINT --> BTLEAF
  PC --- BTree
  PC --- LSM
  REC --- WAL
  Tradeoffs --- LSM
  Tradeoffs --- BTree

    classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
    classDef edge fill:#cffafe,stroke:#0e7490,stroke-width:1px,color:#0f172a;
    classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
    classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
    classDef cache fill:#fed7aa,stroke:#9a3412,stroke-width:1px,color:#0f172a;
    classDef queue fill:#ede9fe,stroke:#5b21b6,stroke-width:1px,color:#0f172a;
    classDef compute fill:#d1fae5,stroke:#065f46,stroke-width:1px,color:#0f172a;
    classDef storage fill:#e5e7eb,stroke:#374151,stroke-width:1px,color:#0f172a;
    classDef external fill:#fce7f3,stroke:#9d174d,stroke-width:1px,color:#0f172a;
    classDef obs fill:#f3e8ff,stroke:#6b21a8,stroke-width:1px,color:#0f172a;
    class WAL,CKP,REC,BTROOT,BTINT,BTLEAF,BTINS,BTGET,BTSCAN,BTFREE,LN,INDEX,COMPS,TS,SNAP,RA,WA,SA service;
    class LMEM,IMMU,L0,L1,BLOOM datastore;
    class PC cache;

When each wins#

Property B+ Tree LSM
Write throughput medium (in-place page writes) high (sequential append)
Read latency low, predictable higher tail (multi-level lookup)
Range scan very fast fast (with leveled)
Write amp low high (compaction)
Space amp low higher (multiple copies during compaction)
Concurrency latch-coupling complex simpler (immutable SSTables)
Best for OLTP, mixed write-heavy, log-like, embedded KV

Compaction strategies (LSM)#

  • Size-tiered: merge same-sized SSTables → low write amp, high space amp.
  • Leveled: bounded levels, non-overlapping per level → low space amp, high write amp.
  • Universal / hybrid: tune knobs for workload.

WAL & durability#

  • Group commit batches fsyncs; trade latency for throughput.
  • sync vs async mode (Postgres fsync=off → fast & dangerous).

Read path (LSM)#

  1. Check memtable.
  2. Check immutable memtable.
  3. For each level: bloom filter → SSTable index → block cache → disk.
  4. Merge values, dedupe by seqno, return latest.

Glossary & fundamentals#

Concepts referenced in this design. Each row links to its canonical page; the tag column shows whether it is a high-level (HLD) or low-level (LLD) concept.

Tag Concept What it is Page
HLD LSM vs B-Tree engines WAL, memtable, SSTables, compaction storage-engines-lsm-btree
HLD Probabilistic data structures Bloom, HLL, Count-Min, MinHash, t-digest probabilistic-data-structures
LLD State machines FSM, HSM, transitions, guards state-machines
LLD Testing strategy pyramid, doubles, TDD, contracts testing-strategy
LLD Immutability immutable types, persistent collections immutability

Quick reference#

The fundamental trade-off#

Disk loves sequential IO, hates random. B-trees do in-place updates (random IO on writes); LSMs sequentialize writes via append + later compaction.

Engines in the wild#

Engine Model Used in
InnoDB B+ tree MySQL
Postgres heap + btree heap files + B-tree index Postgres
BoltDB / LMDB mmap'd B+ tree etcd v3, Mongo legacy
RocksDB / LevelDB LSM TiKV, CockroachDB, Kafka Streams, MyRocks
WiredTiger hybrid (B-tree default, LSM opt) MongoDB
Cassandra LSM (custom) Cassandra
ScyllaDB LSM (Seastar) Scylla

Tunable knobs#

  • Block size (4 KB-64 KB).
  • Compression (Snappy, Zstd, LZ4) - trades CPU for IO.
  • Cache size - biggest single performance lever.
  • Bloom filter bits/key (10 = 1% FPR typical).
  • Compaction threads / IO scheduler.

Failures & recovery#

  • WAL fsync absolutely required for ACID-D.
  • On crash: replay WAL into memtable; redo / undo for B-tree.
  • Torn writes → use checksums per page; double-write buffer (InnoDB).

When to choose#

  • Heavy random write, append-mostly, time-series → LSM.
  • Mixed OLTP with strong range and update → B-tree.
  • Tiny embedded need with mmap → LMDB.

Refs#

  • Designing Data-Intensive Applications ch.3.
  • "The Log-Structured Merge-Tree" (O'Neil et al. 1996).
  • RocksDB wiki, ScyllaDB blog series on LSM, Postgres docs.

FAQ#

What is the core difference between LSM and B-tree engines?#

B-trees update pages in place and are read optimized. LSM trees buffer writes in memory and flush sorted runs to disk, then compact them in the background, optimizing for write throughput.

Why does RocksDB use an LSM tree?#

Workloads with heavy writes like time series, queues, and logs benefit from sequential writes to disk. The LSM design also compresses well and is friendly to SSD wear leveling.

What is write amplification?#

The ratio of bytes written to disk versus bytes logically inserted by the user. LSM compaction can write the same data several times across levels, costing IO and SSD endurance.

When should I prefer a B-tree?#

For mixed workloads with frequent point reads and range scans on hot data, or where transactional locking and predictable latency matter more than peak write throughput.

How does compaction work in an LSM engine?#

Background threads merge smaller sorted SSTables into larger ones, drop deleted keys, and keep older versions tidy. Strategies include leveled compaction and size tiered compaction.

  • Database Sharding: the choice of storage engine (LSM vs. B-Tree) affects write amplification and compaction under sharding
  • Caching Strategies: storage engines use in-memory caches (block cache, memtable) as a core performance optimization
  • MVCC and Isolation Levels: storage engines implement MVCC at the page or SSTable level to support concurrent reads and writes

Further reading#

Curated, high-credibility sources for going deeper on this topic.