HNSW算法：让向量检索快如闪电的“分层地图”
如果你接触过AI应用开发，大概率对“向量检索”这个词不陌生。无论是RAG系统中的知识库检索，还是推荐系统中的相似物品查找，背后都离不开一个核心问题：如何在海量高维向量中快速找到与目标最相似的那些？
最朴素的方法是暴力扫描（KNN），逐一计算查询向量与库中所有向量的距离。这种方法在数据量小的时候很精确，但面对百万甚至亿级数据时，耗时和算力都无法接受。
于是，近似最近邻（ANN） 算法应运而生。它们在精度和速度之间寻找平衡，而HNSW（Hierarchical Navigable Small World，分层可导航小世界） 正是目前公认表现最优秀的ANN算法之一。如果你理解它背后的思想，就会觉得它异常巧妙。
核心思想：两份经典的智慧融合
HNSW并非凭空创造，它是两种经典数据结构的“混血儿”：
-
可导航小世界图（NSW）：一种近邻图。每个节点（向量）都与其相似的节点相连。搜索时，通过“贪婪路由”从任意起点出发，不断跳转到与查询向量更近的邻居，直到找到局部最优解。这就像在一个小圈子里通过朋友找人，效率很高，但容易陷入局部最优。
-
跳表（Skip List）：一种多层的链表。底层包含所有元素，越往上层元素越少，并且指针可以“跳过”中间节点，从而实现快速查找。
HNSW的巧妙之处就在于，它把跳表的分层思想应用到了NSW图上，构建了一个多层图结构。
工作原理：如登高望远，逐渐聚焦
你可以把HNSW想象成一个拥有不同缩放层级的地图。
- 高层（稀疏层）：就像从卫星看地球，只包含少量“地标性”的节点，它们之间的连线很长，代表着长距离的跳转。在这里搜索，是为了快速定位到目标所在的大区域。
- 底层（稠密层）：就像城市街道图，包含了所有的数据节点，连接非常精细。在这里进行搜索，是为了在目标区域内进行精确查找。
搜索过程也像这个思路，自上而下进行：
- 从最高层的入口点开始，贪婪地寻找当前层离查询向量最近的节点。
- 下降到下一层，以上一层找到的节点为起点，继续贪婪搜索。
- 重复这个过程，直到到达最底层。在最底层找到的最近节点，就是最终结果。
这个过程有点像你先坐高铁（高层）从一个城市到另一个城市，再换乘地铁（中层），最后步行（底层）到达具体地址——高效又精准。
关键参数：掌控“速度与精度”的旋钮
HNSW的性能主要由几个参数控制，调整它们就是在精度、速度和内存之间做权衡。
M(每个节点的最大连接数)：决定图的密度。M越大，图越稠密，搜索路径越多，召回率越高，但内存占用和构建/查询时间也会增加。Milvus的默认值是30。efConstruction(构建时的候选池大小)：在构建图时，为每个新节点考察的候选邻居数量。值越大，图质量越好，召回率越高，但索引构建时间会显著变长。它不影响查询速度。ef(搜索时的候选池大小)：查询时，每一步考察的潜在邻居数量。ef越大，搜索越彻底，召回率越高，但查询延迟也会增加。
调参策略通常建议：先用默认值（如M=16），然后优先调整ef来平衡召回率和延迟。如果对召回率有更高要求，再逐步增加M或efConstruction。
优点与代价
HNSW之所以成为向量数据库（如Milvus、Elasticsearch）和许多应用的首选索引，是因为它有非常突出的优势：
- 查询速度极快：能达到对数级别的时间复杂度（~O(log N)），在百万级数据上也能实现毫秒级响应。
- 召回率高：在速度和精度之间取得了极佳的平衡，搜索质量有保障。
- 增量插入友好：支持动态添加新数据，无需重建整个索引。
但同时，它也有代价：
- 内存开销大：存储图结构（节点和边）需要大量内存。例如，300万条词向量经过8位量化后仍需约3GB内存。
- 构建时间较长：构建索引的时间复杂度为O(N log N)。
总结
HNSW通过构建一个分层的、从粗到细的近邻图，巧妙地解决了高维空间向量检索的效率难题。它用可控的精度损失和较高的内存开销，换来了惊人的检索速度，是支撑现代AI应用检索环节的坚实基石。
理解其背后的“跳表+小世界图”思想，以及掌握M、ef等核心参数的调优方法，是你在实际项目中用好这个强大工具的关键一步。