为满足高效向量搜索的需求,HNSW(分层可导航小世界)算法出现,它是一种广泛采用且高效的基于图的近似最近邻(ANN)搜索算法。该算法在搜索速度和召回率(准确性)之间实现了良好平衡,使其适合许多语义搜索应用。HNSW的核心思想结合了跳表和可导航小图的原理。让我们分解其构成:多层图结构想象一个类似多层高速公路系统的结构。HNSW构建的图中,数据点(向量)是节点。连接(边)表示向量空间中的接近度。然而,HNSW创建的是多层结构,而不是一个单一的平面图。第0层(基础层): 这一基础层包含所有数据点。这里的连接距离相对较短,连接的是近邻。仅在此层进行导航对于远距离查询可能仍然较慢。更高层(快速通道): 上方每个后续层都包含其下方层节点的一个子集。这些更高层就像高速公路,具有更远距离的连接,以便在向量空间中快速通过。节点出现在更高层的概率呈指数下降,使得顶层非常稀疏。digraph HNSW_Layers { rankdir=BT; // 从下到上排列 splines=true; overlap=false; node [shape=circle, style=filled, width=0.3, height=0.3, label="", fixedsize=true]; subgraph cluster_2 { label = "第2层(顶层)"; bgcolor="#e9ecef"; node [fillcolor="#7048e8"]; // 紫色 L2_A; L2_E; L2_A -> L2_E [color="#495057"]; } subgraph cluster_1 { label = "第1层"; bgcolor="#e9ecef"; node [fillcolor="#1c7ed6"]; // 蓝色 L1_A; L1_B; L1_C; L1_D; L1_E; L1_A -> L1_B [color="#495057"]; L1_A -> L1_C [color="#495057"]; L1_B -> L1_D [color="#495057"]; L1_C -> L1_D [color="#495057"]; L1_D -> L1_E [color="#495057"]; L1_C -> L1_E [color="#495057"]; } subgraph cluster_0 { label = "第0层(基础层)"; bgcolor="#e9ecef"; node [fillcolor="#1098ad"]; // 青色 L0_A; L0_B; L0_C; L0_D; L0_E; L0_F; L0_G; L0_H; L0_I; L0_J; L0_A -> L0_B; L0_B -> L0_C; L0_C -> L0_D; L0_D -> L0_E; L0_E -> L0_F; L0_F -> L0_G; L0_G -> L0_H; L0_H -> L0_I; L0_I -> L0_J; L0_A -> L0_C; L0_A -> L0_D; L0_B -> L0_D; L0_C -> L0_E; L0_D -> L0_F; L0_E -> L0_G; L0_F -> L0_H; L0_G -> L0_I; L0_H -> L0_J; L0_A -> L0_F; L0_C -> L0_H; L0_E -> L0_J; edge [color="#adb5bd"]; // 基础层的灰色边 } // 层间连接 edge [style=dashed, color="#fa5252", constraint=false]; // 红色虚线 L2_A -> L1_A; L2_E -> L1_E; L1_A -> L0_A; L1_B -> L0_B; L1_C -> L0_C; L1_D -> L0_D; L1_E -> L0_E; // 如果需要,添加不可见的边以进行排名(根据布局调整) L2_A -> L1_A [style=invis]; L1_A -> L0_A [style=invis]; L2_E -> L1_E [style=invis]; L1_E -> L0_E [style=invis]; }HNSW多层图结构的一个简化示意图。更高层提供稀疏、远距离的连接,以便更快速地通过,而基础层包含所有点,用于细粒度搜索。构建索引(构造)将新向量插入HNSW图涉及以下步骤:层分配: 确定新节点将位于的最高层。这通常是概率性完成的,停留在较低层的机会更大。顶层入口: 使用指定入口点,在图的最高层开始搜索邻居。贪婪搜索与插入(逐层):在当前层中,在现有节点中找到新向量的近似最近邻。此搜索使用动态候选列表(由$efConstruction$参数控制)。将新节点连接到本层中找到的最近邻居(最多达到限制$M$)。为保持图的质量并限制每个节点的连接数(由$M_{max}$控制),可能会修剪现有连接。将本层中找到的最接近的节点作为下一层搜索的入口点。重复此过程,逐层向下,直到到达第0层。随着层级下降,搜索变得越来越精细。参数$M$(每层每个节点的最大连接数)和$efConstruction$(索引构造期间动态候选列表的大小)在此阶段很重要。更高的值通常会生成更高质量的图(可能提高搜索准确性),但会增加索引构建时间和内存占用。搜索邻居(查询)当查询向量到达时,搜索过程与插入逻辑相似,但不将查询向量添加到图中:顶层入口: 从图的顶层中指定的入口点开始。贪婪搜索(逐层):在当前层中,在当前最佳候选节点的邻居中找到最接近查询向量的节点。此搜索维护一个动态候选列表(由$efSearch$参数控制)。进行贪婪导航:从当前节点移动到更接近查询向量的邻居。重复此操作,直到在本层中找不到更近的邻居(一个局部最小值)。本层中找到的最接近的节点成为下一层搜索的入口点。重复此过程,逐层下降,直到在第0层执行搜索。结果收集: 在第0层进行的搜索会生成最终的近似最近邻集。返回的邻居数量通常由用户指定(例如,top-k)。$efSearch$参数在此处很重要。它控制每层搜索期间所考察的候选列表的大小。较大的$efSearch$允许更详尽的搜索,增加找到真实最近邻(更高召回率)的概率,但代价是增加搜索延迟。它必须至少与所需邻居数量(k)一样大。HNSW的权衡HNSW提供可调整参数,让您管理以下各项之间的权衡:搜索速度(延迟): 返回结果的速度。主要受$efSearch$和图结构($M$)影响。较低的$efSearch$更快。召回率(准确性): 找到真实最近邻的比例。主要受$efSearch$、$efConstruction$和$M$影响。更高的值通常会提高召回率。索引构建时间: 插入所有向量所需的时间。受$efConstruction$和$M$影响。更高的值需要更长时间。内存占用: 内存中索引图的大小。受$M$(更多连接 = 更多内存)和节点总数影响。与IVF(倒排文件索引)等方法相比,HNSW在给定搜索速度下通常能获得更高的召回率,尤其是在高维空间中,尽管其索引构造可能计算量更大,并且通常占用更多内存。其优势体现在通过分层结构实现高效的图通过。了解这些机制,可以帮助您在向量数据库中构建HNSW索引时选择适当的参数,平衡性能要求与您的特定应用所需的准确性水平。