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

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

了降低频繁合并造成的系统性能影响, 本文基于 FreshDiskANN 的架构和索引算法, 将其拓展为内存层、磁盘中
间层和磁盘基本层 3 层架构; 为了降低冗余查询的额外开销, 本文提出了搜索参数动态确定机制, 在层间以及层内
采用不同搜索参数; 为了减少合并操作删除阶段的 I/O 开销, 本文提出了磁盘重布局算法.
综上, 本文的主要贡献包括以下 3 点.
(1) 基于 LSM 思想的更新友好型磁盘向量索引框架. 在 FreshDiskANN 架构基础上, 引入磁盘中间层与刷新
操作, 有效降低合并操作频率, 同时将磁盘中间层作为缓冲区域, 提升了每次合并操作的数据量, 从而增加其中被
更新点的占比, 最终提高 I/O 利用率. 实验结果表明, 该方法最高能够增加 35.5% 查询吞吐量和 14.2% 更新吞吐量.
(2) 搜索参数动态确定机制. 在引入磁盘中间层后, 多层索引结构会带来查询路径冗余问题, 导致查询延迟增
加. 基于“所包含向量数据越多的磁盘索引包含最终结果的可能性越高”的启发式假设, 本文设计了层间动态搜索
参数策略. 进一步地, 结合 DiskANN 中磁盘索引的量化信息反映索引数据分布状况的特点, 本文定义了查询点与
磁盘索引的距离计算方法, 并基于该距离设计了层内动态搜索参数策略. 在查询时采用多种策略相结合以显著降
低查询延迟. 实验结果表明, 该机制平均提升查询 QPS (query per second) 达 65.86%.
(3) 面向合并操作删除阶段的重布局算法. 本文借鉴面向查询操作的向量索引磁盘重布局算法 [26] , 并结合合并
操作删除阶段顺序读取特点, 优化向量索引点在磁盘上的物理排序, 使得原本需要二次顺序扫描的操作转化为“一
次顺序扫描+少量随机读取”, 最终大幅减少合并操作删除阶段的 I/O 开销. 实验结果显示, 该方法平均可降低删除
阶段 41.36% 的 I/O 开销.
本文第 1 节介绍磁盘动态向量索引与 LSM 次级索引相关的研究背景. 第 2 节介绍所需的基础知识, 包括相
关概念的定义、量化压缩与 FreshDiskANN 架构等. 第 3 节介绍本文提出的基于 LSM 思想的更新友好型磁盘向
量索引框架及相关优化. 第 4 节通过对比实验与消融分析验证所提框架的有效性. 第 5 节总结全文.
1 相关工作

1.1 向量索引算法
K 近似近邻搜索 (KANN) 是数据挖掘领域的经典问题, 近年来随着以检索增强生成 (RAG) 为代表的高维
向量检索需求的兴起, KANN 再次成为研究热点. 该领域近年已有多篇综述和基准测试研究 [26−30] , 为理解该领域
发展脉络提供了良好基础. 从技术角度看, 向量索引算法主要分为两大类: (1) 基于图的算法: 将每个向量抽象为图
中的一个节点, 依据特定规则构建索引图 [5,7,8,31] , 查询阶段则借助剪枝策略 [6,32,33] 与图遍历方法 [34] 完成高效搜索;
(2) 基于分区的算法: 可进一步细分为基于树索引的算法 [12,35] 、基于哈希索引的算法 [10,36,37] 和基于倒排索引的算
法 [9,11,38] , 其核心关注以下 3 个问题: ① 如何划分分区; ② 查询时需访问哪些分区; ③ 如何在分区内执行高效搜索,
由此衍生出分区策略、导航策略与执行策略这 3 条研究路径.

1.2 磁盘向量索引
随着自然语言处理等领域中向量表示技术的发展, 为了保留更多原始模态的特征, 向量维度呈现数量级增长,
[40]
从传统的几十维增长至如今常见的数百甚至上千维, 如 DEEP 中的 96 维、GIST 中的 960 维、WIT-Image 中的
[39]
[9]
2 048 维. 同时, 在现今互联网与物联网加持下, 向量数据规模也在呈现数量级增长, 比如 YouTube8M [15] 、
[9] [41]
SIFT1B 、Microsoft SPACEV-1B 等更多大规模向量数据集. 在多种因素影响下, 向量存储压力也随之倍增.
传统向量索引多为纯内存索引, 其假设索引结构和向量数据完全驻留在内存中, 但这一前提在大规模数据场
景下显然不现实. 因此, 近年来大量研究转向基于磁盘的向量索引技术 [11,13,14,42,43] , 其中最具代表性的则是微软提
出的 SPANN [11] 和 DiskANN [13] . (1) SPANN 基于倒排索引, 将倒排列表持久化在磁盘上, 将中心点构建成内存导航
图, 并保证在少量倒排列表遍历下即可完成查询, 从而在保证查询准确性、查询延迟的同时显著节省内存开销. 其
结构简单, 构建速度快, 但为保证高召回率需进行数据冗余存储, 磁盘开销较大. (2) DiskANN 基于图索引, 将原始
向量及邻接表存于磁盘, 仅将量化压缩编码与码表加载到内存中. 在查询时, 通过压缩码进行距离估算, 再结合贪
婪遍历策略逐步读取邻居信息与原始向量, 最终完成精排查询. 得益于图结构的高收敛性, 每次查询需访问的节点