Storage Engines: LSM vs B-Tree — Simple

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.

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;