bloom-filter - 为什么布隆过滤器不能处理范围查询？

Question

上下文：我正在阅读有关 RocksDB 和 LSM 树的信息，据我了解，Bloom 过滤器用于避免在所有存储级别中检索多个 I/O。我同意。

显然，挑战之一是布隆过滤器不能用于范围查询。是什么原因？如果我想检查 32 到 200 之间是否有一个键，我可以对中间的每个值进行单键查找（或在第一个“真”响应处停止）。真的没有效率吗？

Answer 1

您可以这样做，但效率低下，因为与寻找第一个值 (32) 并迭代到 200 相比，单点查找很慢（即使使用布隆过滤器）。Leveldb/rocksdb 已针对此类迭代进行了优化。

此外，在您的情况下，您只需要 32 到 200 之间的任何第一个键 - 您只需进行一次搜索，仅此而已，否则您必须在最坏的情况下进行 200-32 = 168 次查找。如果没有冲突，布隆过滤器可以快速回答 key 是否不存在，但如果存在冲突，它仍然需要进行磁盘查找。