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

Question

上下文:我正在阅读有关 RocksDB 和 LSM 树的信息，根据我的理解，Bloom 过滤器用于避免所有存储级别中的项目检索的多个 I/O。我对此没有意见。

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

Answer 1

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

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