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

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

图 3 ADC 策略示意图

2.3 FreshDiskANN
FreshDiskANN 作为基于图的动态磁盘向量索引中的代表性算法, 因其在查询效率与更新能力之间实现良好
平衡, 成为本文的重要对比对象. 以下对其核心架构与关键机制进行简要介绍.
2.3.1 架构概述
FreshDiskANN 采用内存层与磁盘层共同组成的双层结构, 我们将两层中的基本结构单元统称为组件.
(1) 内存层组件: 分为两类: ① 读写组件, 支持插入、删除与查询操作; ② 只读组件, 仅支持查询操作. 二者结
构相同, 均包含: 一个删除键集合 (记录逻辑删除的向量 ID); 一个基于内存构建的 Vamana 图索引. 系统运行过程
中, 内存层至多存在一个读写组件, 其余均为只读组件.
(2) 磁盘层组件: 单一的长期数据组件, 使用 DiskANN 索引结构, 并作为系统的持久存储层. 通常, 系统初始化
时会加载一批初始向量构建磁盘层索引, 具体过程包括先在内存中构建 Vamana 图, 随后将其序列化为 DiskANN
磁盘格式. 同时, 对所有向量进行量化压缩, 生成压缩码与码表并保存在内存中, 以支持后续的高效距离计算.
2.3.2 核心操作机制
(1) 插入/删除操作: 当插入/删除一个点时, 都是在内存层中的读写组件进行. 新向量插入时, 首先在读写组件
上执行一次近似 KNN 查询, 获取其初始邻接出边. 随后, 将新点与出边一起插入 Vamana 索引中, 并尝试将每条出
边对应的反向边加入目标点的邻接入边集合, 同时根据 Vamana 剪枝策略淘汰部分节点; 删除时, 则采用懒删除策
略, 即不立即从索引中物理删除点, 而是将其主键记录到删除键集合中, 实际查询中再进行后过滤.
(2) 查询操作: 查询向量时, 系统会在内存层与磁盘层的所有组件依次执行相同参数的查询操作. 随后, 将多个
结果集合并, 并根据内存中所有删除键集合过滤逻辑删除的向量, 最终返回过滤后的查询结果.
(3) 合并操作: 当读写组件的数据量超过预设最大阈值的一半时, 系统将其转化为只读组件, 并创建新的读写
组件处理后续数据. 同时, 触发一次将该只读组件合并入磁盘层组件的操作. 如图 4 所示, 整个合并操作分为以下
3 个阶段.

: 全量顺序读 : 全量顺序写
收集删除点邻接 删除点及其邻接 删除邻接入边并
出边 出边 修补

插入邻接入边并 插入点和邻接 分配插入位置
修补 出边

图 4 FreshDiskANN 合并操作示意图

● 删除阶段: 首先, 根据只读组件的删除键集合, 顺序扫描磁盘层长期数据组件索引, 收集所有被删除点的邻
接表, 然后, 再重新顺序扫描磁盘层长期数据组件中的所有索引点. 如果是删除点, 则直接移除; 如果邻接表中包含
删除点, 则将被删除点的出边合并入当前点的邻接表, 若合并后邻接表长度超出阈值, 则根据 Vamana 剪枝策略淘