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

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

而准确的检索, 其基本思想是相近的点其 Z-order 值也相近, 最终的索引结构是由多棵 LSB-tree 组成的 LSB-forest.
文中指出, 两棵树就可以取得很好的搜索效果. HD-index [98] 是一个基于磁盘的索引方法. 文献 [98] 提出基于
Hilbert [99] 空间填充曲线的 RDB-tree 来对数据进行组织. PM-LSH [100] 利用 PM-tree [101] 来组织投影后的数据.
DET-LSH [102] 通过动态编码树 (DE-Tree) 来编码根据数据分布投影后的向量, 以提升索引的构建效率. DET-LSH 将
动态编码树与基于局部敏感哈希的方法结合, 通过两阶段的搜索方式提升召回率.
2.6 小 结
在实际中要基于数据量、业务场景以及成本等选择不同索引方案 [63] , 并在搜索性能、空间占用开销和维护
难度等方面做出取舍. 针对只有几千条数据的小数据量场景, 无须维护复杂的索引结构, 采用直接搜索全部数据
的方案就能够满足要求; 对于一些维度相对较低的数据, 采用基于树的方法, 如 Annoy [59] 也可以很好地完成相关
查询任务 [63] ; 面对搜索大量向量数据的情况, 基于图的方法, 如 HNSW、NSG 等方案的优秀搜索性能支持完成
大部分任务. 但是, 仅使用基于图的方案并非适用于每个场景, 如表 3 所示, 其具有空间占用高、更新维护困难
等问题, 当面对 10 亿级别大规模向量搜索以及数据动态更新频繁的业务时, 基于图的方法将面临巨大挑战, 此
时就需要考虑更多的方法来找到解决方案, 并在搜索性能、维护代价、价格成本等之间取得平衡, 支撑上层业
务平稳运行.
当面对的数据规模很大, 如超过 10 亿规模的情景, 内存资源有限导致无法在内存中存储全部数据的情况时,
使用 PQ、RaBitQ 等量化方法存储有损数据可以适配有限的内存空间. OG-LVQ 方案提供了将图和量化进行结合
的方案, 并且不要求在索引中存储原始的向量数据, 有效地降低了内存的占用, 在获得较高的查询速度的同时保证
较高的召回率. 除了面向内存的方案, 还可以选择面向硬盘的方案以解决内存空间限制导致超出了单机处理能力
的问题, 此时 DiskANN 等基于磁盘内存混合的索引方法可以有效地完成任务; 向量数据库在数据动态变化的场景
中面临着处理更新的挑战, 基于图的方法面临着更新困难的问题, 选择基于倒排文件 (IVF) 等构建速度快、维护
难度低的索引可以很好地平衡维护成本与查询性能的关系, SPFresh 设计基于倒排的更新方案取得了良好的效果.
此外, 将倒排和量化方法进行结合使用是一个经常被采用的搜索方案. 局部敏感哈希方法具有理论保证, 可以用于
需要精度质量承诺的场景中, 对搜索结果提供可量化的性能边界和可靠性支撑.
3 向量数据搜索优化方法

随着人工智能的发展, 向量近似最近邻搜索发挥了日益关键的作用, 在获得越来越广泛关注的同时, 应用场景
也更加复杂多样, 在效率、精度和可扩展性等层面面临严峻的挑战. 为了应对挑战, 实现更高效的搜索以支持越来
越广泛的应用场景, 近年来很多研究工作从多个维度探索, 包括硬件加速、距离比较操作优化、数据访问优化等
研究方向, 并取得了一系列的成果, 共同推进构建了高维向量搜索的解决方案.
本节系统性地梳理近年来的研究成果, 依据不同技术路径的差异, 从面向硬件加速、面向学习增强、面向
距离比较操作、面向磁盘内存混合场景、面向数据访问优化、面向分布式场景、面向混合查询场景和理论分
析这 8 个方面对相关工作进行梳理. 表 5 从核心思想、典型方法、优势和局限性这 4 个方面概括展示了整体的
优化方法.

表 5 向量搜索优化方法总览和对比展示

分类维度 核心思想 典型方法 优势 局限性
面向硬件加速的 利用硬件特性加速搜索 AVX指令集、GPU加 能够大幅提升吞吐 硬件成本高, 移植复杂度高
优化 速、多线程等 量, 降低延迟
面向学习增强的 利用机器学习方法来挖掘 Neural LSH [103] 、 适应数据分布, 减 训练复杂度高, 模型泛化性
优化 数据特性 BLISS [104] 等 少冗余计算 要求高
对算法设计要求高, 并且收
[105]
面向距离比较操 定位算法高开销部分, 设计 ADSampling 、 降低计算代价, 通 益受到数据的维度、分布特
作的优化 优化算法降低距离计算 PEOs [106] 等 用性强
性等影响