B+ trees are a strong default for many databases. They keep keys ordered in page-sized chunks, which makes lookups and range scans predictable.

The cost shows up when the system writes a lot. Updating one value may change an existing page, update parent pages, write to a recovery log, and sometimes split a page. That is fine for many workloads, but it can become painful when writes arrive nonstop.

LSM trees, short for Log-Structured Merge Trees, take a different approach. They first collect writes in memory, then write them to disk as sorted files that are never changed in place. Later, the database merges and cleans up those files in the background.

That makes the write path fast because the database avoids constantly rewriting old pages. The tradeoff is that reads and background cleanup have more work to do.

This design powers storage engines such as LevelDB, RocksDB, Cassandra, ScyllaDB, Bigtable, and HBase. A similar idea also appears in search systems such as Lucene, where new index segments are written and later merged.

This chapter explains how LSM trees handle writes, reads, deletes, and background merging.