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

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

点, 其中直接影响搜索延迟的是搜索列表长度 L s 而不是组件数据量, L s 表示当前组件查询返回的结果集合长度,
K
为了保证高召回率, L s 的设置通常远大于查询指定的 , 从而导致冗余查询现象严重. 以 FreshDiskANN 中的默认
值 L s = 75, K = 5 为例, 假如现有 1 个内存层组件和 1 个磁盘层组件, 则会查询得到长度为 150 的结果集合, 并进
行重排序得到前 5 条结果. 如果本文照搬这个策略, 冗余查询带来的查询延迟将不可估量. 如第 3.1.1 节所言, 不同
层组件的数据量大小差异很大. 因此, 直观地想, 数据量越大的组件包含最终 5 条结果的概率越大, 反之越小. 基于
这种启发式思想, 本文在磁盘中间层组件与磁盘基本层组件采用不同的搜索参数. 假如内存层和磁盘基本层遵循
FreshDiskANN 的设置, 磁盘中间层设有 5 个组件且查询参数 L s = 15, 那么其结果集长度则为 15×5+150=225, 因
此即使是串行搜索, 其搜索时间也仅比 FreshDiskANN 高出 50%, 从而大大减少冗余查询.
L s ⩾ K, 就存在获得 100% 召回率的可能. 基于此, 本文进一步
(3) 层内动态搜索参数策略: 从理论上讲, 只要
提出了一种动态确定搜索列表长度的机制 (详见后文第 3.2 节), 可根据组件数量与查询特征自动调整 L s , 最大程
度地减少冗余计算, 提高查询效率.
3.1.4 刷新操作
在引入磁盘中间层后, 系统需设计刷新机制以实现内存层组件向磁盘中间层组件的转换. 当内存层组件的数
据量超过设定阈值时, 系统将触发一次刷新操作, 将其转化为磁盘中间层组件. 图 6 展示了 Vamana 索引在内存与
磁盘中的两种数据布局形式的差异: (1) 内存形式下向量数据与邻接表分离存储, 而在磁盘形式中, 向量数据与对
应邻接表紧邻存储; (2) 磁盘形式引入了量化压缩机制, 压缩码与码表需驻留于内存中. 因此, 刷新操作主要包括两
项任务: (1) 依据磁盘索引的数据布局, 将内存中的向量与邻接表数据持久化至磁盘; (2) 生成量化压缩码和码表文
件并写入磁盘.

内存层
内存组件
向量数据 邻接表数据
向量 1 邻接表 1
向量 2 邻接表 2
刷 向量 3 邻接表 3
新 量化
操 压缩
作 刷新
磁
盘 压缩码 向量 1 邻接表 1
中 向量 2 邻接表 2
间 码表文件 向量 3 邻接表 3
层 磁盘索引数据
磁盘索引

图 6 刷新操作示意图

3.1.5 合并操作
在 3 层索引架构中, 合并操作由原来的“内存层向磁盘层合并”演化为“磁盘中间层向磁盘基本层合并”. 当磁
盘中间层组件数量达到设定阈值时, 将触发一次合并操作. 与 FreshDiskANN 相比, 本文所提框架的合并操作在以
下 3 方面有所不同: (1) 借助重布局算法 (详见后文第 3.3 节), 删除阶段仅需对磁盘基本层组件进行一趟顺序读操
作; (2) 插入阶段的向量来源于磁盘中间层索引, 而非常驻内存, 因此需要从磁盘读取向量数据; (3) 插入点数量显
著增多, 为降低内存占用, 不再使用 ∆ 结构暂存所有邻接出边.
针对上述挑战, 本文重新设计了合并操作中的删除、插入和修补阶段过程.
(1) 删除阶段. 此阶段负责从磁盘基本层中物理删除被标记删除的点并进行必要修补, 删除流程如算法 2 所
示: 首先, 每次从磁盘基本层迭代器获取一个点 (第 2–4 行), 如果该点 ID loc q 已被标记删除则对该点 x q 进行实际

删除并将其邻居列表 N q 暂存至 ∆ 结构中 (第 5–7 行); 如果该点未被删除, 则遍历其邻居点 n, 若发现被删除邻居,
则将其邻接列表 N n 合并至当前邻接列表 N q 中, 并根据 Vamana 剪枝策略淘汰部分节点 (第 8–13 行). 在这个过程