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

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

∆ 中 (第 10 行).
中, 算法会尝试从 ∆ 读取邻居点的邻居列表 N n , 如果其不存在于 ∆ 中, 则从磁盘进行读取并加入至
如果邻接出边集合有所更新则写回至磁盘.

算法 2. 合并操作删除算法.
输入: 磁盘基本层层级索引L 1 , 增量数据存储结构∆;
输出: void.
1. begin
Iter 1 ← L 1 .GetIterator() //初始化磁盘基本层索引迭代器
2.
3. while Iter 1 .HasNext()
(loc q , x ,N q ) ← Iter 1 .Next() //依次遍历所有点
4.
q
if loc q is deleted
5.
delete x q and add N q to ∆ //实际删除点并缓存邻居列表
6.
7. else
8. foreach n in N q
9. if n is deleted
if ∆ not contains N n then read N n from disk and add to ∆ //若缓存未命中则读取磁盘
10.
( )∪
11. N q ← RobustPrune( N q /{n} N n ) //对删除点进行修补
12. endif
13. endfor
14. endif
15. endwhile
16. end
(2) 插入阶段. 如图 7 合并操作插入阶段示意图所示, 本文设计了两个迭代器, 分别是磁盘索引的全量扫描迭
代器和多磁盘索引间迭代器, 插入流程如算法 3 所示: 首先, 每次从磁盘中间层迭代器获取一个需要插入的点 (第
4、5 行); 然后, 从磁盘基本层迭代器获取一个空闲的可插入位置 (第 6–12 行), 如果获取到一个可插入位置 loc, 则
以插入点 x q 为查询向量在磁盘基本层索引中获取新的邻接出边集合 (第 13–16 行); 最后, 将插入点向量 x q 及其邻
N q 插入至磁盘基本层索引的可插入位置 (第 17 ∆ 结构
接出边集合 行), 并且同时将每条邻接出边的反向边暂存至
中 (第 18 行).

当前组件指针
磁盘中间层
磁盘组件 磁盘组件 磁盘组件 磁盘组件

当前位置指针
磁盘基本层 空闲位置指针 插入

磁盘组件

图 7 合并操作插入阶段示意图

算法 3. 合并操作插入算法.
输入: 磁盘中间层层级索引L 0 , 磁盘基本层层级索引L 1 , 增量数据存储结构∆;
输出: void.