Every database index has the same chore: when a new row arrives, its entry has to land in the right place in a sorted structure. In a classic B-tree, that place is usually a leaf page somewhere on disk. If the index is too big for memory, each insert means reading and writing a random page. On a spinning disk, a random access is the slowest thing you can ask for.
In 1996, Patrick O'Neil and colleagues proposed a way out for write-heavy workloads such as logs and activity histories. Do not put each entry where it belongs right away. Collect entries, sort them in memory, and merge them into the disk structure in big sequential sweeps. The result is the log-structured merge-tree, the idea behind Bigtable, LevelDB, RocksDB and Cassandra.
An LSM-tree turns many small random writes into a few large sequential ones. It keeps recent entries in memory, merges them into bigger sorted structures on disk, and pays for it with slightly more work on reads.
The problem: random writes are expensive
The paper's running example is a transaction system that records every change in a History table. To find a customer's past activity quickly, you need an index on account and time. But every new History row needs a new index entry, and those entries land all over the index. Each one costs a random disk access.
The authors observe that the disk arm, not the disk's capacity, is the real cost. They estimate that the LSM-tree can do the frequent index inserts with much less disk arm use, at an order of magnitude lower cost for their example.
Imagine filing paper letters into a giant alphabetical cabinet. Walking to the right drawer for every letter is slow. A smarter clerk drops letters in an in-tray, and once an hour sorts the pile and files a whole batch in one trip down the aisle. Same cabinet, far fewer walks.
How an LSM-tree handles a write
An LSM-tree has components of increasing size. The smallest, C0, lives in memory. The next, C1, lives on disk and looks like a B-tree, but is packed full and laid out for sequential access.
- The write is first appended to a log file, so a crash cannot lose it.
- The entry is inserted into the C0 tree in memory. That costs no disk I/O.
- When C0 grows too big, a rolling merge takes a run of sorted entries out of C0 and merges them into C1, rewriting those C1 pages in large multi-page blocks.
