《大规模分布式计算深入解析》2.2 HNSW 多层图:层分配、入口点与搜索

HNSW用指数层分配和逐层导航;层零前沿C与有界结果W分开,ef不是访问或算距硬上限,结果不足K返回实际条数。

指数层分布与入口

经典层分配可写level=floor(−ln(U)·mL),U在(0,1],常用mL=1/ln(M)。于是达到层l的概率按M^(−l)递减。M=2时理论P(level≥1)=1/2、P(level≥2)=1/4。有限样本会波动,不能用id取模构造均匀层再宣称验证指数分布。

入口选当前最高层节点。搜索先在高层用小候选定位,逐层把入口下传,层零再用较宽预算收集结果。每一层都有独立邻接,节点只能出现在不高于自身最高层的层中。

为什么需要两个队列

前沿C按最小距离取待展开点;结果W按最大距离暴露当前最差保留结果,最多ef条;visited防止同层重复评估。一个点可以作为导航候选,却因删除或过滤没有资格进入W。把它们合并成一个ef大小的堆,会改变停止、删除与过滤行为。

在普通受控搜索中,若W已达到ef且最近前沿点已比W最差更远,可停止。具体bare-bone优化与扩展停止接口依上游实现,不能只写“把堆里点都访问完”。逐邻居处理完成后才回到前沿取点,避免漏掉当前邻接表的后续边。

ef与K的合法性

教学API要求ef≥K≥1,低于K直接拒绝;hnswlib0.8.0的C++核心searchKnn会用max(ef,K)调用底层,而其参数文档要求调用者ef≥K。应分别说明接口选择,不把ef2返回Top3作为所有产品通用合法例。

ef控制动态保留结果预算,不是算距上限。在独立上游64点示例,配置ef2/K3核心提升后返回3条,实际算距18次。这个固定例子只用于破除“K=算距”的混淆,不是复杂度界,也不是Milvus内部计数。

本卷最小多层索引

Hnsw.Index用固定seed采层,逐层插入和搜索,几何选择邻居并约束各层出度。八点0..7、q0.6、K3/ef16返回1/0/2,与Flat对照。搜索跨层累计调用次数,结果不足K时只返实际ID,不填默认0。该实现没有并发、持久化、SIMD或生产级索引文件。

架构与流程

flowchart TD
    Q["输入 q、K、ef;按实现校验或提升 ef"] --> UPPER["从最高层入口下降:贪婪定位"]
    UPPER --> INIT["层零:visited + 待展开前沿 C + 有界结果 W"]
    INIT --> POP{"C 是否为空?"}
    POP -->|"是"| OUT["W 中按距离取实际可用 TopK"]
    POP -->|"否"| BEST["弹出 C 中最近候选 c"]
    BEST --> STOP{"达到当前实现停止条件?"}
    STOP -->|"是"| OUT
    STOP -->|"否"| EDGES["读取 c 的邻接表"]
    EDGES --> MORE{"邻接表还有未处理邻居?"}
    MORE -->|"是:取下一邻居v"| NEW{"邻居 v 首次发现?"}
    MORE -->|"否"| POP
    NEW -->|"否"| NEXT["继续下一邻居"]
    NEW -->|"是"| DIST["标记 visited;计算 q-v 距离"]
    DIST --> FRONTIER{"仍有扩展价值?"}
    FRONTIER -->|"否"| NEXT
    FRONTIER -->|"是"| ENQUEUE["加入前沿 C;可能继续导航"]
    ENQUEUE --> ELIGIBLE{"v 未删除且满足结果过滤?"}
    ELIGIBLE -->|"是"| RESULTS["加入 W,超过 ef 则淘汰最差"]
    ELIGIBLE -->|"否"| SKIP["不进入 W,保留导航可能性"]
    RESULTS --> NEXT
    SKIP --> NEXT
    NEXT --> MORE

实现与验证边界

Java测试指数分布、真实多层插入、邻接层级、候选/结果分离与结果不足。固定hnswlib核心探针对照另列原生入口;Milvus不暴露同样的内部计数。

下载卷十三实验包 。Java 8入口为 lab.RunAll;本节对应 hnsw.HnswSuite。按README分别运行模型与原生入口,失败必须返回非零。模型通过不代表完整产品实现。

一手资料

卷十三目录 · 系列导读

继续阅读

探索更多技术文章

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

全部文章 返回首页

「books」更多文章

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