Chapter 7. Log Structured Storage

Brief

Log-structured merge trees (LSM trees) suit write-heavy workloads because they append changes and merge sorted files later. Unlike a B-tree, which locates a node and updates it in place, an LSM tree first records new values sequentially. Reads can cost more because they may need to check and combine several levels.

B-trees can require random I/O when a write splits or merges a page. These changes are called structure-modification operations (SMOs). LSM trees instead favor sequential writes, which storage devices can perform efficiently.