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

1030 软件学报 2026 年第 37 卷第 3 期

frequency) 算法, 试图将图中相邻顶点聚集在同一块中. 这种方法忽视了图结构与向量空间之间的结构差异, 无法
充分保证相似向量的物理邻近性, 进而限制了 I/O 局部性的进一步提升. 图 8 展示了不同方法的存储布局与缓存
命中情况 (假设没有静态缓存). 图 8(a) 为索引图结构; 图 8(b) 展示了 DiskANN、Starling 与 GoVector 的存储布局
结果, 均假设每页最多容纳 3 个顶点; 图 8(c) 模拟了从入口点开始进行搜索的拓展过程, 并记录了每一轮拓展顶点、
候选优先队列, 以及当前页面是否命中下一个拓展顶点. 实验过程中, 从入口点 v 0 出发, 系统依次拓展点 v 0 ,v 3 ,v 6 ,
并维护候选队列. 由于 v 6 距离查询点最近, 因此第 3 轮拓展 v 6 后进入第 2 搜索阶段, 此时的候选队列为 {v 4 ,v 7 ,
v 5 ,v 8 ,v 1 }, 下一拓展点为 . 若采用 DiskANN 的存储策略, 由于 v 6 与 v 4 存储于不同磁盘页, 会产生两次磁盘 I/O 操
v 4
作; 在 Starling 的布局下, 二者分布于不同页面, 则仍需两次磁盘 I/O 操作. 直至搜索结束, 两种存储布局均因划分
不合理, 导致单次 I/O 的数据利用率低下. 尽管可以通过扩大缓存容量或引入异步加载机制来缓解 I/O 开销, 但如
果能设计出更合理的索引布局方案, 将以更低成本取得更显著的性能提升.

下一个拓展点是否命中当前页
索引页面存储布局 拓展顶点 候选队列
DiskANN Starling GoVector
DiskANN Starling GoVector
类 1 v 0 v 3 , v 8 , v 1
入口点 类 2 v 3 v 6 , v 7 , v 8 , v 1
类 3 v 0 , v 1 , v 2 v 0 , v 3 , v 8 v 0 , v 1 , v 8
v 3
v 0 v 6 v 4 , v 7 , v 5 , v 8 , v 1
查询点
v 4 v 7 , v 5 , v 8 , v 1
v 8 v 6 v 3 , v 4 , v 5 v 1 , v 2 , v 7 v 2 , v 5 , v 9
v 7 v 7 v 5 , v 2 , v 8 , v 1
v 4
v 1
v 6 , v 7 , v 8 v 4 , v 5 , v 6 v 4 , v 3 , v 6 v 5 v 2 , v 9 , v 8 , v 1
v 5
v 2 v 2 v 9 , v 8 , v 1
v 9
v 9 v 9 v 7
v 9 v 8 , v 1
v 8 v 1
(a) 索引图结构 (b) 不同方法的存储布局 (c) 不同方法缓存命中情况
图 8 基于向量相似性的索引图重排序

5.2 基于向量相似性的索引图重排序方法
针对现有布局方法存在的局限性, 本文提出了一种结合向量相似性与存储重排的索引图布局优化策略, 以提
升磁盘访问效率与整体检索性能. 具体来说, GoVector 通过以下两个阶段实现索引图的重排序.
(1) 相似性聚类阶段: 基于向量空间中的欧氏距离, 采用 K-means 聚类算法 [31,32] 将全部向量划分为多个高相似
度簇, 每个簇内的向量在向量空间中彼此接近.
(2) 局部性优化阶段: 在聚类结果基础上, 结合索引图的拓扑结构, 将同一簇内的向量尽可能分配至相同或物
理相邻的磁盘页中, 以最大程度地降低查询过程中的跨页访问频率.
图 8 展示了该重排序方法的过程与效果. 首先, 系统在原始向量空间中应用 K-means 聚类算法, 将向量划分为
类 1–类 3, 对应的索引图结构如图 8(a) 所示. 随后, 在每个聚类内部, 系统进一步基于图拓扑中顶点之间的连通性
进行顺序重排. 以类 3 为例, 其中包含的顶点集合为 {v 2 ,v 4 ,v 5 ,v 9 }, 但由于磁盘页面大小存在限制, 系统在排序时优
先将 {v 2 ,v 5 ,v 9 } 顺序组织在同一页面中, 因为这 3 个点相对于 v 4 更接近所在类的质心, 而边缘的顶点 v 4 则被安排在
下一个页面中, 最终重排后的布局结果如图 8(b) 中 GoVector 所示. 在实际查询过程中, GoVector 能够有效提升单
次 I/O 的数据利用率. 例如, 以传统 Beam Search 算法为例, 当拓展顶点 v 3 时, 系统会加载 v 3 所在的磁盘页. 然后继
v 3 在 GoVector 存储布局下处于同一磁盘页, 因此可以减少一次磁盘 I/O, 充分利用了上
续拓展顶点 v 6 , 由于 v 6 与
一次的 I/O 带宽. 图 8(c) 对比了不同存储布局策略下的实际缓存命中情况. DiskANN 使用向量插入顺序或随机分
布方式进行磁盘存储, 完全忽略向量之间的相似性关系, 导致在查询过程中, 相似向量往往被分散在不同磁盘页
中. 在本例中, 由于下一个拓展点都无法命中当前页, 因此需要执行更多次 I/O 操作, 造成极高的 I/O 开销. Starling
采用图拓扑结构作为分布依据, 将拓扑邻居尽可能聚集于同一磁盘页中, 能够在一定程度上缓解跨页问题. 但在
ANNS 的第 2 阶段, 拓展路径是由向量与查询点之间的相似性驱动, 而不是由拓扑结构决定的. 由于图结构与相似
性结构之间并不总是一致, Starling 的布局方式难以精准覆盖实际访问路径中那些具有空间聚集性的热点区域.
GoVector 首先通过聚类方法识别出向量空间中高相似度的局部区域, 然后在每个聚类内结合图拓扑结构进行局