B+ Tree vs LSM Tree for Database Interviews: Reads, Writes, Compaction, and Amplification

"B+ tree or LSM tree?" sounds like a vocabulary question. In a strong database interview, it is really a test of whether you can trace one read, one write, and the background work that makes both possible.

This guide covers B+ Tree vs. LSM Tree for database interviews, including point reads, range scans, page updates, compaction, tombstones, and read, write, and space amplification. The goal is not to memorize a winner. It is to choose an engine from the workload and defend the cost model.

Use PracHub to practice real interview questions with written solutions, then narrow the set with company-specific interview prep. For this topic, say your workload assumptions first and make every I/O consequence explicit.

The useful comparison is not "reads versus writes." It is where each design pays for ordering, durability, and cleanup.

Quick Verdict: B+ Tree or LSM Tree?

Choose a B+ tree when you value direct, predictable lookups and ordered traversal. Choose an LSM tree when you need to absorb sustained writes by batching them into sequential flushes, and you can budget for compaction and a more layered read path.

B+ Tree and LSM Tree Fundamentals

1. What is the core difference between a B+ tree and an LSM tree?

A B+ tree maintains one page-oriented, sorted search structure as writes arrive. An update finds the target leaf, changes a page, and may trigger a split, merge, or rebalancing operation.

An LSM tree buffers recent writes in memory, flushes immutable sorted files, and reconciles those files later through compaction. The B+ tree pays more of the organization cost near the foreground write; the LSM tree defers and batches much of it.

2. What makes a database B+ tree different from a binary search tree?

A B+ tree node holds many keys and child pointers, so its branching factor is large and its height stays small. Internal pages guide the search, while leaf pages hold the ordered entries or references to records.

Database trees are designed around pages rather than individual objects. A wide node can turn many key comparisons into one storage read, which matters more than minimizing CPU comparisons when the data is larger than memory.

3. Why are B+ tree leaves useful for range scans?

After the engine finds the first qualifying leaf, it can continue through neighboring leaves in key order instead of returning to the root for every row. PostgreSQL documents that B-tree indexes can serve equality, range, and ordered retrieval, which is why they fit predicates such as BETWEEN and ordered LIMIT queries.

The important interview caveat is selectivity. If a query returns a large fraction of the table, a sequential scan plus sort can still beat following an index and fetching many scattered rows.

4. What is the typical LSM write path?

A durable write is appended to a log and inserted into an in-memory sorted structure called a memtable. When the memtable reaches its limit, it becomes immutable and is flushed as a sorted string table, or SSTable.

Later compactions merge overlapping sorted runs, retain the newest visible versions, and produce new immutable files. LevelDB and Cassandra both document this log, memtable, SSTable, and compaction pattern.

5. Is a write-ahead log exclusive to LSM trees?

No. A WAL is a durability mechanism; an LSM tree or B+ tree is an indexing and storage-layout choice. An LSM engine logs the in-memory write so it can rebuild an unflushed memtable after a crash.

A page-oriented B+ tree engine also commonly logs changes before dirty pages reach durable storage. Do not say "LSM has a WAL, B+ tree does not." Explain what must survive a crash and how recovery reconstructs a consistent state.

Read Paths and Range Scans

6. How does a B+ tree serve a point read?

The engine follows separator keys from the root through internal pages to one leaf. Upper levels are often cached, so a cold lookup may require only the lower pages; a clustered index can lead directly to the page containing the row.

A secondary index may require another lookup. MySQL documents that an InnoDB secondary-index record contains the primary key, which the engine then uses to search the clustered index.

7. How does an LSM tree serve a point read?

The engine checks the active memtable and any immutable memtable, then searches the SSTables that could contain the key. Because newer files may override older versions, the read path must respect recency and sequence numbers.

Indexes, block caches, and Bloom filters keep this from becoming a full scan. In a leveled design, non-overlapping files above level 0 also limit how many files can contain a given key.

8. What does a Bloom filter fix, and what does it not fix?

A Bloom filter can prove that an SSTable definitely does not contain a key, avoiding unnecessary data-block reads. A positive result is only "maybe," so the engine must still inspect the candidate file.

Bloom filters are strongest for point lookups and some configured prefix lookups. They do not remove the need to merge sorted runs during a general range scan, and false positives still consume work.

9. Why are LSM range scans more complicated?

Relevant keys may exist in the memtable and several SSTables, including obsolete versions and tombstones. The engine creates ordered iterators over those sources and performs a merge that returns the newest visible value for each key.

A B+ tree generally walks one ordered leaf sequence. An LSM scan can still be efficient, but its cost grows with overlapping runs, stale versions, cache misses, and compaction debt.

10. How does caching change the comparison?

If B+ tree internal pages and hot leaves fit in memory, many reads avoid storage and multiple updates can be combined before a dirty page is flushed. That can reduce the practical cost of page-oriented writes.

For an LSM tree, the block cache, index blocks, and filters reduce point-read I/O, while the memtable serves the newest data. A senior answer treats cache size and working-set locality as workload inputs, not footnotes.

Writes, Compaction, and Deletes

11. Why can an LSM tree sustain high write throughput?

It converts many small, scattered mutations into larger sequential flushes and merge operations. The original LSM paper describes this as a batching advantage: several in-memory entries can be merged into a disk page during one pass.

That advantage is amortized, not free. The system must provision enough background I/O and CPU to compact data at least as fast as the long-term ingest rate.

12. What does compaction actually do?

Compaction reads selected SSTables, merges their sorted entries, writes replacement SSTables, and retires old files after readers no longer need them. It reduces the number of runs a read may consult and reclaims superseded values when it is safe.

Compaction is therefore part of the serving design, not housekeeping. If it falls behind, read amplification, temporary disk use, and eventually write latency can all rise.

13. What is the difference between leveled and tiered compaction?

Leveled compaction keeps relatively few overlapping runs, which improves reads and controls space amplification, but it may rewrite overlapping data repeatedly. Tiered compaction waits for similarly sized runs and merges them together, usually reducing write amplification while allowing more read and temporary space amplification.

There is no universal best policy. The choice depends on update frequency, read latency, data lifetime, available disk headroom, and whether the workload is steady or bursty.

14. What causes an LSM write stall?

If flush or compaction cannot keep pace, immutable memtables and level-0 files accumulate. The engine eventually slows or stops foreground writers so background work can catch up instead of exhausting memory or disk.

RocksDB explicitly ties this backpressure to pending flushes, too many level-0 files, and excessive pending compaction bytes. In an interview, include queue depth, compaction throughput, stall time, and free-space alerts in the design.

15. How do deletes work in an LSM tree?

Because SSTables are immutable, a delete usually writes a tombstone instead of editing every older file immediately. Reads treat the tombstone as a newer version that hides the old value.

A later compaction can discard both the tombstone and older data only when no unprocessed lower level, snapshot, or replica rule still requires them. Removing tombstones too early can make deleted data reappear.

Read, Write, and Space Amplification

16. What is write amplification?

Write amplification is physical bytes written divided by logical bytes written by the application. An LSM engine may write a value to the log, flush it to an SSTable, and rewrite it through several compactions.

A B+ tree can also amplify writes when a small update dirties a full page, generates WAL records, or triggers structural changes. Compare complete implementations under the same durability and cache assumptions.

17. What is read amplification?

Read amplification is the extra storage work required to answer one logical read. A B+ tree lookup follows a bounded root-to-leaf path, although secondary indexes and row fetches can add steps.

An LSM lookup may consult multiple runs, and a scan may merge several iterators. Bloom filters, non-overlapping levels, indexes, and caches reduce the cost, but they do not erase the layered read path.

18. What is space amplification?

Space amplification is on-disk bytes divided by the live logical data size. LSM engines temporarily retain old versions, tombstones, input files, and compaction outputs, so free-space planning must cover more than the live dataset.

B+ trees also carry page slack, internal nodes, secondary indexes, old versions, and WAL or snapshot overhead. The useful question is which form of overhead dominates for this workload and recovery model.

19. Is "B+ trees win reads and LSM trees win writes" always correct?

It is a starting heuristic, not a conclusion. An in-memory B+ tree working set can coalesce updates efficiently, while a poorly tuned LSM can suffer heavy compaction and stalls. Large values can also make repeated LSM rewrites expensive.

Conversely, an LSM with a write-heavy, larger-than-memory workload can batch random updates effectively, and filters plus cache may make point reads competitive. State the record size, read/write ratio, key distribution, cache budget, durability, scan pattern, and latency target before choosing.

Compaction moves cost among write, read, and space amplification; it cannot minimize all three independently.

Choosing a Storage Engine in an Interview

20. How should you choose between B+ tree and LSM tree for a real workload?

Start with the SLO and access pattern. A transactional service with frequent point reads, ordered queries, and tight p99 latency often favors a B+ tree-family engine. An event, metrics, or wide-column workload with sustained small writes may favor an LSM-family engine.

Then name the deferred cost. For a B+ tree, discuss dirty-page flushing, splits, WAL, and cache locality. For an LSM tree, discuss compaction bandwidth, tombstones, Bloom filters, read amplification, disk headroom, and write stalls.

This explains why PostgreSQL defaults to B-tree indexes for common ordered queries, while Cassandra documents an LSM-based, write-oriented storage engine. The products solve different workload problems; the data structure is part of that product decision.

A Five-Step Answer Framework

First, define the workload: read/write ratio, point versus range access, value size, update pattern, and durability. Second, trace one write from acknowledgment to durable placement. Third, trace one cold read. Fourth, expose deferred work such as splits or compaction. Fifth, name the metrics that would falsify your choice.

For more practice turning workload requirements into defensible architecture choices, work through PracHub's system design questions, then review the related database design interview questions and database replication interview questions.

What Interviewers Are Actually Scoring

Interviewers are listening for a causal chain: workload requirement, storage layout, read or write path, failure mode, mitigation, and measurement. Naming PostgreSQL, Cassandra, RocksDB, or a Bloom filter without tracing that chain is not enough.

Strong candidates also avoid false binaries. They recognize that engines combine WALs, caches, filters, indexes, compaction policies, and concurrency control, and that production results depend on configuration and hardware.

Frequently Asked Questions

Is a B+ tree always better for range queries?

No. Its ordered leaf traversal makes the path simple and predictable, but selectivity, row placement, cache behavior, and query width still matter. LSM trees also support ordered scans, though they may merge several runs and process stale versions or tombstones.

Does an LSM tree eliminate random writes?

It moves most foreground data placement toward append and sequential merge patterns, but the complete engine still writes logs, manifests, indexes, and compaction outputs. Storage allocation and filesystem behavior also matter, so "sequential" is a design tendency rather than a promise about every device operation.

Does a B+ tree need compaction?

Not in the LSM sense of repeatedly merging immutable sorted runs. A page-oriented engine still needs maintenance such as page splits, merges, vacuuming, defragmentation, checkpointing, or copy-on-write cleanup depending on its implementation.

Which tree does PostgreSQL or Cassandra use?

PostgreSQL documents B-tree as its default index method for common equality, range, and ordering needs. Cassandra documents an LSM-based storage engine with commit logs, memtables, immutable SSTables, Bloom filters, and background compaction.

What is the best one-minute interview answer?

Say that B+ trees maintain one ordered page structure and usually provide a direct, predictable read path, while LSM trees batch writes into immutable sorted runs and pay later through compaction and layered reads. Then choose from the workload and name the read, write, and space amplification you will monitor.

Final Takeaway

The strongest B+ Tree vs. LSM Tree answer does not crown a universal winner. It shows where ordering work happens, how durability is preserved, what background maintenance costs, and which SLO matters most.

Use PracHub to move from reading to practice: answer real interview questions under a timer, compare your reasoning with written solutions, and add behavioral and leadership practice so the technical trade-off remains clear when interviewers push on risk and ownership.

Official Sources

• The Log-Structured Merge-Tree
• PostgreSQL index types
• SQLite database file format
• MySQL InnoDB clustered and secondary indexes
• LevelDB implementation notes
• RocksDB tuning guide
• RocksDB compaction documentation
• Apache Cassandra storage engine