prefix-bloom-filter · shipping · also Prefix membership filter

Prefix Bloom filter

A Bloom filter built over extracted key prefixes rather than only whole keys, allowing negative membership tests for those represented prefixes.

A present prefix can belong to an absent full key; that is not a false positive for prefix membership. A single negative prefix test cannot prove an interval crossing other prefixes empty. RocksDB prefix iteration requires the matching query contract. [1]

Relations

related

bloom-filter, prefix-extractor, succinct-range-filter

Citations

1. RocksDB project. Prefix Seek: comparator compatibility, iterator modes and extractor changes. (accessed 2026-10-13)
2. Hesela: filter predicates, prefix correctness and SuRF boundaries (accessed 2026-10-13)

JSON: /data/terms/prefix-bloom-filter.json