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

宋子文 等: 向量数据库中近似最近邻搜索关键技术综述 993

性减少 I/O, 同样可以在大规模数据下达到高召回率, 但其基于图的算法, 面临着构建时间很长的问题, 且难以应对
索引更新的场景.
3.5 面向数据访问的优化策略
向量搜索的性能同时受到计算代价和数据访问代价的影响, 尤其是在基于图的方法中, 数据的随机内存访问
方式导致 cache 的预取操作失效, 带来了高昂的访存代价, 通过优化数据的访问可以提升搜索的性能. 当前提出了
很多方法来优化数据的访问方式, 主要包括: (1) 数据重排序优化, 通过改变数据的存储顺序来提升数据的访问性
能; (2) 数据预取优化, 数据预取是通过提前加载数据到缓存中来提升数据的访问性能; (3) 数据压缩优化, 通过压
缩数据来降低数据大小从而 减少访问代价.
(1) 数据重排序优化
在图的搜索中, 需要不断地访问邻居节点的数据. 文献 [143] 指出, 40% 的时间消耗在内存访问上, 尤其是向
量数据的获取, 如果能够优化相关时间, 将能极大地提升搜索性能, 基于此, 提出了数据布局优化的方法, 通过调整
节点的内存布局, 使相邻节点的数据在内存中邻近存储, 利用硬件预取机制减少缓存缺失, 从而加速查询. 文章在
理想化缓存模型下分析图遍历成本, 依据经典的图重排序方法 [143] 进一步优化, 提出了基于查询的加权重排序算
法 Porder 来优先优化重要的邻居节点, 实验结果表明, Porder 实现了最多 40% 的延迟减少, 为后面的图索引优化
提供了新方向.
Starling [142] 是一个面向磁盘图索引方案的内存布局优化方法. 它提出一个基于磁盘的重排序方案来增强数据
访问的局部性, 减少磁盘访问的开销. 它首先采样部分向量数据, 在内存中构建导航图以实现在内存中快读定位接
近查询点的邻居节点, 减少磁盘 I/O 开销. 对于磁盘中的数据, 采用块重排将相邻顶点尽可能存储在统一磁盘块中,
提升数据局部性, 使得单次磁盘 I/O 能加载更多相关数据. 文献 [142] 证明块重排序问题是 NP 难问题, 提出启发
式策略来进行近似求解. 实验结果表明, Starling 方案实现了 43.9 倍的吞吐量提升. 此外, 通过优化布局还可以加
速索引的构建速度, Flash [144] 通过优化数据布局同时充分利用 SIMD 来加速图索引的构建速度. PDX [145] 针对 IVF
索引方法设计垂直布局方案来优化搜索速度.
(2) 数据预取优化
数据的随机访问限制了数据的硬件预取, 但是可以通过软件预取的方式预判数据的访问模式, 将数据提前加
载进缓存中以提升数据的访问性能. VSAG [146] 提出了利用预取来进行数据的访问优化的方法. 它包括软件预取和
硬件预取优化两个部分. 软件预取是通过分析数据的访问模式来提前加载数据到缓存中提升缓存命中率. VSAG
通过提前将还没有被访问过的点预取到缓存中来提升数据的访问性能, 针对可能发生的缓存驱逐问题, 进一步提
出了基于步长的预取方案以根据计算速度确定预取时机, 避免了缓存的驱逐问题. 硬件预取是通过利用 CPU 的硬
件预取机制来提升数据的访问性能, VSAG 通过根据服务器的负载状况将邻居节点的数据额外存储在连续内存位
置的冗余向量存储方法来实现顺序内存访问.
(3) 数据量化优化
通过量化后降低要处理的数据, 可以减少内存中的数据量, 从而降低需要处理的数据总量, 具有处理更多数据
点的能力. 通过量化的方法可以压缩数据量, 代表性方法如 NGT-QG [147] 、OG-LVQ [35] 和 SymphonyQG [108] .
SymphonyQG 是一个利用最新的 RaBitQ [34] 量化方法和图方法协同集成的索引方案. 它结合了量化和利用布局两
种优化手段. 通过调整图拓扑结构, 将图的每个节点 p 的邻居节点数据的量化编码连续存储在 p 所在位置的邻近
内存中, 避免了访问邻居节点时随机访问的开销, 由于存储的是量化数据, 因此减少了重复地存储节点带来的内存
开销, 通过空间换取时间的方式提升了查询性能. 相较于 NGT-QG 方案, SymphonyQG 能够提供更准确的距离估
计, 并且其避免了显式的重排序从而降低了内存访问开销. 此外, RaBitQ 的量化方法的高计算效率, 加速了图的构
建. 实验结果显示, SymphonyQG 在内存中实现了最多 4.5 倍的查询性能提升.
3.6 面向分布式场景的优化
面对大规模数据, 单机难以进行处理, 采用分布式的处理方法将数据分片到多台机器上协同处理是一个可行