布隆过滤器用可控误判率省去不存在键的磁盘读取

[[LSM树用内存表加WAL兼顾写入速度与崩溃安全]]有一个天然的性能陷阱：查找一个数据库 中不存在的键时反而最慢——因为要证明”这个键不存在”，必须检查内存表，然后依次回查 每一个磁盘段（可能每一个都要单独发起磁盘读取），直到最老的段都查完才能下结论，而 这个昂贵的过程恰恰针对的是最后什么结果都没查到的请求。解法是引入布隆过滤器——一种 内存高效的近似集合数据结构，能快速回答”某个键有没有可能出现在这个数据库里”这个 问题。布隆过滤器的关键特性是它只会漏报”存在”（即可能有假阳性：说某键存在，但实际 上不存在），但不会漏报”不存在”（不会有假阴性：如果它说某键不存在，那这个键就一定 真的不存在）。这个不对称性正是它能被安全使用的原因：查找前先问一遍布隆过滤器， 如果它说”不存在”，就可以直接跳过对应段的磁盘读取，节省大量原本注定徒劳的I/O操作； 只有当它说”可能存在”时才真正去磁盘查，即使这时候偶尔查出来发现其实不存在（假阳性）， 也只是浪费了一次本可避免的查询，不会导致把真实存在的数据误判为不存在这种正确性 错误。这是用”轻微的、可控的误判率”换取”大幅减少无谓磁盘I/O”的一个经典权衡范例。