What Is a Bloom Filter - and When You Actually Don't Need One
A Bloom filter is a small, fixed-size bit array that answers one question: "is this key definitely absent, or possibly present?" It never says no when the answer is yes, but it will sometimes say maybe when the answer is no. That asymmetry is the whole product. You trade exact answers for memory, and you get a structure that holds membership information for millions of keys in a few megabytes, with no stored keys at all. The problem it exists to solve is expensive lookups. If checking whether a key exists means a disk seek, a network round trip, or a cross-region query, you want something cheap in front of it that can rule out most of the misses. A Bloom filter is that guard, and its cost is that it lets a small fraction of misses through and can never take a key back out. Concept Bloom filter (BF) Where it sits Data structure - sits in front of an expensive lookup, at the cache or storage layer In one sentence A probabilistic set membership structure that can t...
