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

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

留了一份索引执行所需的完整上下文结构, 比如重复的元数据和查询所需的内存上下文. 进而导致在多磁盘索引
组件的情况下, 内存占用随着磁盘组件数的上升呈现线性增长趋势. 若能实现组件间共享资源机制, 比如统一元数
据管理和线程池管理, 则可大幅降低内存开销. 这类共享资源的方案属于工程实现的范畴, 因此本文并未在此方面
做进一步测试.
4.4.2 磁盘组件搜索参数动态确定机制消融实验
为了评估磁盘组件搜索参数动态确定机制的有效性, 本文在 SIFT1M 索引快速膨胀实验设置下, 对层间动态
搜索参数策略 (以下简称策略 1 (Policy 1)) 与层内动态搜索参数策略 (以下简称策略 2 (Policy 2)) 进行了消融实验
分析, 实验选取其中策略 2 生效的查询记录并按迭代轮次取均值从而得到实验结果, 如图 16 所示.

LSMDiskANN LSMDiskANN without Policy 1 and Policy 2 LSMDiskANN without Policy 2
32.5
400 99.6 30.0

350 99.4 27.5
QPS Recall@5 Latency (ms) 25.0
300 99.2 22.5
99.0
250 20.0
98.8 17.5
0 2 4 6 8 10 0 2 4 6 8 10 0 2 4 6 8 10
Iterations Iterations Iterations
(a) Query throughput (b) Query accuracy (c) Query P90 latency
35.0 40
225
32.5 35 200
Latency (ms) 27.5 Latency (ms) 30 Latency (ms) 175
30.0
150
25.0
125
22.5
25 100
20.0 75
0 2 4 6 8 10 0 2 4 6 8 10 0 2 4 6 8 10
Iterations Iterations Iterations
(d) Query P95 latency (e) Query P99 latency (f) Query P99.9 latency
图 16 磁盘组件搜索参数动态确定机制消融实验

从实验结果可以看出, 相较于完全不使用动态搜索参数, LSMDiskANN 在查询 QPS 上平均提升了 65.86%, 在
查询延迟 P90、P95、P99、P99.9 上分别平均下降了 36.7%、35.89%、31.01% 和 27.74%. 进一步比较策略 1 与联
合使用策略 1 和策略 2 的效果可发现, 后者在查询 QPS 上平均提升了 1.35%, 而在极端查询延迟上几乎持平. 这
是由于策略 1 中查询列表长度的默认值为 15, 而策略 2 将其下调至 5, 下降幅度相对较小, 因此带来的性能优化也
较有限.
综上所述, 磁盘组件搜索参数动态确定机制在提升查询吞吐量及降低高分位延迟方面均表现出良好的实用性
与有效性.
4.4.3 磁盘索引重布局算法消融实验
为了评估磁盘索引重布局算法的有效性, 本文在 SIFT1M 索引稳定更新实验设置下, 比较了基于入度的排序
分配 (in degree rank relayout, IDRR) 算法、基于贪心的朴素分配 (greedy allocation relayout, GAR) 算法和基于邻居
频率启发式的收敛分配 (neighbor frequency relayout, NFR) 算法这 3 种磁盘重布局算法对松弛化重叠比例 (ROR)
的提升效果, 其中 RAW 表示未经任何重布局优化的初始索引布局, 实验效果如图 17 所示.
图 17 展示了具有先后顺序, 编号为 0–2 的最小单元在经过 3 种算法处理后的 ROR 提升效果. 由于所有数据
点都在最小单元 0 及其之后, 因此最小单元 0 的 ROR 恒为 100%. 可以看出: (1) 在最小单元 1 中, 各分位点层级的 ROR
显著提升, 平均提升幅度为 42.81%; (2) 在最小单元 2 中, 平均 ROR 提升更为明显, 达 163.15%; (3) 从全局来看, 索