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

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

的交集与并集来完成. 在实际中, Jaccard 相似度用 minhashing [27] 来加快计算速度, 实现对文档的重复度计算等.

2 向量数据索引组织方法

为了实现高效的近似最近邻搜索, 研究工作主要聚焦于通过设计索引对高维向量数据进行组织, 以空间换时
间为原则, 将无序的向量数据系统性地、结构化地组织成高效的索引以提升搜索性能. 面对低延迟高精度的近似
最近邻搜索的需求以及维度灾难带来的挑战, 需要对高维向量的内在结构和分布规律进行深度的挖掘, 优化索引
组织以提升性能.
向量索引组织的经典范式一般将高维向量索引的组织分为树、图、哈希、量化、倒排等方法, 如在文献 [4]
中将索引组织分为 3 种类型: 基于表格 (包含哈希、量化等)、基于树以及基于图的方法, 在文献 [9] 中分别从图、
哈希和树这 3 个分类上进行描述. 本文在向量数据索引组织的经典分类范式的基础上结合经典的研究工作和最新
的研究成果来展示内在的设计原理和优化思路. 本文在已有研究工作和综述分类的基础上, 进一步地将组织方法
分为 5 大类: 基于图的数据组织方法、基于层次的数据组织方法、基于哈希的数据组织方法、基于量化的数据组
织方法和混合数据组织方法, 并在这一分类的基础上进一步详细介绍各个方法, 表 3 是对所有组织方法的总体对
比展示.

表 3 向量数据索引组织方法总览

代表性方法 原始数据 维护 构建 数据访问 内存 磁盘
数组组织方法 关键方案
举例 存储 难度 速度 方式 占用 支持
多层图 HNSW [28] 是 高 慢 随机 高 否
基于图的数据组织 [17]
单层图 NSG 是 高 慢 随机 高 否
倒排结构 IVF [29] 是 低 快 顺序 中 否
基于层次的数据组织
基于树的结构 k-d tree [30] 是 低 中 顺序 中 否
局部敏感哈希 QALSH [31] 是 中 快 混合 低 是
基于哈希的数据组织 [32]
学习 (二进制) 哈希 GPH 是 中 快 顺序 低 否
乘积量化 PQ [33] 否 低 快 顺序 低 否
基于量化的数据组织
标量量化 RaBitQ [34] 否 低 快 顺序 低 否
OG-LVQ [35] 否 高 中 随机 低 否
图+量化
DiskANN [36] 是 高 中 随机 低 是
图+树 SPTAG [37] 是 高 慢 随机 高 否
混合数据组织
图+哈希 LSH-APG [38] 是 高 中 随机 高 否
倒排+量化 IVFPQ [39] 否 低 快 顺序 低 否
哈希+树 SRS [40] 是 中 快 混合 低 是

表 3 主要从 6 个角度进行总体对比, 并包含其关键方案和代表方法举例, 并结合代表性方法对关键因素进行
分析. 当向量数据库中的数据被更改时, 需要维护的索引进行对应的更新, 维护的难易程度是一个需要考虑的关键
因素. 当增量索引维护出现性能退化时, 往往需要执行索引重建. 在大规模向量数据场景下, 索引构建速度成为不
可忽视的关键因素. 许多向量索引是基于内存的索引, 当针对的是大规模数据构建索引时会占据大量内存资源, 索
引的内存占用开销就是一个关键的因素. 一些索引组织方法仅存储量化后的数据而并非原始数据, 一方面, 这种做
法可以减少空间消耗, 另一方面也会影响搜索精度, 考虑索引是否存储原始数据对分析其空间占用和搜索性能十
分重要. 面向大规模数据和内存资源受限场景, 索引是否支持磁盘是一个十分重要的衡量因素. 磁盘的随机访问性
能往往低于顺序访问性能, 同样, 内存的顺序访问因为能够有效地利用缓存预取而能获得相较于随机访问更快的
速度, 分析不同方法的数据访问方式有助于评价并优化索引.
2.1 基于图的数据组织方法
基于图的方法在高维向量近似最近邻搜索中取得了优异的性能 [28] . 其主要思想是将数据点视为图中的节点,