Bloom 索引:假阳性概率不是确定上限
Bloom 位数组用多个哈希位置表示集合,插入值不应被错误判成不存在;不存在的值可能假阳性,读回后仍需执行真实谓词。这个保证以正确实现、相同编码与完整索引为前提。
机制与确认边界
给定 m 位、n 个元素和 k 个近似独立哈希,常见估计 p≈(1-exp(-kn/m))^k;最优 k 与 m/n 有关,不是越多越好。九个不含目标值的块可能零个、一个或多个假阳性,不能承诺最多只多读一个。
实现与验证范围
本包实现 BitSet Bloom,逐个验证已插入值,另用 m=1 的饱和过滤器明确制造假阳性。原生跳数索引还受表达式、tokenization、索引 GRANULARITY 和分布影响;低基数值如果每块都存在,Bloom 再准确也不能跳过。
本章共享图解见 10.1 的机制图 ,其中的状态与确认点需和本节一起阅读。
复现与资料
下载本卷实验包
,按 README 运行 Java 8 lab.RunAll。单节点原生运行 clickhouse-probe.sh,多分片与复制实验运行 clickhouse_cluster.py;每个脚本仅把实际执行并断言的场景记为实测。外部源、真实 Kafka、TTL 介质、TPC-H 和未测版本的功能不包含在这些结果中。
继续阅读
探索更多技术文章
浏览归档,发现更多关于系统设计、工具链和工程实践的内容。