LSM 05: The Bloom Filter

The Data Systems board on the pieces around the two storage engines, among them the Bloom filter that lets a log-structured engine skip files. This lesson builds that piece. Part of the LSM series, Build Your Own LSM Tree.

Before you start. This series builds a small copy of a storage engine that never edits a file in place. LSM 03-04: Table Files and the Sparse Index made each table file cheap to ask with a sparse index, and left one problem standing: a key that is not in the database still makes the engine ask every file. You need no probability beyond “one in a hundred”. Storage Extras: richer indexes, warehouse schemas, column tricks describes Bloom filters in prose and is worth reading first or after.