Tries and Bloom filters

Tries

A trie's root represents the empty string. Each node has a child per next character, and nodes that complete a word are marked. Looking up a key takes one step per character, independent of how many keys are stored, and finding every key with a given prefix means walking to the prefix's node and listing everything below it:

That makes tries natural for autocomplete, spell checkers and routing tables. A one-character-per-node trie wastes a lot of memory on long chains with a single child, so real implementations compress those chains into one edge labelled with a whole substring. That is a radix tree (or Patricia trie), the structure many HTTP routers use to match paths like /users/:id/posts, and the basis of longest-prefix matching for IP routes.

Bloom filters

A Bloom filter is an array of m bits, all 0 at the start, plus k hash functions that each map an item to a bit position. Adding an item sets its k bits. Checking an item looks at the same k bits: if any is 0, the item was definitely never added; if all are 1, it was probably added, but other items may have set those bits by coincidence. There are no false negatives, only false positives, and the filter never stores the items themselves.

For n items, the false-positive rate is about (1 − e^(−kn/m))^k, and the best k is (m/n) · ln 2. Roughly 9.6 bits per item with 7 hash functions gives 1%, and every extra 4.8 bits per item divides the rate by ten, regardless of whether the items are 8-byte ids or 2 KB URLs. The example uses one well-mixed hash and derives the k positions from two values, a trick from Kirsch and Mitzenmacher that loses nothing in accuracy:

The measured rate matches the formula, 1.00%. Without the final mixing step the bit positions of similar keys like user-1 and user-2 were correlated: fewer bits got set than the formula assumes, and the measured rate came out at 0.54% instead of 1.00%. Better than predicted, but no longer predictable, which is a good reminder that a Bloom filter is only as good as its hash.

Bloom filters earn their place in front of something expensive. An LSM-tree database such as RocksDB or Cassandra keeps one per on-disk file, so a read for a key that isn't in a file usually skips reading that file at all. Caches use them to avoid storing items seen only once, and distributed joins use them to avoid shipping rows that can't match. Removing items needs a variant, such as a counting Bloom filter or a cuckoo filter, because clearing a shared bit would create false negatives.