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

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

分布的随机变量进行采样而生成: 令 u 为一个服从标准均匀分布的随机变量, 即 u~U (0,1), 最大层数 l ma 的计算
x
方式为:

l max = ⌊−lnu·mL⌋ (2)
在公式 (2) 中, ⌊·⌋表示向下取整函数, 参数 mL 是控制层数分布的归一化因子, 通常取 mL = 1/lnM, 其中, M 为
各节点可连接的最大邻居数. 这种概率分配机制确保了绝大多数节点仅存在于底层, 而只有极少数节点能被选入
高层网络. 该多层设计使得搜索可以从顶层稀疏图的高效导航开始, 逐步深入至底层稠密图进行精确查找, 从而将
搜索复杂度由线性级别 O(N) 成功降低至对数级别 O(logN).

level 2

level 1

level 0

图 2 HNSW 索引查询过程

● HNSW 的启发式邻居选择规则. 为了保证图的导航质量, 尤其是在节点分布不均的区域, HNSW 设计了一
种启发式邻居选择规则. 该规则的核心思想在于最大化所选邻居集的空间覆盖多样性, 而不是仅追求距离上的绝
对最近. 如图 3 所示, 其算法流程如下: 在为待插入节点 v 从一个候选邻居集 C 中筛选最终邻居时, 算法首先会判
断 C 的基数|C|. 只有当|C|大于预设的节点最大邻居数时, 才实施启发式剪枝机制, 否则无须剪枝. 此时, 算法将迭
代地构建一个结果集 R. 在每一轮迭代中, 算法从 C 中选取当前距离 v 最近的节点并将其加入 R. 随后, 算法将对
C 中剩余的候选节点应用剪枝规则: 对于 C 中任何一个候选节点 v', 若存在结果集 R 中的已选邻居 v i , 使得其与
′
′
v i 的距离 dist(v ,v i ) 以及其与待插入节点 v 的距离 dist(v ,v) 满足:

′
′
dist(v ,v i ) > dist(v ,v) (3)
在公式 (3) 中, 当公式不成立时, v'被视为一个冗余的候选邻居, 算法将其从 C 中移除. 此过程反复进行, 直至
结果集 R 的大小达到最大邻居数上限且满足提前终止条件.

v
连接长边
v 1
避免形成孤岛
v′
v 2
候选节点
(a) ෬ႄ֥ܛི֛ႋ (b) ఓؿൔࡧᆥܿᄵ
图 3 保证图索引质量的关键

此规则在选择邻居时考虑区域覆盖 (不同邻居有一定的方向和范围辐射), 避免在局部区域出现大量冗余连
接, 从而保证图高效与高质量的探索能力. 然而, 也正是因为这一规则, 在面临批量插入相似数据场景时, 可能会因