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

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

目标近邻. 在典型的索引图方法中, HNSW 通过多层跳跃图结构实现高效的内存搜索; NSG 通过约束图结构的稀
疏性, 优化搜索路径长度和冗余边数; DiskANN 提出了一种面向磁盘的索引图结构, 通过 Beam Search 搜索算法支
持大规模向量检索, 已被集成至 Milvus 等工业系统.
(1) 存储优化技术
存储布局是基于磁盘的索引图系统的核心设计要素, 其物理组织方式直接决定了检索过程中的磁盘 I/O 效率.
当前主流向量数据库系统主要采用两种基础存储策略: 插入顺序存储与哈希分布存储. 插入顺序存储按照向量插
入的时序线性组织数据, 虽然实现简单且写入吞吐量高, 但由于完全忽略向量的相似性, 导致高维空间中相邻的向
量在物理存储上呈现高度离散分布, 使得查询时需要触发大量随机 I/O 操作. 哈希分布存储通过哈希函数实现数
据的均匀分布, 能够有效避免访问热点问题, 但同样割裂了图结构中邻接顶点的物理存储位置, 导致跨页访问现象
加剧.
针对上述问题, 学界提出了多种创新解决方案. 例如, Facebook 的 Faiss-IVFOPQ [23] 通过倒排索引 (inverted file,
IVF) 聚类相似向量, 并配合乘积量化 (PQ) 压缩存储, 同时减少了磁盘寻道次数和单次 I/O 数据传输量. UC Berkeley
提出的 LENS 系统基于查询日志挖掘访问热点, 进行主动预加载, 实验结果表明可将缓存命中率提升约 25% [30] .
(2) 缓存优化技术
为了降低查询过程中的磁盘访问延迟, 现代 ANNS 系统普遍引入缓存机制, 以缓解因图结构跳转不确定性导
致的频繁 I/O 问题. 缓存机制主要通过在查询路径上提前加载部分关键顶点数据, 从而提升查询阶段的数据命中
率与响应效率. DiskANN 等方法通过提前加载访问频率较高的入口顶点及其若干跳邻居, 来减少从磁盘加载数据
的次数. Starling 系统则引入了内存导航图的概念, 依据系统的内存限制, 从整个数据集中随机采样一部分顶点, 并
利用构建算法 (如 Vamana) 在内存中构建轻量级导航图. 该导航图能够高效地为查询向量提供更接近的入口点,
从而显著缩短其在磁盘图上的搜索路径, 有效降低 I/O 负担.

3 方法概览

本文提出 GoVector, 一种基于向量相似性的 I/O 高效向量近邻查询缓存策略. 其方法整体框架如图 4 所示.

1 选择拓展点
候选搜索 搜索
向量队列 5 数据加载
搜索模块 6 计算与拓展
3
3 命中缓存 2 发起数据请求
静 动 3 未命中
态 入口顶点 态 缓存 相似性
缓 缓 感知读取
存 缓存区 存

混合缓存模块
内存 4 选择加载策略
磁盘
聚类信息 索引图信息
#0 #1 #2
id 向量 邻居 id 向量 邻居 id 向量 邻居
…
id 向量 邻居 id 向量 邻居 id 向量 邻居
id 向量 邻居 id 向量 邻居 id 向量 邻居

图 4 GoVector 系统架构图

在内存层面, GoVector 设计了一种静态与动态结合的混合缓存机制, 以适应 ANNS 查询过程中不同阶段的访
问行为. 在静态缓存区, 系统根据预设的容量, 从入口点出发预加载其多跳邻居, 用于快速定位到查询向量附近的