LSM-trees and B-trees

An LSM-tree (log-structured merge tree) is a stack of sorted files merged in the background. A B-tree keeps sorted pages and changes them in place.

Bloom filters

A Bloom filter is a small bit array per file. Adding a key hashes it to a few bit positions and sets them to 1. If any of a key's bits is 0, the key is surely not in that file. If all are 1, it is probably there, but it may be a false positive. About 10 bits per key gives roughly 1% false positives.

Compaction strategies

Size-tiered compaction merges newer, smaller files into bigger ones. Data is copied fewer times, which suits heavy writes, but big merges need lots of spare disk. Leveled compaction keeps levels of fixed-size files, split by key range, each level bigger than the last. Reads check fewer files and less space is wasted, so it suits reads.

B-tree pages and lookups

A B-tree stores data in fixed-size pages, often 4 to 16 KiB, overwritten in place. Pages point to each other by page number. A lookup starts at the root and follows the child whose key range holds the key, down to a leaf. Each page has hundreds of children. Shortened keys and links between neighbor leaves help.

B-tree splits and depth

Updating a key overwrites its leaf page. Inserting into a full page splits it into two half-full pages and adds a boundary key to the parent. If the root splits, a new root grows on top. The tree stays balanced, usually 3 or 4 levels deep. With 4 KiB pages and 500 children each, four levels can hold about 250 TB.

Crash-safe B-trees

A split changes several pages, and a crash halfway can break the tree. So each change first goes to a write-ahead log (WAL), which is replayed after a crash. Copy-on-write instead writes changed pages to new places.

Remember

• Bloom filter: "no" is sure, "yes" is maybe.
• Size-tiered for writes, leveled for reads.
• B-trees overwrite pages; splits keep them shallow.
• The WAL makes overwrites safe.