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

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

汰部分节点.
● 插入阶段: 类似于插入操作, 对待插入的新点, 在磁盘层长期数据组件上进行一次 K 近邻查询以获取初始出
边集合, 并将其与反向边一起暂存于 ∆ 结构中, 以便修补阶段应用.
● 修补阶段: 顺序扫描磁盘层长期数据组件所有索引点, 如果是插入点, 将其与 ∆ 结构中存储的出边一起插入
∆ 结构中暂存边的插入导致长度超限, 则根据 Vamana 剪枝策略淘汰部
索引; 如果是已有点, 若其邻接出边集合因
分节点, 维持索引结构紧凑性.
总而言之, FreshDiskANN 通过上述双层索引结构与高效的更新/合并机制, 实现了在支持高吞吐插入的同时,
维持高质量的近似邻居查询性能. 其设计理念对后续系统架构具有重要参考意义.
3 基于 LSM 思想的更新友好磁盘向量索引框架

在实际测试中, 我们观察到 FreshDiskANN 的后台合并操作频率偏高, 频繁抢占搜索线程资源, 进而对前台查
询性能造成负面影响. 为解决该问题, 本文提出了一种基于 LSM 思想的更新友好磁盘向量索引框架, 旨在通过牺
牲部分索引静态搜索性能, 以降低合并频率、提高单次合并数据量, 从而提升整体查询吞吐能力.
该框架受 LSM R 树 [49] 启发, 在 FreshDiskANN 的架构基础上进行了关键改进. 具体而言, 本文引入了一个新
的磁盘中间层, 并配合该层设计了新的操作逻辑. 此外, 为了缓解组件数量增加可能导致的查询冗余和合并操作删
除阶段的 I/O 开销增长, 本文还提出了磁盘组件搜索参数动态调整机制与磁盘索引重布局策略.
3.1 架构设计
与 FreshDiskANN 双层架构不同, 本文提出的框架在内存层与磁盘层之间新增磁盘中间层. 如图 5 所示, 该结
构从高层设计上看虽然较为简单, 但实际实现中涉及更复杂的组件管理逻辑. 从本文的实验结果来看, 这是一个思
想上简单、实现上复杂、效果上有效的架构. 整个系统分为 3 层: 内存层、磁盘中间层、磁盘基本层, 每一层由一
个或多个索引组件组成.

内存层 删除键 删除键 更新操作
集合 集合

只读内存索引 可写内存索引
相 并
同 行
查 磁盘中间层 查
询 删除键 刷新操作 删除键 删除键 询
, 集合 集合 集合 ,
不 结
同 磁盘索引 磁盘索引 磁盘索引 果
参 聚
数 合
磁盘基本层
合并操作
磁盘索引
重布局操作

图 5 基于 LSM 思想的更新友好型磁盘向量索引框架图

3.1.1 架构概述
● 内存层组件: 与 FreshDiskANN 保持一致, 每个组件包含一个 Vamana 图索引和一个删除键集合. 整个内存
层由若干个组件组成, 其中仅允许一个读写组件, 用来处理数据更新, 其他均为只读组件. 为限制内存开销, 通常控
制每个组件的数据规模在较小范围内 (例如: 百万量级数据中限制每个组件不超过 32k 个向量).
● 磁盘中间层组件: 每个组件均由内存层组件转换生成, 结构上包含一个 DiskANN 索引与一个删除键集合.
整个磁盘中间层由若干个组件组成. 在其生命周期内, 这些组件不再接受修改, 属于只读、独立管理的结构单元.