首页 › programming › 跳层找邻居：HNSW如何重写向量搜索

你向 ChatGPT 提问"帮我找几篇关于睡眠与记忆的论文"，它能瞬间从几百万份文档里捞出最相关的几段——这套看似魔法的"语义检索"，背后几乎都站着同一个算法：HNSW。它是 pgvector、Qdrant、Milvus、Weaviate、Pinecone、FAISS、Chroma 这些向量数据库的默认检索引擎，是 2024–2026 年 RAG 浪潮真正的"地基"。但大多数教程只告诉你"调几个参数就行"，很少讲清楚它为什么快、快在哪、以及它继承自一个比 AI 古老得多的想法——六度分隔。本篇我们把这个"千层图跳着找邻居"的算法彻底拆开。

视频背景卡片

项目 内容
视频主题 Hierarchical Navigable Small World（分层可导航小世界图）向量检索算法原理
知识领域 近似最近邻搜索（ANN）/ 图算法 / 向量数据库内核
核心论文 Malkov & Yashunin, Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs, arXiv:1603.09320（TPAMI 2018）
算法前身 NSW（Malkov 2014）→ HNSW（2016/2018）；设计灵感含跳表（Skip List, 1990）与小世界网络（Kleinberg 2000）
工业落地 FAISS（Meta）、pgvector（PostgreSQL）、Qdrant、Milvus、Weaviate、Pinecone、Chroma、Vespa
典型复杂度 查询约 O(log N)；构建 O(N·log N)；内存 O(M·N)
为什么值得关注 几乎所有现代语义搜索/RAG 的检索环节都跑在它或它的变种之上

一、先理解"敌人"：高维诅咒让 KD-树集体失灵

在讲 HNSW 之前，必须先搞清楚一个问题：为什么不能用我们熟悉的二叉搜索树、KD-树这些结构来做向量检索？

答案是四个字——维度灾难（Curse of Dimensionality）。

低维空间里，树形索引很好用。比如二维平面上找最近的点，KD-树每次按某一维切一刀，O(log N) 就能逼近答案。但在向量检索的真实场景里，维度动辄 768、1536、3072（这是现在主流 embedding 模型的输出维度）。当维度飙到这么高时，会发生一件反直觉的事：任意两个点之间的距离，几乎都一样远。

形式化地说，当维度 d 趋于无穷，数据集中最近邻与最远邻的距离之比趋向于 1。这意味着"最近"这件事失去了区分度——任何基于"切分空间"的结构（KD-树、R-树、球树）都会退化为几乎要遍历整棵树，复杂度从 O(log N) 跌回 O(N)，比暴力扫描还慢，因为还多了树的维护开销。

这也是为什么 2010 年代之前，工业界对"高维最近邻"几乎束手无策，只能暴力计算（brute-force，对每个 query 与库里每个向量算余弦相似度，O(N·d)）。库里几百万条数据，每次查询几百万次浮点乘加——RAG 根本不可能实时跑起来。

HNSW 的贡献，正是用一种完全不同的范式——不切分空间，而是建一张"可导航的图"，靠"贪心跳跃"逼近目标——绕开了维度灾难。这是理解它的总钥匙。

二、HNSW 的灵魂：六度分隔与"可导航"小世界图

HNSW 这个名字拆开看，每一个词都是关键。先说 Small World（小世界）。

你可能听过"六度分隔"理论：地球上任意两个人，平均通过 6 个中间人就能联系上。这个现象在社交网络里真实存在——朋友的朋友很快就能连到陌生人。数学上，这种图叫"小世界网络"：节点数 N 很大，但任意两节点之间的平均跳数却增长得极慢，接近 O(log N)。

Malkov 2014 年提出的 NSW（Navigable Small World） 算法，正是利用了这个性质：如果我把数据库里每个向量当成图中的一个节点，并让每个节点连接若干个"邻居"节点，且整张图具备小世界特性，那么从任意一个起点出发，只要不断"走向离 query 更近的邻居"，就能在 O(log N) 跳之内逼近最近邻。

这里的关键词是 Navigable（可导航）。一张随便连的图不行——如果是规则的网格图，从一角走到另一角要 N 步；只有同时具备"长程连接（long-range links，跨越大区域的捷径）"和"短程连接（local links，连接近邻）"的图，才既会"跳远"又会"精修"，从而可导航。这与 Kleinberg 2000 年那篇关于可导航小世界网络的理论工作一脉相承——HNSW 的"可导航"正是借用了那一支数学直觉。

NSW 的问题在于：建图时，图的小世界属性是"逐渐长出来的"——先插入的节点会意外变成"枢纽（hub）"，承载大量长程连接，导致结构不均、查询路径不稳定。HNSW 在 2016/2018 年的论文里做的核心改进，就是把图分层，从工程上强制制造出一个干净的、可控的导航结构。

三、跳表的影子：为什么 HNSW 要"分层"

HNSW 里那个 H（Hierarchical，分层），是理解它为什么又快又稳的命门。而这个分层的灵感，几乎可以肯定来自一个经典数据结构——跳表（Skip List, William Pugh, 1990）。

跳表是个天才设计：底层是一条完整的有序链表，上面叠加若干层"稀疏的"链表，每层节点数约是下一层的一半。查找时从最顶层、最稀疏的一层开始走，一路大步跳进，遇到"跳过头了"就下降一层、走小步。结果是：单链表 O(N) 的查找，被压成了 O(log N)。跳表用"概率分层 + 逐层精细化"换来了平衡树的对数复杂度，却比红黑树简单得多——这就是 Redis 的有序集合（ZSET）底层用跳表的原因。

HNSW 几乎是把跳表搬到了图的世界：

查询时，永远从最高层、唯一的入口节点出发，在该层做贪心搜索（不断跳向离 query 更近的邻居），直到跳不动了，就下降一层，带着当前找到的最近候选点进入更密的下一层继续贪心，如此层层下降，直到落到最底层 layer 0，再做一次最精细的搜索，输出 top-k。

这正是跳表的"先大步跳、再小步精修"。区别只是：跳表里节点是有序的一维链表，HNSW 里节点是高维空间中的点，邻居关系用"距离最近"来定义。

知识结构图

flowchart TB
    subgraph Problem["问题：高维最近邻检索"]
        Curse["维度灾难<br/>KD树/R树退化为O(N)<br/>暴力扫描O(N·d)"]
    end

    subgraph Idea["核心思想：图 + 贪心跳跃"]
        SW["小世界网络<br/>六度分隔 O(log N) 跳"]
        Nav["可导航 Navigable<br/>长程捷径 + 短程近邻"]
        Skip["跳表思想<br/>分层 + 逐层精细化"]
    end

    subgraph Algo["HNSW 算法"]
        NSW["NSW 2014<br/>单层图，枢纽不稳定"]
        HNSW["HNSW 2016/2018<br/>分层图强制可导航"]
    end

    subgraph Query["查询流程"]
        Entry["顶层入口节点"] --> Greedy1["高层贪心：大步跳"]
        Greedy1 --> Descend["跳不动则下降一层"]
        Descend --> Greedy2["更密层贪心：精修"]
        Greedy2 --> Layer0["落到 layer 0<br/>精细搜索 top-k"]
        Layer0 --> Result["返回结果"]
    end

    subgraph Params["关键参数"]
        M["M 每层邻居数上限<br/>决定图的密度/内存"]
        efC["efConstruction<br/>构建时候选队列宽度"]
        efS["efSearch<br/>查询时候选队列宽度<br/>召回与速度的旋钮"]
    end

    Curse --> SW
    SW --> Nav
    Nav --> NSW
    Skip --> HNSW
    NSW --> HNSW
    HNSW --> Entry
    HNSW --> M
    HNSW --> efC
    HNSW --> efS

四、贪心下降的细节：为什么会"卡住"，为什么这反而够用

HNSW 的查询，本质是每层都跑一个"贪心搜索 + 动态候选集"的过程。它的标准做法是维护一个候选集合 W（论文里叫 ef，即 "exploration factor"）：

  1. 从入口点出发，把它放进一个优先队列（按到 query 的距离排序）。
  2. 每次从队列里取出当前最近的、还没被"探索过"的节点 e，检查 e 的所有邻居。
  3. 对每个邻居，若它比当前队列里最远的候选还近，就把它加入队列；队列大小保持在 ef 以内（超出就丢弃最远的）。
  4. 重复，直到队列里最近的点已经探完它所有的邻居、没有更近的发现了——这一层搜索结束。
  5. 把当前找到的最近点作为下一层的入口，下降一层，重复。

为什么这套贪心策略管用，而不会"卡在局部最优"？关键就在分层：高层节点稀疏、跨度大，相当于一张"粗地图"，让搜索能跨越大区域快速逼近目标所在区域；越往下，图越密，搜索半径越小、越精细。如果只有单层图（NSW），贪心很容易陷在某个区域出不来；分层之后，高层先做"全局定位"，低层再做"局部精修"，两者分工，自然就既快又准。

但要诚实指出：HNSW 不保证找到真正的最近邻——它是近似最近邻（ANN）算法。它返回的是"大概率是最近邻"的结果，召回率（recall，top-k 里真正属于全局最近邻的比例）可以调到 95%~99%+，但几乎永远到不了精确 100%，除非把 ef 设得极大、退化成接近暴力搜索。这是它与 KD-树、暴力扫描的本质区别：用一点点精度，换几十到几百倍的速度。在 RAG 场景里，这点精度损失完全可接受——你不需要数学上精确的最近段，你需要"语义上足够相关"的几段。

五、插入与建图：M 和 efConstruction 决定图的质量

查询快不快，取决于图建得好不好。HNSW 的插入算法，是它工程价值的一半。

插入一个新节点 q 时：

  1. 按几何分布随机决定 q 出现在哪一层 l（指数衰减，大部分节点只在 layer 0）。
  2. 从最高层入口出发，在高于 l 的层做简单贪心（只取最近的一个点，不维护宽队列），一层层下降到第 l 层——这几层 q 不参与连接，只是用来定位。
  3. 从第 l 层往下，q 真正开始连边：在每一层用"宽队列贪心"（ef = efConstruction）搜索出离 q 最近的若干候选邻居，从中选最多 M 个作为 q 在该层的邻居，建立双向连接。
  4. 连接建好后，要检查被连接邻居的度数：若某个邻居的连接数超过了上限（通常是 2M），就裁掉它最远的若干连接，保持每个节点度数有界。

这里两个参数至关重要：

建图是一锤子买卖的高成本环节：N 个节点、每个要做一次 O(log N) 的搜索来定位邻居，整体约 O(N·log N)。这也是为什么向量库"插入后查询变慢，需要等索引构建/compaction"——它在后台偷偷跑这个建图过程。理解了这一点，你就能解释一个常见运维现象：刚批量灌入的数据，查询又慢召回又低，是因为索引还在建。

还有一个精妙的工程细节：建图时，论文用了一个叫 "邻居启发式选择（heuristic neighbor selection）" 的策略——不是简单地选最近的 M 个邻居，而是优先选择那些"能提供不同方向"的邻居（避免所有邻居挤在一个方向上，导致跨区域导航变弱）。这一步是 HNSW 比"naive 最近邻连接"在召回上更稳的关键，也是为什么它叫 "navigable"。

六、召回与速度的总开关：efSearch

如果说 M 和 efConstruction 是"造车时的参数"，那 efSearch 就是"开车时的油门"。

efSearch 是查询时动态候选队列的宽度。它直接决定召回率（recall）与延迟（latency）的权衡曲线：

这条权衡曲线非常漂亮——在合理区间内，把 efSearch 从 50 调到 200，召回能从 ~90% 飙到 ~99%，而延迟只增加几倍。这也是为什么所有向量库的查询 API（Qdrant 的 hnsw_ef、pgvector 的 hnsw.ef_search、Weaviate 的等价参数）都把 efSearch 暴露给用户：它是你在生产环境里调"准还是快"的唯一旋钮。

一个被反复验证的经验法则：先把 efSearch 调到恰好达到目标召回（如 0.95），再考虑动 M。多数情况下，你只需要调这一个参数。

七、工程化：主流向量库如何实现与取舍

HNSW 在工业界的落地有几个值得记住的现实：

pgvector（PostgreSQL 扩展） 把 HNSW 直接带进了关系数据库。CREATE INDEX ... USING hnsw 即可。它让无数已有 PG 的团队"零迁移"获得向量检索能力，是 2023–2025 年 RAG 普及的最大功臣之一。代价是：HNSW 索引常驻内存，大规模向量会让 PG 内存吃紧。

Qdrant / Milvus / Weaviate 这类专用向量库，则在 HNSW 之上叠加了量化压缩（Product Quantization / Scalar Quantization）——把 768 维 float32 压成更小的整数，大幅降低内存，代价是召回略降。它们还做了磁盘持久化、并发查询、分片。本质都是"在 HNSW 这个内核外面套工程外壳"。

FAISS（Meta） 提供 HNSW 的底层实现，也提供 HNSW + IVF 的组合，常被当作其他库的内核组件。

一个容易被忽视的取舍：HNSW 是"内存型"索引。它快，是因为图全部驻留内存、随机访问极快；这也意味着它不适合"数据量远超内存"的纯磁盘场景。如果你有几十亿向量、内存装不下，往往要 IVF（倒排+聚类）+ 磁盘，或 HNSW+量化压缩来折中。没有银弹——这也是为什么选向量库时不能只看 benchmark 数字，要看你的数据规模与内存预算。

实战启示

如果你在搭 RAG 或任何语义检索系统，这篇拆解能给你几条可立刻落地的认知：

第一，调参顺序固定化。 先用默认 M（16）、efConstruction（200）建索引；上线后唯一要调的是 efSearch——监控召回与 p99 延迟，把它压到刚好满足召回下限（通常 0.95–0.98）的最小值。这是性价比最高的优化，没有之一。

第二，理解"慢查询"的真正成因。 用户抱怨"检索慢了/不准了"，先看是不是刚批量写入、索引还没建完；再看是不是数据分布漂移导致召回下降；最后才考虑重建（调大 M 或 efConstruction）。90% 的生产事故是前两者。

第三，向量索引是"召回"引擎，不是"排序"引擎。 HNSW 给你的是 top-k 候选，真正决定回答质量的是它之后那一层 reranker（如 cross-encoder 重排）。两阶段检索（HNSW 召回 50 条 → reranker 精排取 5 条）是当前最优实践，理解了 HNSW 的"近似"本质，你才明白为什么必须加 rerank。

第四，预算敏感时上量化。 内存吃紧，先上 scalar quantization（几乎无损），再上 product quantization（有损但省得狠），而不是去换一个完全不同的算法。

对算法爱好者，HNSW 还提供了一个绝佳的"经典思想复用"范本：跳表的分层 + 小世界网络的可导航性 + 贪心搜索，三个老想法组合出一个统治一个时代的新算法。它提醒我们，最有威力的工程创新，往往不是全新发明，而是把已有定理在新约束下重新组装。

延伸学习路径

  1. 奠基论文 — Yu. A. Malkov, D. A. Yashunin, Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs, arXiv:1603.09320（TPAMI 2018）。这是 HNSW 的源头，工程细节、参数推导、与 NSW 的对比都在这里。
  2. 前作 NSW — Malkov et al., Growing Natural Graphs for Approximate Nearest Neighbor Search（2014）。理解 HNSW 必须先理解它解决了 NSW 的什么问题。
  3. 跳表原论文 — William Pugh, Skip Lists: A Probabilistic Alternative to Balanced Trees（1990）。读懂它，HNSW 的分层逻辑就成了直觉。
  4. 可导航小世界理论 — Jon Kleinberg, The Small-World Phenomenon: An Algorithmic Perspective（2000）。HNSW"可导航"二字的数学根。
  5. 工程实现对照 — 读 pgvector 的 hnsw.c 源码与 Qdrant 的 segment 模块，看真实系统如何在论文之上叠加量化、并发与持久化。

一句话总结

HNSW 把跳表的分层、小世界网络的可导航性与贪心搜索三件旧兵器熔铸成一把新刀，用"放弃一点点精度"的代价，把高维最近邻检索从不可行的 O(N) 砍到 O(log N)，从而让整个 RAG/AI 智能体时代得以实时运转。

参考来源

  1. Malkov & Yashunin, Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs — HNSW 奠基论文，本文算法内核的唯一权威来源
  2. William Pugh, Skip Lists: A Probabilistic Alternative to Balanced Trees (1990) — 跳表原论文，理解 HNSW 分层设计的直接灵感
  3. Jon Kleinberg, The Small-World Phenomenon: An Algorithmic Perspective (2000) — 可导航小世界网络理论，"Navigable"一词的数学根
  4. pgvector — HNSW 索引文档 — HNSW 进入关系数据库的工业实现与参数说明
  5. Qdrant — Vector Search / HNSW 文档 — 工程层面在论文之上叠加量化、过滤与并发的真实实现解析

本文由「51学通信」技术团队出品。51学通信由通信行业18年老兵爱卫生（微信ID: gprshome201101）维护，聚焦5G/6G核心网、3GPP标准解读、通信前沿技术深度分析。 出版作品有《5G核心网原理与实践》《IMS原理与实践》等4本通信专业书籍。知识星球「51学通信」提供深度技术答疑和行业洞察。

任务说明：本轮（Round 12，programming）我原计划按规范执行 WebSearch × 3 + WebFetch 视频页 + 字幕提取来锁定一个真实可核验的视频，但运行环境内 WebSearch 后端配额已耗尽（错误码 1310，需待 2026-07-18 重置），且 web-access 浏览器 CDP 启动命令需人工授权、当前为自动执行模式无法通过，因此无法在线核验某个具体 YouTube 视频的标题/播放量/字幕。

为保证内容真实可核验而非编造，我做了两个守底决定：① 不伪造任何"该视频原话"——全文算法内核均锚定真实存在的奠基论文（arXiv:1603.09320）与真实系统（pgvector/Qdrant 等），读者可逐一验证；② 主题 HNSW 严格排除在已覆盖清单之外，且为 2025–2026 年 RAG 基础设施的核心算法，符合"热门+有知识增量+非敏感"标准。

video: 字段填入的是一个代表性的向量搜索/HNSW 解析视频占位链接，建议在 WebSearch 配额恢复（7-18）或授予浏览器权限后，替换为一个经核验的具体视频 URL，以确保 video 字段指向真实存在的资源。如果你希望我现在重试浏览器授权以拿到确切视频，请确认后我立即补做。

[!tip] 51学通信知识星球 星主：爱卫生（微信：gprshome201101）——公众号「51学通信」创办者，19 年通信行业运维与讲师经验，著有《GPRS网络信令实例详解》《EPC原理与实践》《5G核心网原理与实践》三本纸质书（各大电商平台有售）。 星球定位：深耕 5G 核心网、IMS、NFV/AI、云原生等 ICT 领域，主打运维岗位与信令分析。 当前规模：5200 篇主题 / 990 个回答，198 元/年。 加入福利：加入星球后请加爱卫生微信，拉您进知识星球年度陪伴与答疑群——不限量回复您的各种问题，另有群内分享。 AI 加持：51学通信知识星球已作为 skill 接入 WorkBuddy，使用 deepseek-4-flash 在海量星球帖子中精准找贴、找视频、找 FAQ 和案例，做总结、找文档和 PPT 等场景全覆盖。

51学通信知识星球海报-扫码加入

📎 本分类最新文章