算法概览：HNSW

为满足高效向量搜索的需求，HNSW（分层可导航小世界）算法出现，它是一种广泛采用且高效的基于图的近似最近邻（ANN）搜索算法。该算法在搜索速度和召回率（准确性）之间实现了良好平衡，使其适合许多语义搜索应用。

HNSW的核心思想结合了跳表和可导航小图的原理。让我们分解其构成：

多层图结构

想象一个类似多层高速公路系统的结构。HNSW构建的图中，数据点（向量）是节点。连接（边）表示向量空间中的接近度。然而，HNSW创建的是多层结构，而不是一个单一的平面图。

• 第0层（基础层）： 这一基础层包含所有数据点。这里的连接距离相对较短，连接的是近邻。仅在此层进行导航对于远距离查询可能仍然较慢。
• 更高层（快速通道）： 上方每个后续层都包含其下方层节点的一个子集。这些更高层就像高速公路，具有更远距离的连接，以便在向量空间中快速通过。节点出现在更高层的概率呈指数下降，使得顶层非常稀疏。

HNSW多层图结构的一个简化示意图。更高层提供稀疏、远距离的连接，以便更快速地通过，而基础层包含所有点，用于细粒度搜索。

构建索引（构造）

将新向量插入HNSW图涉及以下步骤：

1. 层分配： 确定新节点将位于的最高层。这通常是概率性完成的，停留在较低层的机会更大。
2. 顶层入口： 使用指定入口点，在图的最高层开始搜索邻居。
3. 贪婪搜索与插入（逐层）：
   • 在当前层中，在现有节点中找到新向量的近似最近邻。此搜索使用动态候选列表（由$efConstruction$参数控制）。
   • 将新节点连接到本层中找到的最近邻居（最多达到限制$M$）。为保持图的质量并限制每个节点的连接数（由$M_{max}$控制），可能会修剪现有连接。
   • 将本层中找到的最接近的节点作为下一层搜索的入口点。
   • 重复此过程，逐层向下，直到到达第0层。随着层级下降，搜索变得越来越精细。

参数$M$（每层每个节点的最大连接数）和$efConstruction$（索引构造期间动态候选列表的大小）在此阶段很重要。更高的值通常会生成更高质量的图（可能提高搜索准确性），但会增加索引构建时间和内存占用。

搜索邻居（查询）

当查询向量到达时，搜索过程与插入逻辑相似，但不将查询向量添加到图中：

1. 顶层入口： 从图的顶层中指定的入口点开始。
2. 贪婪搜索（逐层）：
   • 在当前层中，在当前最佳候选节点的邻居中找到最接近查询向量的节点。此搜索维护一个动态候选列表（由$efSearch$参数控制）。
   • 进行贪婪导航：从当前节点移动到更接近查询向量的邻居。重复此操作，直到在本层中找不到更近的邻居（一个局部最小值）。
   • 本层中找到的最接近的节点成为下一层搜索的入口点。
   • 重复此过程，逐层下降，直到在第0层执行搜索。
3. 结果收集： 在第0层进行的搜索会生成最终的近似最近邻集。返回的邻居数量通常由用户指定（例如，top-k）。

$efSearch$参数在此处很重要。它控制每层搜索期间所考察的候选列表的大小。较大的$efSearch$允许更详尽的搜索，增加找到真实最近邻（更高召回率）的概率，但代价是增加搜索延迟。它必须至少与所需邻居数量（k）一样大。

HNSW的权衡

HNSW提供可调整参数，让您管理以下各项之间的权衡：

• 搜索速度（延迟）： 返回结果的速度。主要受$efSearch$和图结构（$M$）影响。较低的$efSearch$更快。
• 召回率（准确性）： 找到真实最近邻的比例。主要受$efSearch$、$efConstruction$和$M$影响。更高的值通常会提高召回率。
• 索引构建时间： 插入所有向量所需的时间。受$efConstruction$和$M$影响。更高的值需要更长时间。
• 内存占用： 内存中索引图的大小。受$M$（更多连接 = 更多内存）和节点总数影响。

与IVF（倒排文件索引）等方法相比，HNSW在给定搜索速度下通常能获得更高的召回率，尤其是在高维空间中，尽管其索引构造可能计算量更大，并且通常占用更多内存。其优势体现在通过分层结构实现高效的图通过。

了解这些机制，可以帮助您在向量数据库中构建HNSW索引时选择适当的参数，平衡性能要求与您的特定应用所需的准确性水平。