When would you choose a B-tree storage engine over a log-structured merge engine, and what workload signals point each way?
answer
- update in place vs append
- random vs sequential I/O
- one location vs several files
- background merge cost
- predictable reads vs fast writes
basics
~20 sChoose a B-tree engine for read-heavy work needing predictable point and range latency, since each key has one place. Choose an LSM engine for sustained heavy writes, since it writes sequentially and compresses well, at the cost of reads checking several files and background compaction.
solid answer
~40 sA **B-tree** engine keeps each key in **one place**, a page it updates in place, with a write-ahead log for safety. Reads walk a shallow tree to that page, so point and range reads are **predictable**; writes cost random page I/O, and a small change can rewrite a whole page. An **LSM** engine **appends**: writes go to a log and a memory buffer and reach disk as large sequential sorted files, so write throughput is high and data compresses well without page fragmentation. The price is on reads, which may check several files, and on **background compaction**, which rewrites data and competes for I/O. So: read-heavy, update-in-place, latency-sensitive transactional work leans B-tree; write-heavy ingestion, time-series and append-mostly data at scale leans LSM. Benchmark your own workload; the gap depends heavily on it.
go deeper
Know that B-trees update pages in place while LSM engines append and merge, and which one favours writes.
Compare the two across write pattern, read cost, space and background work, and map workloads to each.
Explain latency behaviour under load, including compaction stalls, and design a benchmark that reflects the real workload.
Be ready to choose an engine for a system and defend it in terms of amplification, latency predictability and operating cost.
## Two ways to keep sorted data on disk Both engines keep keys sorted so that point lookups and range scans are efficient. They differ in **how they absorb change**. - **B-tree** (in practice a B+tree): data lives in fixed-size pages arranged as a shallow tree. A write finds the leaf page for its key and **modifies it in place**, splitting pages when they fill. A write-ahead log protects against torn updates. - **Log-structured merge (LSM)**: writes are **appended** to a log and a sorted memory buffer, flushed as immutable sorted files, and merged in the background. The internals of B-tree pages — fanout, height, node layout — are a subject of their own; here what matters is the behavioural contrast. ## Side by side | dimension | B-tree | LSM | |---|---|---| | where a key lives | exactly one page | memory buffer plus possibly several files | | write I/O pattern | random page writes (plus log) | sequential log appends and large sequential flushes | | write amplification source | rewriting whole pages for small changes, page splits | compaction rewriting data several times | | point read cost | one tree walk, predictable | memory, filters and possibly several files | | range scan | walk adjacent leaf pages | merge every overlapping file | | space use | fragmentation inside pages | obsolete versions and delete markers until compaction | | compression | limited by page boundaries | whole sorted files compress well | | background work | little (vacuum or page cleanup in some engines) | continuous compaction competing with foreground I/O | | latency profile | stable | good on average, spikes when compaction falls behind | ## Workload signals Lean **LSM** when: 1. writes are **sustained and heavy** relative to reads (ingestion, logging, metrics, events); 2. data is mostly **appended**, with few updates to old keys; 3. storage efficiency and compression matter at large volume; 4. the system can tolerate occasional read-latency variance. Lean **B-tree** when: 1. reads dominate and need **predictable** latency; 2. data is **updated in place** often, and transactions touch several keys; 3. range scans over current data are frequent; 4. there is little appetite for tuning background compaction. ## Nuances interviewers like - **Neither is universally faster**: well-cached B-trees handle heavy writes; well-compacted LSMs serve fast reads. Measure with realistic data. - **SSDs narrow the random-write penalty** of B-trees but still reward fewer bytes written, which can favour either engine depending on amplification. - **Compaction is the LSM's defining cost**: its tuning decides how read, write and space amplification balance. - Some relational databases can use LSM engines, and wide-column stores are built on them, because their workload is write-heavy. ## Interview angle A strong answer contrasts update-in-place with append-and-merge, walks through the table's key rows, gives workload signals for each, and refuses to name a universal winner.
- Why can an LSM engine show latency spikes that a B-tree engine usually does not?Compaction runs in the background and competes with foreground reads and writes for disk and CPU. When writes outpace it, files pile up, reads touch more of them, and the engine may slow or stall writes until compaction catches up.
- Where does write amplification come from in each engine?In a B-tree, rewriting a whole page for a small change, plus the log write and page splits. In an LSM, compaction rewriting the same data several times as it moves into larger files. Which is worse depends on update patterns and compaction policy.
saying these in an interview costs you the question
- Claiming LSM engines are always faster than B-trees
- Saying B-tree engines append writes sequentially like a log
- Ignoring compaction as a cost of LSM engines
- Believing an LSM point read always touches exactly one file
- Assuming B-trees have no write amplification