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

邱海浪 等: LSMDiskANN: 更新友好型磁盘向量索引框架 1065

● 磁盘基本层组件: 相当于 FreshDiskANN 的磁盘层, 包含一个长期存储的 DiskANN 索引. 该层组件承载系
统的绝大多数数据, 生命周期最长. 合并时不做就地修改, 而是通过重建新组件并原子替换的方式完成结构更新,
确保查询操作不受影响.
3.1.2 插入/删除操作
插入与删除操作仅作用于内存层的读写组件, 具体流程遵循 FreshDiskANN 中的实现.
为了支持删除操作, 本文采取主动 (eager) 策略: 每个非磁盘基本层组件都维护一个删除键集合, 用于标记相
对于其更老的组件中需要被逻辑删除的向量. 换句话说, 一个组件中实际可用的数据需排除所有更年轻组件中记
录的删除键. 为减少查询时删除键集合的访问成本, 每一层还维护一个合并删除集合, 作为本层所有组件删除集合
的并集, 用于快速过滤比当前层更老的层中的已删除向量.
3.1.3 查询操作
查询操作需要跨多个层级进行, 因此本文设计了多层索引查询算法 (见算法 1, 其中 L −1 、L 0 、L 1 分别对应于
内存层、磁盘中间层和磁盘基本层).
算法 1. 多层索引查询.

输入: 查询向量x q , 返回结果集大小K, 层级索引集合L = [L −1 ,L 0 ,L 1 ];
输出: 最终结果集V.
1. begin
2. R ← [∅ for i in −1..1] //初始化中间结果集数组
3. V ← ∅ //初始化最终结果集V
4. D ← [∅ for i in −1..1] //初始化删除键集合
5. for i ← 0 to 1 //按照生命周期从新到老构建删除键集合
6. D i ← D i−1 + L i−1 .GetDeleteS et()
7. endfor
8. foreach L i in L
( )
9. R i ← KNNQuery L i , x q ,D i //对各层分别进行K近邻查询
10. endfor
11. for i ← −1 to 1 // 将查询结果进行聚合
12. V ← V ∪R i
13. endfor
V ← sort V by vector distance ASC with limit K //对结果集V按照距离进行排序并保留前K个
14.
15. end

由于不同层级的组件之间数据互不重叠, 为保证数据覆盖的完整性, 查询需在所有层中分别执行, 然后合并结
果并做距离排序. 查询按算法 1 流程执行. 首先初始化各层中间结果集并准备好各层级索引查询所需要排除的删
除键集合 (第 2–7 行), 然后再对各层级索引分别进行 K 近邻查询 (第 8–10 行), 再把过滤后的结果进行聚合 (第
11–13 行), 最后再将聚合结果按距离进行重排序并保留最近的 K 个 (第 14 行).
磁盘中间层的引入虽然提升了更新友好性, 但也带来了一个挑战: 组件数量增加导致的查询冗余. 本文提出以
下 3 种配合使用的策略以有效缓解此问题.
(1) 并行查询策略: 在 FreshDiskANN 中, 其由若干个内存层组件和单个磁盘层组件组成, 其中内存层组件在
搜索时因为不涉及磁盘 I/O, 所以其查询时间相比磁盘层组件搜索可以忽略不计, 采用串行查询即可满足性能需
求. 然而本文框架中磁盘组件数量增加, 且涉及磁盘 I/O, 因此均可以采用并行查询策略, 有效降低查询延迟.
(2) 层间动态搜索参数策略: FreshDiskANN 以统一搜索列表长度 L s 对所有组件进行查询, 由于图索引本身特