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

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

14. W direct ← direct neighbors number before P i
15. W reverse ← reverse neighbors number after P i
16. W i ← W direct +W reverse
17. if P i is not full and W i > W max
18. W max ← W i ; x ← i
19. endif
20. endfor
21. endif
22. if x = −1 then x ← any free partition //分配一个空闲分区
23. P x ← P x ∪v
24. endfor
25. endwhile
26. end

上述 3 种分配算法的效率虽然较高, 但在应用至系统中时, 仍会引发较大的短期 I/O 开销: (1) 获取原始磁盘
布局信息以及邻接图信息需要对磁盘基本层索引组件进行全量顺序读操作; (2) 在获取到磁盘重布局位置映射信
息后, 根据布局映射重写磁盘索引时需进行大量随机读与全量顺序写.
虽然重布局会产生大量 I/O 操作, 但是仍有以下理由支持执行重布局操作: 无论是磁盘合并操作, 还是磁盘重
布局操作, 都是一种低频、高代价但能获取显著长期收益的操作, 其目的都是为了降低操作的冗余性, 合并操作是
为了降低磁盘中间层在查询操作时的冗余性, 而重布局操作则是为了降低磁盘基本层在合并操作时的冗余性. (1)
在实际生产环境中, 只要磁盘中间层存在数据, 合并操作则可以在查询操作空闲时进行; 同理, 只要磁盘基本层存
在数据, 重布局操作则可以在合并操作与查询操作空闲时进行, 进而可以降低重布局操作本身引发的大量 I/O 操
作对系统性能的影响. (2) 只有磁盘中间层保存的数据量足够大时, 才会触发一次合并操作; 同理, 重布局操作仅在
磁盘基本层的松弛化重叠比例低于阈值时才被触发, 从而能有效控制其频率, 因为较低的重布局操作频率淡化了
其本身引发大量 I/O 对系统性能的影响.
本文引入如下策略来判断是否触发重布局.
(1) 测试物理机当前使用磁盘的随机读速度 V r 与顺序读速度 , 并设置一个重布局阈值系数 λ, 如公式 (6)
V s
所示:

V r
λ = , λ ∈ (0,1] (6)
V s
B s 的比率, 用于近似表示松弛化重叠比
(2) 监控每轮合并操作中删除阶段产生的随机读块数 B r 与顺序读块数
例, 当满足公式 (7) 时, 则触发一次重布局操作:

B r
⩾ λ (7)
B s
4 实验分析

4.1 实验数据
我们在多个公开向量数据集上进行了实验, 包括 SIFT1M、GIST1M 和 DEEP10M. 表 1 展示了每个数据集的
详细信息.
● SIFT1M [53] 是一个经典的图像向量数据集, 用于评估支持大规模近似最近邻搜索 (approximate nearest
neighbor search, ANNS) 算法的性能. 该数据集由图像的 SIFT (尺度不变特征变换) 特征构建, 包含 100 万个 128 维
向量和 1 万个查询向量.