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

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

引总布局的平均 ROR 从 67.6% 提升至 83.2%. 这一结果表明, 即使在合并操作的删除阶段需要大量删除磁盘索引
点, 在优化后的布局下, 最坏情况下也仅会触发不超过 16.8% 的随机读操作, 从而有效降低了 I/O 操作成本.

RAW IDRR GAR NFR
100 100 100 100
80 80 80 80
ROR (%) 60 ROR (%) 60 ROR (%) 60 ROR (%) 60
40
40
40
40
20 20 20 20
0 0 0 0
0 1 2 0 1 2 0 1 2 0 1 2
Partition number Partition number Partition number Partition number
(a) Average ROR (b) ROR P10 latency (c) ROR P50 latency (d) ROR P99 latency
图 17 不同最小单元在不同算法下 ROR 提升效果

此外, 本文还对是否启用磁盘索引重布局算法进行了消融实验分析, 并统计了每轮合并操作中删除阶段的磁
盘 I/O 操作时间, 实验结果如图 18 所示.

LSMDiskANN LSMDiskANN without relayout
3.0 15.0 25
2.5 12.5 20
I/O time (s) 2.0 I/O time (s) 10.0 I/O time (s) 15
7.5
1.5
10
5.0
1.0
0.5 2.5 5
0 0 0
0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 5
Merge iteration Merge iteration Merge iteration
(a) Delete phase I/O time (SIFT1M) (b) Delete phase I/O time (GIST1M) (c) Delete phase I/O time (DEEP10M)
图 18 磁盘索引重布局算法消融实验

如图 18 所示, 在采用重布局算法并结合本文提出的删除流程后, 在 3 个数据集上, 整个删除阶段的磁盘 I/O 时
间分别平均下降了 40.06%、42.76%、41.26%, 进一步验证了所提出磁盘索引重布局算法在降低系统开销方面的
有效性.
5 总 结

基于 LSM 的次级索引广泛应用于 NoSQL 数据库, 在高吞吐量场景下有效地解决了索引表的同步更新与高
并发查询问题, 展现出极强的实用价值. 受此启发, 本文提出了一种基于 LSM 思想的更新友好型磁盘向量索引框
架. 针对现有领先算法 FreshDiskANN 在查询-更新混合场景中存在的查询吞吐量瓶颈与极端查询延迟过高等问
题, 本文借鉴 LSM 的分层思想并结合 FreshDiskANN 的系统架构, 设计并引入了磁盘中间层, 以缓解访问瓶颈. 同
时, 本文进一步提出了磁盘组件搜索参数动态确定机制与面向合并操作删除阶段的磁盘索引重布局算法, 在降低
查询延迟与减少合并操作删除阶段 I/O 开销方面取得了显著效果. 通过在多个经典大规模高维向量数据集上进行
的索引快速膨胀场景与索引稳定更新场景下的对比实验与消融分析可知, 本文所提出的方法在查询吞吐量以及极
端查询延迟方面均有显著改善, 验证了该框架的有效性与实用性.

References
[1] Asai A, Min S, Zhong ZX, Chen DQ. Retrieval-based language models and applications. In: Proc. of the 61st Annual Meeting of the
Association for Computational Linguistics, Vol. 6 (Tutorial Abstracts). Toronto: ACL, 2023. 41–46. [doi: 10.18653/v1/2023.acl-tutorials.6]
[2] Li S, Lv FY, Jin TW, Lin GL, Yang KP, Zeng XY, Wu XM, Ma QL. Embedding-based product retrieval in taobao search. In: Proc. of the
27th ACM SIGKDD Conf. on Knowledge Discovery & Data Mining. Singapore: ACM, 2021. 3181–3189. [doi: 10.1145/3447548.