Page 124 - 《软件学报》2026年第3期

王可 等: 面向批量更新的向量索引召回率优化 1087

与查询两个核心阶段.
在图的构建阶段, 算法为数据集中的所有节点构建高效导航的近邻图. 该构建过程是增量式的: 新节点 v 被逐
一插入图中, 并为每个 v 执行邻居查找与连接操作. 具体而言, 邻居查找过程复用了查询阶段的贪心搜索机制, 即
从图的随机入口点出发, 迭代搜索以定位一组距离 v 最近的候选邻居集. 随后, 算法从候选邻居中筛选预设数量的
节点作为最终邻居, 并建立从 v 指向它们的有向边. 为了保证索引的存储开销与查询复杂度维持在可控范围内, 每
个节点的最大出度受一个固定上限值约束. 重复此流程直至所有数据点入图, 即完成了完整近邻图的构建.
基于图的查询阶段则充分利用已构建的图结构实现高效检索, 其贪心寻路过程如图 1 所示. 查询通常从整个
图中所有节点中随机选取的一个入口点开始, 迭代访问当前节点的邻居集. 在每步迭代中, 算法选择离查询点更近
的未访问邻居作为下一个当前节点, 并维护容量有限的动态候选结果集. 当邻居中不存在比候选集中最远点更接
近查询点的新节点时, 搜索收敛并返回候选集作为近似最近邻结果. 这种基于图的贪心寻路策略通过局部搜索快
速收敛至目标区域, 无须遍历全图, 实现高效率检索.

C: 候选集 R: 结果集 visited: 标记节点的访问 (1) C: A
R:
C visited: A
D
E (2) C: B G D E
R: A
入口点
visited: A B D E G
A (3) C: H G C D E
B R: A B
F
visited: A B C D E G H
I (4) C: G C D E K J
G
H R: A B H
visited: A B C D E G H J K
J q (5) C: C D E F K J
K 查询 R: G B H
visited: A B C D E F G H J K
图 1 图向量索引的查询过程

基于上述基本原理, 图向量索引经历了一系列演进. 早期的探索以 Delaunay 图为代表. 该方法虽能保证搜索
的精确性, 但其过高的构建复杂度使其难以应用于大规模数据集. 为了缓解时间复杂度与搜索精度的固有矛盾,
Malkov 等人 [21] 提出了以构建小世界网络特性的邻近图为特征的 NSW 索引, 其长链接负责实现高效的全局路由,
而短链接则保障了在目标区域内的局部精确查找, 从而首次在查询效率与召回精度间取得了良好的平衡. 此后的
研究大多聚焦于如何构建拓扑更优的邻近图, 其中最具影响力的是 HNSW 索引.
除了在算法层面优化索引拓扑以提升效率与精度外, 索引的可扩展性, 特别是如何将图索引部署于超过单机
内存的海量数据集上, 是该领域的另一大挑战. 为了应对此挑战, 研究人员提出了多种基于外存的图索引方案. 其
中, 以 DiskANN [34−36] 和 SPTAG [37] 为代表的工作影响最为深远, 其核心思想在于构建一种内存-磁盘混合架构: 在内
存中仅保留一个小型的稀疏导航图, 而将包含完整连接信息的全量数据存储于磁盘. 查询时, 首先利用内存中的导
航图快速定位至磁盘上的一个或多个粗粒度区域, 随后通过精心设计的磁盘 I/O 策略, 高效地读取局部图结构以
完成最终的精确查找. 这种分层处理机制以可控的 I/O 开销与精度损失为代价, 成功地将图索引的应用扩展至 10
亿规模的向量数据集.
在众多基于图的内存索引中, 由 Malkov 等人 [29] 提出的 HNSW 索引结合了层级化图结构与高效的邻居选择
策略, 在性能上取得了重大突破, 已成为当前应用最为广泛的向量索引之一. HNSW 的卓越性能主要源于以下两
大核心机制.
● HNSW 的层级化图结构. 为加速搜索过程, HNSW 引入了一种多层图的组织方式. 如图 2 所示, 该结构以包
含了所有数据点的底层稠密图 (第 0 层) 为基础结构, 保证了查询的高召回率. 同时, 通过对下层节点进行概率性
采样, 构建出上层稀疏图作为实现远距离跳转的快速路径. 在插入新节点时, 算法会依据一个指数衰减的概率分布
函数为其随机指派一个最大层数 l max , 并将该节点添加至从 0 到 l ma 的每一层图中. 该层数通过对一个服从指数
x