Expert · Module 24 · Lesson 1 of 4
Bloom filters
A Bloom filter answers membership questions from a few kilobytes of bits: absence is always certain, presence is probably right, and the false positive rate is a number you choose. It is how databases skip reads they do not need.
By the end you can
- Trace insertions and membership queries through a Bloom filter's bit array
- Size a Bloom filter from a key count and a target false positive rate
- Explain why the filter never reports a false negative and why deletion breaks it
Builds on What a hash function does, Expected cost of hashing.
01 · A question first
LevelDB keeps a few bits per key beside every sorted table and consults them before touching the disk, so most lookups for keys that are not there cost one in-memory probe instead of a seek. The trade is a small chance of answering "present" for a key that was never stored. What makes that acceptable, and why can the filter never answer "absent" for a key it did store?
Make a guess before you read on.
02 · The idea
Members only
Unlock the full lesson
This lesson is part of the membership. Join to read it in full, along with every other premium deep dive.
What's inside
- Looking up keys you never stored
- One array, several hash functions
- When present means probably
- Sizing for the rate you need
- What a filter costs, and what it cannot do
- Why you cannot delete
- Where Bloom filters do the work
- Pseudocode & Multi-Language Implementations (C++, Java, Python)
03 · Practice
Something wrong with this lesson? Report a problem