B-Tree vs LSM-Tree Storage: Which Should You Choose?
Compare B-tree and LSM-tree storage engines — read vs write amplification, real systems, and how to choose for your workload.
Expected Interview Answer
B-trees update data in place with balanced, sorted disk pages that favor fast, low-amplification reads, while LSM-trees buffer writes in memory and flush them as immutable sorted files merged later by compaction, favoring high write throughput at the cost of extra read and space amplification, so the right choice depends on whether the workload is read-heavy or write-heavy.
A B-tree stores keys in sorted, fixed-size pages arranged in a balanced tree, and every update finds and rewrites the relevant leaf page in place, which means a point read typically only needs to walk a few pages from root to leaf, giving low, predictable read amplification. The cost is that writes involve random-access page rewrites and possible page splits, which is slower on spinning disks and adds write amplification on flash storage due to how SSDs handle small overwrites. An LSM-tree instead appends every write sequentially to an in-memory buffer and a log, flushing to immutable sorted files and merging them later, which makes writes extremely fast and sequential but means a read may need to check several files, and stale/deleted data lingers until compaction, raising read and space amplification. In practice, B-trees suit read-heavy, transactional workloads like OLTP with strong point-query needs (e.g., PostgreSQL, MySQL InnoDB), while LSM-trees suit write-heavy workloads like logging, metrics, and event ingestion (e.g., Cassandra, RocksDB, HBase) — and some systems even offer both as pluggable storage engines.
- B-trees give predictable, low-latency point reads and in-place updates for transactional workloads
- LSM-trees give very high sustained write throughput by converting random writes into sequential I/O
- Choosing correctly avoids paying unnecessary read or write amplification for the actual workload shape
- Understanding both lets engineers reason about real systems like InnoDB, RocksDB, and Cassandra by their underlying trade-offs
AI Mentor Explanation
A B-tree is like a fully organized, alphabetized scorecard filing cabinet where updating one player’s entry means walking straight to their exact folder and correcting it in place — quick to look up, but slower to file corrections during a fast-paced match. An LSM-tree is like a scorer scribbling every update on a running scratch pad and only filing a proper cabinet update once an over ends, which keeps up with rapid play but means looking up a player’s latest score might require checking the scratch pad plus several recent filings. A team recording a slow Test match favors the cabinet; a scorer covering a rapid T20 favors the scratch pad.
Step-by-Step Explanation
Step 1
Characterize the read/write mix
A workload with far more writes than reads (logging, ingestion) leans LSM-tree; one with frequent point reads and moderate writes (OLTP) leans B-tree.
Step 2
Consider update pattern
In-place updates to existing records favor a B-tree; append-heavy, immutable-event workloads favor an LSM-tree.
Step 3
Weigh amplification trade-offs
B-trees keep read/space amplification low but pay write amplification on random updates; LSM-trees keep writes cheap but pay read/space amplification until compaction.
Step 4
Check the engine, not just the database name
Some databases are pluggable (e.g., MySQL supports InnoDB/B-tree or MyRocks/LSM), so the decision is about storage engine choice, not just product choice.
What Interviewer Expects
- Correctly frames the trade-off as write-optimized (LSM) vs read-optimized/in-place (B-tree)
- Explains why B-tree writes are random I/O and LSM writes are sequential
- Mentions concrete amplification differences: read/space amplification for LSM, write amplification for B-tree on random updates
- Names real engines: InnoDB/Postgres heap (B-tree) vs RocksDB/Cassandra/HBase (LSM)
Common Mistakes
- Claiming one is strictly “better” instead of workload-dependent
- Ignoring compaction and its read/space amplification cost when praising LSM-trees
- Ignoring page splits and random I/O cost when praising B-trees for writes
- Not mentioning that some databases offer both as pluggable storage engines
Best Answer (HR Friendly)
“B-trees and LSM-trees are two different ways databases organize data on disk. B-trees update records in place, which makes reading data fast and predictable but can slow down under heavy write load. LSM-trees buffer writes and add them in big batches, which makes writing extremely fast but means reads sometimes have to check more than one place. The right choice depends on whether your system does a lot more reading or a lot more writing.”
Code Example
workloads:
oltp_orders_service:
read_write_ratio: "9:1" # read-heavy, point lookups
engine: btree # e.g. PostgreSQL heap+btree, MySQL InnoDB
rationale: "Low, predictable read amplification for point queries"
event_ingestion_pipeline:
read_write_ratio: "1:20" # write-heavy, append-only events
engine: lsm_tree # e.g. RocksDB, Cassandra, HBase
rationale: "Sequential writes absorb high ingest rate; reads are rare/batched"
hybrid_analytics_store:
read_write_ratio: "3:1"
engine: lsm_tree_with_leveled_compaction
rationale: "Leveled compaction bounds read amplification for moderate reads"Follow-up Questions
- Why does a B-tree page split cause a burst of random writes, and how does that affect write amplification?
- How does leveled compaction let an LSM-tree approximate B-tree-like read amplification at the cost of more write I/O?
- What is MyRocks, and why would a team choose it over InnoDB for a MySQL-compatible workload?
- How would range scans compare between a B-tree and an LSM-tree with sorted SSTables?
MCQ Practice
1. Which storage structure updates data in place and generally gives lower, more predictable read amplification?
B-trees rewrite the relevant leaf page in place, so a point read walks a small, bounded number of pages from root to leaf.
2. Why are LSM-tree writes generally faster than B-tree writes under heavy write load?
LSM-trees convert writes into sequential appends, while B-trees must locate and rewrite (and sometimes split) the specific page for each update.
3. Which pairing correctly matches a real system to its underlying storage structure?
PostgreSQL and InnoDB use B-tree indexes with in-place page updates, while RocksDB (and Cassandra, HBase) are LSM-tree based.
Flash Cards
B-tree strength? — Low, predictable read amplification via in-place, balanced sorted pages — great for read-heavy OLTP.
LSM-tree strength? — Very high write throughput via sequential appends to memory and log, merged later by compaction.
B-tree weakness? — Random-access page rewrites and possible splits make heavy write load slower and add write amplification.
LSM-tree weakness? — Reads may check multiple files (read amplification) and stale/deleted data lingers until compaction (space amplification).