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

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

化: (1) Starling 在磁盘布局算法中的最小单元是块 (block), 而本文的合并操作中, 每次是从磁盘索引顺序读取一批
块, 所以本算法的最小单元是缓冲区 (buffer); (2) Starling 中的优化目标是点 P 1 与邻居 P 2 需要位于同一个最小单
元上, 而因为合并操作中顺序读取带来的先后顺序, 所以本算法的优化目标可以放松为 P 2 存在于与 P 1 相同或者
之前的最小单元上.

2 P 2 3
1 P 1 P 1 4
P 1 P 1
邻 邻 邻 邻 邻 邻 邻 邻 邻 邻
接 接 接 接 接 接 接 接 接 接
表 表 表 表 表 重布局操作 表 表 表 表 表
向 向 向 向 向 向 向 向 向 向
量 量 量 量 量 量 量 量 量 量
① ② ③ ④ ⑤ ① ② ③ ④ ⑤
扫描顺序 扫描顺序
(a) 重布局操作前 (b) 重布局操作后
图 9 重布局操作示意图

为了量化这一目标, 本文给出如下定义.
定义 5 (磁盘索引布局). 给定一个磁盘索引 I, 其向量索引数据在磁盘上的排列顺序称为磁盘索引布局.
定义 6 (松弛化重叠比例). 点 p 的松弛化重叠比例为其入边邻居在当前及后续缓冲区中出现的比例, 假设整个
磁盘索引数据在一次全量顺序扫描中分为 0 至 n–1 共 n 段缓冲区进行读取, 给定一个点 , p 在
p BufIdx(p) 表示点
第几个缓冲区, Buf (i) 表示第 i 个缓冲区中的点集合, IN (p) 表示点 p 的入边邻居集合, 从而有如下计算公式衡量
p 的松弛化重叠比例 (relaxed overlap ratio, ROR):
点

n−1
∑
|Buf (i)∩IN (p)|
i=BufIdx(p)
ROR(p) = (4)
|IN (p)|
定义 ROR(P), 其中:
7 (磁盘索引重布局). 给定一种磁盘索引布局 P, 磁盘索引重布局的目标则是最大化
∑
ROR(p)
p∈P
ROR(P) = (5)
|P|
基于上述目标, 本文设计了 3 种磁盘索引重布局算法: 第 1 种是最直接的基于入度的重排序算法, 第 2 种是基
于贪心的朴素算法, 第 3 种是基于邻居频率启发式的收敛优化算法.
(1) 分配算法 A: 基于入度的排序分配算法
因为每个点的出度是一致且预先设定的值, 而入度则因为剪枝规则的存在而大相径庭. 将入度大的点排列在
前面从直观上更容易提高其入边邻居出现在之后缓冲区的概率, 从而提升松弛化重叠比例. 因此, 不妨考虑按照每
个点的邻接入边数 (即入度) 进行降序排序, 并按照该顺序进行索引重布局.
(2) 分配算法 B: 基于贪心的朴素分配算法
在分配算法 A 的布局基础上, 本文进一步提出基于贪心的朴素分配算法, 期望在尽量不破坏分配算法 A 的先
后顺序基础上, 进一步加强松弛化条件. 具体流程如算法 6 所示: 按照分配算法 A 中的排序顺序访问所有点, 当访
问点 p 2 时, 该算法将 p 2 尽可能地分配到原本的分区 (第 5–8 行), 并将其入边邻居 p 1 贪心地分配到原本的分区和
p 2 的分区中的下标较大值分区 (第 9–14 行).

算法 6. 基于贪心的朴素分配算法.
输入: 图G = (V,IN (V));
输出: 新磁盘索引布局P.