LSM Tree vs B-Tree
Compare an LSM tree with a B-tree as a storage engine. When would you pick each?
Answer out loud in under a minute: a definition, one concrete example, and one pitfall or trade-off.
Hints
Hint 1
Follow a single write and a single point read through both structures and count the disk operations.
Solution
Show the approach
The short version
An LSM tree appends writes to a log and an in-memory table, flushes sorted files to disk, and merges them in the background (compaction); a read may check several files, helped by Bloom filters. A B-tree updates pages in place, so reads are a predictable walk from the root and writes pay a random I/O.
Example
An ingestion-heavy event store writes millions of rows an hour and reads recent ranges: LSM. A product catalogue read a thousand times per write with tight latency targets: B-tree.
Pitfall
LSM compaction costs write amplification and can stall writes when it falls behind; B-trees fragment and pay for random writes. Neither is free — the choice is which cost matches the workload.