HNSW：高效近似最近邻搜索算法

一句话解释

HNSW 是一种高效查找“最相似”向量的算法，它把数据点组织成多层图结构，搜索时从顶层快速定位到候选区域，再逐层细化，就像导航地图先看全局路线再查街道。

为什么会被关注

随着大模型和向量嵌入的普及，需要在海量高维向量中实时找到最近邻居。传统暴力搜索太慢，而树形或哈希方法精度损失大。HNSW 在查询速度、内存占用和召回率之间取得出色平衡，成为工业生产中最受欢迎的 ANN 算法之一。

许多主流向量数据库（如 Milvus、Weaviate、Qdrant）都将 HNSW 作为默认或核心索引，Faiss 也提供了 HNSW 实现。其开箱即用的性能和灵活性让它几乎成了向量检索的“标配”。

核心逻辑

HNSW 的核心思想是“分层的可导航小世界图”。它构建多层图：底层包含所有节点，上层节点稀疏。搜索时从顶层入口节点开始，在每个层次内使用贪婪搜索（沿图中最接近目标的边移动），然后下降到下一层，重复直到底层。

构建时，每个新节点随机分配一个层数（服从指数衰减分布），然后从顶层插入，逐层找到该层邻居点并连边。这种“分而治之”的方式让长距离跳跃在顶层完成，底层只做精细搜索，大幅降低搜索复杂度到 O(log n)。

常见场景

搜索引擎中，将文档、图片、音频都编码为向量后，用 HNSW 索引实现语义相似内容推荐。例如电商“找同款”商品、短视频平台“相关推荐”。

对话式 AI 中，用户问题向量化后通过 HNSW 快速匹配知识库中最相关的 Q&A 片段，用于 RAG（检索增强生成）管线，减少大模型幻觉。

生物信息学中，用于蛋白质序列、分子结构的相似性查找；地理信息系统中，用于 GPS 轨迹或地理坐标的快速邻近查询。

容易混淆的点

HNSW 与“小世界网络”模型不同：后者是社会学概念，强调六度分隔；HNSW 是工程算法，通过显式构造长/短边实现高效搜索，并非自然网络。

HNSW 与“图神经网络”无关：GNN 是用于学习图结构数据的神经网络，HNSW 是索引结构，不涉及训练或学习。

HNSW 的搜索结果是近似最近邻（ANN），并非精确结果。但在合理参数下（如 ef_search），其召回率可达到 99% 以上，远快于暴力搜索的 kNN。