《大规模分布式计算深入解析》2.3 HNSW 插入与删除:候选选择、pruning 与占位

插入从新节点所属层向层零连接,几何剪枝保留方向多样性;底层与高层容量分开,懒删除排除结果但可保留导航。

新点在哪些层连边

先采样新点最高层L。从现有最高层入口下降到L之上,主要用于定位;从min(L,当前最高层)向0收集候选并选择邻居。层编号非负,不存在“层0及以下”的负层图。

新节点尝试与最多M个选定近邻建立双向邻接。对被连接的旧节点,如果加入后超过该层上限,则再次剪枝。hnswlib0.8.0典型设置maxM=M、maxM0=2M;本卷模型采用这个层预算,但不宣称所有实现都相同。

为什么不能只保留最近M

查询原点p=0,候选坐标1、1.1、−2,保留上限2。最近截断会取1和1.1;几何多样性规则先取1,再发现1.1更接近已选1而非p,于是跳过;−2与1相距3、大于它到p的距离2,因此可留下。结果1和−2覆盖两个方向,有利导航。

这是基于几何的邻居选择,而非Vamana的所有参数和多轮构建。本卷分别给出两者实现,避免同名pruning掩盖不同合同。

有向边数与“净增一条边”

两端邻接各记一个ID时,一次双向连接会增加两项。旧邻居剪枝可能只修改一端,最终图可出现不对称。因而“加2减1=净增1”只有先规定无向边还是邻接项才有意义。容量按分配槽算,实际边项按最终邻接遍历计,两者不可互换。

删除的结果资格和导航资格

链0→1→2,删除中间节点1后,查询2仍可经1到达2;1不返回,但其邻接还能参与导航。如果把“跳过墓碑”理解为不展开1,路径就被切断。真正删除、槽复用、重连和重建策略因实现而异,20%墓碑触发重建只是可选运维策略,不是HNSW算法常量。

教学索引保留墓碑和邻接,不做ID复用;重建应另创建新索引并受控切换。删除不能凭一个计数器验证,必须测试删除桥、入口已删、全删、结果不足及候选过滤。

架构与流程

flowchart TD
 N["新点:采样最高层L"] --> U["高于L:贪婪选入口"]
 U --> S["从min最高层到0逐层搜候选"]
 S --> G["几何邻居选择;不只最近M"]
 G --> LINK["尝试双向连边"]
 LINK --> DEG{"旧节点超过该层容量?"}
 DEG -->|是| PRUNE["重新几何剪枝"]
 DEG -->|否| KEEP["保留邻接"]
 D["删除ID"] --> T["结果排除;导航仍可穿过"]

实现与验证边界

模型实现几何选择、层容量约束与墓碑结果过滤,并通过受控删除桥。没有在线槽复用、锁或设备恢复。上游固定核心探针验证同样的删除导航区别,不能扩大为所有产品的删除策略。

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

一手资料

卷十三目录 · 系列导读

继续阅读

探索更多技术文章

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

全部文章 返回首页

「books」更多文章

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