LSM versus B-tree write paths
LSM vs B-tree: where writes go
teaching sketch, not a benchmark
LSM write path: always append
WAL
append + fsync
Memtable
sorted RAM
SSTables
immutable
Compact
merge + tomb
->
->
->
point read: mem first, then newest to oldest segment
B-tree: rewrite page in place
Find leaf
root to leaf
Rewrite
same page
WAL
fsync
range scan follows the leaf chain
Amplification per user write (teaching ratios)
write amp
read amp
space amp
LSM: rewrite on compact ~10x
LSM: check several segments
LSM: old + new until merge
B-tree: page rewrite ~1-2x
B-tree: depth 3-4 pages
B-tree: pages + WAL + splits
crash between flush and manifest: SSTable file ignored, WAL replayed
tombstone dropped too early resurrects the old value