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

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

并操作插入阶段需要对所有磁盘中间层索引组件进行 1 趟顺序读操作, 但凭借优化的删除阶段算法与磁盘重布局
机制 (详见后文第 3.3 节), 在对磁盘基本层索引组件进行合并操作时只需要 2 趟顺序读操作、少量随机读操作和
2 趟顺序写操作, 却能达到与 FreshDiskANN 合并操作相近的合并 I/O 操作代价. 此外, 上述合并操作的 3 个阶段
的算法能很容易地扩展为批处理模式, 即每次处理一批节点, 进一步降低 I/O 开销并提升运行效率.
3.1.7 合并策略
本文设计了两种典型的合并触发策略: (1) 写半合并策略: 当插入线程导致磁盘中间层组件数量超过其上限的
一半时, 触发向磁盘基本层的合并操作; (2) 定期合并策略: 维护一个后台合并检测线程, 定期检查中间层组件数
量, 并在超出阈值后启动合并操作.
3.2 磁盘组件搜索参数动态确定机制设计
(1) 层间动态搜索参数策略
如图 8(a) 所示, 在单个磁盘层组件中, 影响查询延迟的关键因素是搜索列表长度 L s 而非组件数据量大小, 并
L s 呈线性增长趋势. 因此, 降低查询延迟最直接且有效的方式即为缩小搜索列表长度 . 同时, 如图
且该延迟随 L s
8(b) 所示, 查询召回率随搜索列表长度 L s 的增加呈现对数增长, 且在不同规模数据集上具有一致趋势. 因此, 上述
两种指标之间的增长趋势差异, 为实现二者的平衡提供了优化空间.

8 100.0
7 97.5

6 95.0
Latency (ms) 5 4 Recall@5 92.5

90.0
87.5
3
SIFT100k SIFT100k
2 SIFT1M 85.0 SIFT1M
SIFT500k SIFT500k
5 15 25 35 45 55 65 75 5 15 25 35 45 55 65 75
Search list size Search list size
(a) Query mean latency (b) Query accuracy
图 8 搜索列表长度影响趋势图

基于“越靠近下层, 磁盘组件的数据量越大”这一客观规律, 结合“数据量越大的组件更可能包含最终结果”的
启发式思想, 本文设计了一种分层搜索参数策略: 对磁盘中间层和磁盘基本层的组件设定不同的搜索参数
[ ]
, 其中满足 .
L s 0 ,L s 1 L s 0 <L s 1
(2) 层内动态搜索参数策略
在 DiskANN 中, 每个磁盘层组件在构建时都要经历如第 2.2 节所言的量化压缩. 由于量化压缩基于聚类方法, 使
用聚类中心对整个向量集合进行离散化处理, 因此这些聚类中心本质上反映了组件的局部数据分布特征.
基于这个观察, 受 KRT 导航算法 [52] 的启发, 本文将磁盘中间层组件 I 量化压缩中的聚类中心集合视为其特征
I
点集合 C, 定义向量 x q 与磁盘中间层组件 的组件距离为向量 x q 到该组件特征点集合 C 中的最小值:

( ) ( ) ( )
Dist x q ,I = Dist x q ,C = minDist x q ,c (2)
c∈C
进一步借鉴 SPANN [11] 中的动态决定搜索列表数策略, 在磁盘中间层组件的搜索中, 本文定义了向量 x q 在给
I
定的 n 个磁盘层组件 中的搜索距离阈值公式, 用于判定组件是否值得深入查询, 其中 η 是动态搜索阈值系数:

( )
D th = minDist x q ,I i ×η, η ∈ (0,1] (3)
i∈[0,n)