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

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

2.2.2 基于倒排的方法
(1) 构建策略
倒排文件索引 (inverted file (IVF) index) 通过聚类缩减了搜索范围从而提升搜索速度, 图 2 展示了一个基本
的 IVF 索引结构. 高维空间被划分成 Voronoi 图 [62] , 向量数据点根据聚类算法被划分为若干簇 (Voronoi 单元), 每
个簇被一个质心代表, 索引会记录质心及其代表的簇中包含的向量数据点的信息. 对于一个查询点 q, 首先计算得
到所有质心中与 q 距离最近的质心, 再在该质心对应的簇中通过线性扫描簇中的向量数据点来得到该簇中离 q 最
近的 (若干) 数据点作为搜索结果. 受边际效应的影响, 当查询点距离簇分界线较近时, 搜索可能无法得到正确的
结果. 可以通过搜索多个簇来提升搜索结果的召回率, 但由于遍历了更多数据, 搜索的速度会减慢. 算法库 Faiss
(Facebook AI similarity search) [29] 与向量数据库 Milvus [63] 实现了 IVF_FLAT (FLAT 代表簇中记录的是未被压缩或
量化的原始数据) 索引.

质心列表
倒排列表C 2
C 2
C 1
C 1
C 2
C 4
C 3
C 3
C 4
图 2 IVF 索引结构图

一些工作进一步优化了倒排方法. Tribase [64] 细粒度地划分了聚类, 根据子聚类的不同特征选择不同的搜索方
法, 并结合了距离与角度的三角不等式以提升剪枝效果. SC [65] 用子空间碰撞度量 SC-score 来近似欧氏距离, 给出
了误差的理论分析, 并进一步为搜索框架 SC 设计了一种基于聚类的轻量化索引与搜索策略 Suco.
稀疏向量由于其良好的可解释性, 在信息检索中发挥越来越重要的作用, 基于倒排方法来索引稀疏向量取得
了很好的效果. 文献 [66] 提出基于倒排的索引方法 SEISMIC, 取得了比基于图的方法更高的搜索效率. 文中指出,
稀疏向量的 L1 范数主要由少部分的高权重坐标贡献, 两个向量的内积也可以由少部分的坐标有效地近似. 基于这
一发现, SEISMIC 在构建倒排索引时对每个倒排列表中的数据按照权重排序, 进行静态剪枝, 减少检索时需要评
估的数据数量, 并通过 K-means 聚类将倒排列表进行分块, 构建摘要向量, 在搜索时以整体跳过整个子块来提高搜
索速度. 实验结果显示其拥有较低构建时间, 占用较小存储空间, 在保持较高召回率的同时具有更快的检索速度.
(2) 更新策略
SPFresh [67] 是一个支持 10 亿级向量搜索和更新的系统, 其核心是轻量级增量再平衡协议 LIRE. 该研究针对高
维向量索引更新存在的全局重建成本高、查询性能波动剧烈等问题, 创新地将传统索引的全局重建过程解耦为局
部动态调整机制. SPFresh 基于平衡聚类索引框架 SPANN 构建基本索引结构, 通过维护向量分区的最近邻分配属
性 (neighbor posting assignment, NPA), 在数据分布发生偏移时仅需对边界区域的少量向量进行再分配. LIRE 协议
包含分裂、合并、重新分配这 3 类核心操作, 图 3 是这 3 类操作的示意图, 当分区向量数超过阈值时, 通过多约束
平衡聚类算法将其拆分为两个新分区, 并基于必要条件检查触发相邻分区的向量再分配; 对于过小分区则采用最
近邻合并策略, 删除冗余质心后重新校准向量归属. 与传统全局重建方法相比, LIRE 通过限定影响范围 (仅检查分
裂质心最近的 64 个邻居分区) 和版本控制机制 (维护向量复制版本号), 将再平衡操作的计算复杂度从 O(N) 降至
O(1) , 有效地解决了数据持续更新导致的分区失衡和查询准确率衰减问题.
SPFresh 在更新方面进行了系统架构的设计: 更新器采用尾部追加策略将新向量写入最近邻分区, 并维护版本
映射表记录逻辑删除; 本地重建器通过多线程并发执行分区分裂、合并及再分配操作, 采用细粒度分区锁保证原
子性. 在存储层设计了用户态块控制器, 绕过传统文件系统直接管理 NVMe SSD 块, 通过预分配空闲块池和批量
异步 I/O 请求队列实现高吞吐量访问. 为了实现崩溃恢复机制, 系统结合周期性快照与预写日志机制, 利用快照及