分层可导航小世界图HNSW简介

本文是博主在 NIS3351 数据库原理及安全课程上的分享，主题是 LLM 时代的向量数据库。博主负责其中向量数据库索引算法——HNSW 部分的讲解，并基于课程准备的讲义整理学习笔记，发布于此存档，也供大家参考交流。

两个基础

Probability Skip List（概率跳表）

• 改进版的链表数据结构，用于提高查找效率

• 结构特点：它通过引入多个层级来加速查找过程。最顶层的索引连接跨度更大的节点，可以快速跳跃，减少搜索路径长度；随着层级下降，索引的跨度逐渐变短，提供更精确的访问路径；最底层是完整的原始链表，包含所有元素。
• 插入和查找过程：插入过程是概率性的，先确定该元素首次出现在哪一层，每一层的元素出现在更高层的概率是固定的。查找时从最上层开始，每次选择下一个节点，直到遇到比目标值大的节点，然后回退到上一个节点，并进入下一层继续搜索，直到到达最底层找到目标元素。这种设计可以将查找时间复杂度从普通链表的 \(O(n)\) 降低到 \(O(\log n)\)，代价是增加了一些存储开销。

Navigable Small World Graphs（可导航小世界图）

• 用于构建高效搜索结构的图模型，常用于快速近似最近邻搜索任务。

• 结构特点：这种图结合了小世界图的短路径和高聚集性特性，图中节点之间通常有较高的连接度，邻居节点之间往往彼此相连，形成聚集或团簇，同时任意两个节点之间的平均路径长度较短。此外，图中还包含长距离连接，这些连接对于维持小世界特性至关重要，能使在大规模数据中可以快速查找与查询点接近的节点。
• 搜索过程：可导航小世界图通常通过启发式搜索算法进行搜索，从一个初始节点开始，根据距离向与目标节点最近的节点跳转，从而逐渐逼近目标。这种搜索方式效率较高，避免了穷举搜索的时间开销。
• 贪婪
• 痛点：传统近邻图（如 k-NN 图、NSW）是 “单层结构”，搜索时需从某个起点开始，通过 “贪心遍历”找目标。但数据量增大时，遍历步数会呈 “多项式对数级” 增长，尤其在低维或聚类数据中，容易陷入 “局部最小值”（比如在聚类边界停住，找不到其他聚类的近邻）。

Hierarchical Navigable Small World（分层可导航小世界图）

• 顾名思义：HNSW 是在 NSW 基础上引入了分层结构的改进版本。是概率跳表和可导航小世界图的结合。

• 可类比地图导航：从 “全国地图”（顶层）先定位到 “省地图”（中层），再缩小到 “市地图”（底层），每层只关注对应尺度的 “关键路线”（长链接 / 短链接），最终快速找到目标。
• 核心思想：用 “指数衰减概率” 构建 “多层近邻图”，从顶层 “粗定位” 到低层 “精搜索”，通过 “启发式邻居选择” 保证全局连通性，最终用 “对数级复杂度” 实现高效的近似近邻搜索。

核心组件

分层图结构：“多层近邻图” 如何定义？

• HNSW 的整体结构是多层近邻图的集合，每层对应一个 “数据子集” 和 “链接尺度”：
• 层数编号：从 “顶层”（比如 \(L\) 层）到 “底层”（\(0\) 层），底层包含所有数据元素，越往上的数据越少（与概率跳表类似）。
• 元素的 “层数分配”：每个元素会被随机分配一个 “最大层数”（比如元素 A 的最大层数是 3，意味着它会出现在 0-3 层，不会出现在 4 层及以上）。
  • 分配规则是 “指数衰减概率”：层数越高，元素出现的概率越低
• 层内链接：每层内的元素通过 “近邻链接” 连接，但链接的 “特征距离” 不同：
  • 顶层链接是 “长距离链接”（连接不同聚类的关键节点）
  • 底层链接是 “短距离链接”（连接同一聚类内的近邻）

搜索入口点（Enter Point）：从哪里开始搜索？

• 初始入口点：首次构建图时，第一个插入的元素就是顶层入口点；后续若插入 “最大层数更高” 的元素（比如现有顶层是 3 层，插入一个最大层数为 4 的元素），则更新入口点为这个新元素。
• 作用：搜索时必须从 “顶层入口点” 开始 —— 因为顶层的长链接能快速 “跨越” 大范围数据，避免从底层开始的 “盲目遍历”。

邻居选择规则：如何避免 “局部最小值”？

• 传统近邻图只选 “离自己最近的 \(k\) 个邻居”，容易导致 “聚类隔离”（比如两个聚类的元素间没有链接，搜索时无法跨聚类）。HNSW 用两种邻居选择方式，核心是启发式规则：
  • 简单规则（Algorithm 3）：直接选离插入元素最近的 \(M\) 个候选者（\(M\) 是每层最大连接数），适合数据分布均匀的场景。
  • 启发式规则（Algorithm 4）：不仅看 “候选者与插入元素的距离”，还看 “候选者与已选邻居的距离”—— 只有当候选者比 “已选邻居” 更接近插入元素时，才将其选为邻居。这种规则能强制建立 “跨聚类链接”，比如在两个孤立聚类的边界插入元素时，会主动连接另一个聚类的元素，保证全局连通性。
  

核心流程

图构建（插入元素）：如何把元素 “放进” 分层图？

构建流程的目标是 “增量插入元素，同时维护分层图结构”

• 输入：空的 HNSW 图、新元素 \(q\)、参数（\(M\)、\(M_{max}\)、\(efConstruction\) 等）
• 输出：更新后的 HNSW 图

1. 步骤 1：对新插入的元素 \(q\)，按 “指数衰减概率” 随机生成它的最大层数 \(l\) —— 决定它会出现在 \(0\) 到 \(l\) 层。
2. 步骤 2：从顶层开始，“向下搜索” 候选邻居
   • 搜索的目的是 “在每层找到 \(q\) 的近邻”，分两个阶段：
   • 阶段 A：上层搜索（从顶层 \(L\) 到 \(l+1\) 层）—— 用 “小候选列表” 快速定位
     • 从入口点 \(ep\) 开始，用与 NSW 类似的方法遍历找到离 \(q\) 最近的元素。每层搜索后，将 \(W\) 中离 \(q\) 最近的元素作为 “下一层的入口点 \(ep\)”，继续向下搜索。
     • 作用：此阶段近邻列表 \(W\) 的规模为1，快速缩小范围
   • 阶段 B：下层搜索（从 \(\min(L,l)\) 层到 \(0\) 层）—— 用 “大候选列表” 保证召回率
     • 当层数≤元素 \(q\) 的最大层数 \(l\) 时，扩大 \(W\) 的规模，找更多候选邻居。
     • 原因：下层需要更精准的近邻，避免后续邻居选择遗漏关键节点，保证构建质量。
3. 步骤 3：选择邻居并建立 “双向链接”
   • 对每个下层（\(0\) 到 \(l\) 层），从步骤 2 找到的候选邻居中选 \(M\) 个（\(M\) 是每层最大连接数），用两种方式选择：
     • 若用 “简单规则”（Algorithm 3）：直接选 \(W\) 中离 \(q\) 最近的 \(M\) 个元素。
     • 若用 “启发式规则”（Algorithm 4）：遍历 \(W\) 中的候选者，依次判断 “候选者是否比已选邻居更接近 \(q\)”，满足则加入邻居列表，直到选满 \(M\) 个。
   • 建立链接：对选中的每个邻居，在当前层建立 \(q\) 与邻居的双向链接。
4. 步骤 4：处理 “连接数超限”—— 缩减链接
   • 若某个元素（包括 \(q\) 和它的邻居）在当前层的连接数超过 “最大限制 \(M\)”，则用邻居选择规则缩减链接，只保留 \(M\) 个 “最优邻居”。
5. 步骤 5：更新 “入口点”（若需要）
   • 若新元素 \(q\) 的最大层数 \(l\) 超过当前顶层 \(L\)，则更新入口点为 \(q\)，并将图的顶层数更新为 \(l\)。

图搜索（查询近邻）：如何高效找到某个元素的 K 近邻？

搜索流程的目标是 “给定查询元素 \(q\)，返回离 \(q\) 最近的 \(K\) 个元素”，对应论文的 Algorithm 5，逻辑与 “构建阶段的下层搜索” 类似，但更简洁：

1. 步骤 1：从顶层入口点开始 “向下粗定位”
   • 从入口点 \(ep\) 开始遍历：对每层进行遍历，然后将 \(W\) 中最近的元素作为下一层的 \(ep\)，直到进入底层（\(0\) 层）。
   • 作用：快速缩小搜索范围，避免在底层遍历过多节点。
2. 步骤 2：在底层 “精细搜索” 候选近邻
   • 进入底层后，扩大 \(W\) 的规模，找更多候选近邻。
   • 遍历逻辑与构建阶段一致
3. 步骤 3：返回 \(K\) 个最优近邻
   • 从底层的 \(W\) 列表中，筛选出离 \(q\) 最近的 \(K\) 个元素，作为最终的 “近似最近邻” 结果。

关键参数

• 控制元素的层数分配，影响层间链接重叠度
• 每层的最大连接数 \(M\)
• 底层的最大连接数（底层数据多，需更多链接）\(M_{max}\)
• 构建阶段的候选列表规模 \(efConstruction\)
• 搜索阶段的候选列表规模 \(efSearch\)

优缺点总结

• 优点：
  • 效率高：搜索复杂度是 “对数级”（\(O(\log N)\)），比 NSW 的 “多项式对数级” 快，在 10 亿级数据上仍能实现 “毫秒级查询”（比如 200M SIFT 数据上，查询时间比 Faiss（PQ 算法）快数倍）。
  • 鲁棒性强：在低维、高维、聚类数据上均表现最优 —— 传统算法（如 LSH、k-d 树）在高维数据中会 “维度灾难”，NSW 在低维数据中性能差，而 HNSW 通过分层和启发式邻居选择，能适应所有场景。
  • 易扩展：支持 “增量插入”（随时加新数据，无需重建图），且可借鉴 “跳表的分布式技术” 实现分布式搜索。
• 缺点：
  • 内存开销大：HNSW 需要存储多层图结构和大量链接，内存消耗较高，尤其在大规模数据集上。
  • 构建时间较长：相比其他近邻搜索算法，HNSW 的图构建过程较复杂，难以并行化，时间开销较大。
  • 参数调优复杂：HNSW 有多个关键参数（如 \(M\)、\(M_{max}\)、\(efConstruction\)、\(efSearch\) 等），需要根据具体数据集进行调优，增加了使用难度。

分享报告

参考资料

1. MALKOV Y A, YASHUNIN D A. Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs[J]. IEEE Transactions on Pat- tern Analysis and Machine Intelligence, 2018, 42(4): 824-836.