Log-structured merge tree

A log-structured merge tree (LSM tree) turns random updates into sequential writes, then compacts overlapping sorted files in the background.

For example, a key-value database can write new keys quickly to memory and a log before merging them into larger disk files.