按目标误差和键数选择过滤器预算。
实现机制
在哈希近似独立、经典位数组条件下,m/n 比特每键的近似最优 k 为 (m/n) ln 2。10 bit/key 约选 7 个哈希,算例假阳性约 0.8%。
1 亿键按 10 bit/key 是 125 MB 的理想位数组,额外空间包括分区、元数据和实现开销。
Bloom 假阳性的执行路径
flowchart TD
N0["键与快照序号"]
N1["按 min/max 选文件"]
N0 --> N1
N2["过滤器判断是否可能存在"]
N1 --> N2
N3["块索引定位偏移"]
N2 --> N3
N4["读缓存或设备并检查可见版本"]
N3 --> N4
N2 -- "过滤器返回不存在" --> F0["跳过该候选;范围查仍需核对过滤域"]
验证
复算空集合与不同负载下的误判率,确认查询键编码与过滤器生成一致。
一手资料
继续阅读
探索更多技术文章
浏览归档,发现更多关于系统设计、工具链和工程实践的内容。