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

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

由此, 提出磁盘中间层的搜索算法 (算法 5): 首先初始化各层中间结果集并准备好各层级索引查询所需要排
D (第 2–9 K 近邻查询 (第 10–16 行), 其中给定一次 K 近邻查
除的删除键集合 行), 然后再对各层级索引分别进行
询, 对于组件距离小于搜索阈值 D th 的组件, 则认为更有可能包含最终结果, 使用本层的标准搜索参数 L s = L s 0 ;对
于组件距离大于搜索阈值 D th 的组件, 则认为不太可能包含最终结果, 使用最低限度的搜索参数 L s = K 以保证搜
索的理论正确性 (第 11–14 行). 最后再把过滤后的结果进行聚合并返回 (第 17–19 行).

算法 5. 磁盘中间层搜索算法.
;
输入: 查询向量x q , 返回结果集大小K, 磁盘中间层层级索引L 0 , 磁盘中间层搜索列表长度参数L s 0
输出: 最终结果集V.
1. begin
2. R ← [∅ for i in 0..n−1] //初始化中间结果集数组
V ← ∅ //初始化最终结果集V
3.
4. I = [I 0 ,...,I n−1 ] ← L 0 .GetIndexes() //获取磁盘中间层索引组件
5. I ← sort I by each version number DESC //按照生命周期从新到老排序
6. D ← [∅ for i in 0..n−1] //初始化删除键集合
7. for i ← 1 to n−1 //按照生命周期从新到老构建删除键集合
8. D i ← D i−1 + I i−1 .GetDeleteS et()
9. endfor
10. for i ← 0 to n−1
11.
L s ← L s 0
( ) //动态决定搜索参数
12. if Dist x q ,I i > D th
L s ← K
13.
14. endif
( ) //对各组件分别进行KNN查询
15. R i ← KNNQuery I i , x q
16. endfor
17. for i ← −1 to 1 // 将查询结果进行聚合
18. V ← V ∪R i
19. endfor
20. end

3.3 面向合并操作删除阶段的磁盘索引重布局算法
如第 3.1.6 节所述, FreshDiskANN 中的合并操作需要 3 趟顺序读操作, 其中删除阶段需要 2 趟顺序读操作, 从
而引发大量磁盘 I/O 操作.
回顾第 2.3 节对合并操作删除阶段过程的描述, 假如所有数据均位于内存中, 理论上仅需扫描 1 趟即可完成.

但由于未删除点 P 1 的邻居可能包含被标记为删除的点 P 2 , 而 P 1 与 P 2 并不总是同时被加载进内存, 如图 9(a)
1 P 1 则需要进行一次随机读. 因此原
所示, 当 P 1 处于 P 位置, 目前迭代器遍历至黄色区域内的删除点 P 2 , 此时修补
1
方法必须进行额外的一轮全量读取以避免可能引发的大量随机读.
为了解决该问题, 如图 9(a) 所示, 由于顺序读取带来的先后顺序, 当 P 1 处于位置 P 、 P 和 P 时, 无须引发一
2
3
4
1
1
1
P 1 同时或之前被顺序读入内存, 即如图 9(b) 所示, 希望
次随机读操作. 基于上述观察, 改进的目标是尽量让 P 2 与
每个点的物理位置在它的邻接入边邻居前且在它的邻接出边邻居后, 以减少随机读取操作并提升效率.
受 Starling [26] 中面向查询操作的磁盘重布局算法启发, 本文提出了一种面向合并操作删除阶段的磁盘索引重
布局算法. 与 Starling 中面向的优化场景是索引搜索操作不同, 本文的重布局算法聚焦于合并操作删除阶段的优