为什么布隆过滤器无法处理范围查询？
Why Bloom filters cannot handle range queries?
上下文：我正在阅读有关 RocksDB 和 LSM 树的信息，根据我的理解，布隆过滤器用于避免在所有存储级别中对项目检索进行多次 I/Os。我对此没有意见。
显然，挑战之一是布隆过滤器不能用于范围查询。是什么原因？如果我想检查 32 和 200 之间是否有键，我可以对中间的每个值进行单键查找（或在第一个 "true" 响应处停止）。真的没有效率吗？
您可以这样做，但效率很低，因为与寻找第一个值 (32) 并迭代到 200 相比，单点查找速度很慢（即使使用布隆过滤器）。Leveldb/rocksdb 针对此类迭代进行了优化。
此外，在您的情况下，您只需要 32 到 200 之间的任何第一个密钥 - 您只需进行一次搜索，仅此而已，否则在最坏的情况下您必须进行 200-32 = 168 次查找。如果没有冲突，布隆过滤器可以快速回答密钥是否不存在，但如果存在，它仍然需要磁盘查找。
上下文：我正在阅读有关 RocksDB 和 LSM 树的信息，根据我的理解，布隆过滤器用于避免在所有存储级别中对项目检索进行多次 I/Os。我对此没有意见。
显然，挑战之一是布隆过滤器不能用于范围查询。是什么原因？如果我想检查 32 和 200 之间是否有键，我可以对中间的每个值进行单键查找（或在第一个 "true" 响应处停止）。真的没有效率吗？
您可以这样做，但效率很低，因为与寻找第一个值 (32) 并迭代到 200 相比，单点查找速度很慢（即使使用布隆过滤器）。Leveldb/rocksdb 针对此类迭代进行了优化。
此外，在您的情况下，您只需要 32 到 200 之间的任何第一个密钥 - 您只需进行一次搜索，仅此而已，否则在最坏的情况下您必须进行 200-32 = 168 次查找。如果没有冲突，布隆过滤器可以快速回答密钥是否不存在，但如果存在，它仍然需要磁盘查找。