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

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

1. begin
2. Iter 0 ← L 0 .GetIterator() //初始化磁盘中间层索引迭代器
3. Iter 1 ← L 1 .GetIterator() //初始化磁盘基本层索引迭代器
4. while Iter 0 .HasNext()
(loc q , x q ,N q ) ← Iter 0 .Next() //获取一个需要插入的点
5.
6. loc ← −1 //初始化插入位置
7. while Iter 1 .HasNext() //获取一个空闲位置
( )
8. loc temp , x temp ,N temp ← Iter 1 .Next()
if loc temp is free
9.
10. loc ← loc temp
11. endif
12. endwhile
13. if loc == −1
14. break
15. endif
16. N q ← KNNQuery(L 1 , x q ) //获取插入点的新邻接出边
insert x q and N q into L 1 ’s loc position //进行实际插入
17.
//缓存反向边
18. ∆ ← ∆∪backward edges of N q
19. endwhile
20. end

(3) 修补阶段. 本阶段负责将 ∆ 结构中暂存的反向边尝试插入磁盘基本层索引中, 修补流程如算法 4 所示: 首
先, 每次从磁盘中间层迭代器获取一个点 (第 2–4 行), 如果该点 x q 需要更新则尝试将 ∆ 结构中对应的反向边
[ ]
∆ loc q 插入该点的邻接出边集合 N q 中 (第 5–8 行), 随后, 根据 Vamana 剪枝策略淘汰部分节点 (第 9 行).
算法 4. 合并操作修补算法.

输入: 磁盘基本层层级索引L 1 , 增量数据存储结构∆;
输出: void.
1. begin
Iter 1 ← L 1 .GetIterator() //初始化磁盘基本层索引迭代器
2.
3. while Iter 1 .HasNext()
( )
4. loc q , x q ,N q ← Iter 1 .Next() //依次遍历所有点
[ ]
5 if ∆ loc q is empty
6. continue
7. endif
[ ]
8. N q ← N q ∪∆ loc q
( )
9. N q ← RobustPrune x q ,N q //对反向边进行修补
10. endwhile
11. end

3.1.6 刷新/合并操作 I/O 分析
刷新操作主要包括数据写入与量化压缩两个阶段. 由于磁盘索引布局仅在内存索引数据基础上调整了存储顺
序, 数据写入阶段几乎等价于内存索引的直接落盘; 而量化压缩阶段的数据量小, 通常能在秒级完成.
如图 4 所示, 相比于 FreshDiskANN 需要对磁盘基本层索引组件进行 3 趟顺序读和 2 趟顺序写, 虽然本文合