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

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

first stage rapidly navigates from an entry point to a region near the query vector, while the second stage searches for the k nearest
vectors within the localized region. However, due to the need to store a large number of adjacency relationships, graph-based indexes often
incur high memory overhead. In practice, this leads to storing the index in external memory, where vector and graph data are loaded on
demand during ANNS. This results in frequent I/O operations, which have become the primary bottleneck, accounting for over 90% of
total query time. Existing systems exploit the fact that entry points and their nearby neighbors are frequently accessed, and adopt static
caching strategies that preload these points and their multi-hop neighbors into memory to reduce I/O during the first stage. However, this
study finds that the second stage contributes the majority of I/O cost, as it involves accessing a large number of graph vertices related to
the query vector to ensure high recall. Since the accessed vertices in this stage vary dynamically with each query, static caching strategies
fail to capture them effectively and thus become nearly ineffective. To address this issue, a hybrid caching strategy termed GoVector is
proposed, which integrates both static and dynamic components. Specifically, (1) the static cache preloads the entry point and its frequently
accessed neighbors, while (2) the dynamic cache adaptively stores high-locality vertices encountered during the second stage of the search.
Furthermore, to align with the similarity-driven search behavior of the second stage, a vector-similarity-aware disk layout strategy is
proposed, which reorganizes the storage order of vertices to cluster similar vectors into the same or adjacent disk pages, thus enhancing
data locality. This dual-optimization approach significantly improves cache hit rates and effectively reduces overall I/O overhead.
Experimental results on multiple public datasets demonstrate that, under 90% recall, GoVector achieves an average of 46% fewer I/O
operations, 1.73× higher query throughput, and 42% lower latency compared to state-of-the-art disk-based graph indexing ANNS systems.
Key words: high-dimensional vector; approximate nearest neighbor search (ANNS); graph-based index

随着大语言模型 (large language model, LLM) 等生成式人工智能技术的迅速发展, 向量化语义检索在自然语
言处理 [1,2] 、信息检索 [3,4] 和推荐系统 [5,6] 等多个应用中起到关键作用. 特别是在检索增强生成 (retrieval-augmented
generation, RAG) 技术中, 向量语义检索已成为提升生成质量与响应效率的关键机制 [7] . 为了应对高维向量检索的
复杂性 [8] , 近似最近邻搜索 (approximate nearest neighbor search, ANNS) 技术得到广泛应用, 其中基于图的索引方
[9]
法, 如 HNSW 、NSG [10] 、DiskANN [11] 等凭借低延迟、高精度与高吞吐量的特点, 受到学术界和工业界的广泛关
注 [12−15] . 然而, 索引图需显式存储大规模向量之间的邻接关系, 导致索引本身消耗大量存储空间. 随着向量规模不
断扩大, 将全部索引常驻于内存变得代价高昂, 因此越来越多的系统采用基于磁盘的 ANNS 方案, 将索引图部分
或全部存储在磁盘中, 以降低内存压力并提升系统可扩展性 [11,16] . 其中, 以 DiskANN 为代表的基于磁盘的索引图
技术被广泛集成于业界高性能向量数据库系统 (如 Pinecone [17] 、Milvus [18] ) 中, 以支持千亿规模向量数据的高效检
索. 这类方法的核心是从入口顶点开始拓展, 每次从磁盘中加载拓展顶点所在的磁盘页 (page), 以获取其向量信息
及邻接顶点, 并根据邻接顶点与查询向量的距离选择下一次的拓展顶点.
然而, 这种基于磁盘的索引图方法普遍面临严重的 I/O 性能瓶颈. 我们在 5 个真实数据集 [8] 上对当前最先进
的两个基于磁盘的 ANNS 系统 (即 DiskANN 和 Starling [16] ) 的查询性能进行了详细分析. 图 1 展示了在 90% 的召
回率下, 两个系统在不同数据集上的查询过程中, I/O 操作与 CPU 计算所占总耗时的比例. 实验结果表明, I/O 操作
在整体查询延迟中占据主导地位, 在 DiskANN 系统中, I/O 操作平均占比高达 83%, 在 Starling 系统中达到 79%.
这一结果说明, 磁盘访问已成为制约系统整体性能的主要瓶颈.

DiskANN-CPU Starling-CPU GoVector-CPU
DiskANN-I/O Starling-I/O GoVector-I/O
归一化查询时间占比 (%) 100
80

60
40
20

0
SIFT DEEP TINY MSong GIST
图 1 ANNS 系统查询阶段 I/O-CPU 时间占比及查询时间对比