《大规模分布式计算深入解析》10.2 Bloom 索引:假阳性概率不是确定上限

Bloom 位数组用多个哈希位置表示集合,插入值不应被错误判成不存在;不存在的值可能假阳性,读回后仍需执行真实谓词。这个保证以正确实现、相同编码与完整索引为前提。

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 和未测版本的功能不包含在这些结果中。

卷十二目录 · 系列导读

继续阅读

探索更多技术文章

浏览归档,发现更多关于系统设计、工具链和工程实践的内容。

全部文章 返回首页

「books」更多文章

  1. 《大规模分布式计算深入解析·向量数据库与 AI 检索内核》 · 目录与学习路径(45 篇)
  2. 《大规模分布式计算深入解析》15.3 自研向量引擎:可执行骨架与工程缺口
  3. 《大规模分布式计算深入解析》14.1 Milvus:组件架构、段管理与检索链路