HNSW算法：高效向量近邻搜索

CH-28-03-007·约 17 分钟·搜索推荐与信息检索·更新 2026-08-13

想象你在一个陌生城市，导航要去一家藏在老巷子里的苍蝇馆子。你不会开车一条街一条街地找，而是会先上高架快速路，一口气穿越多个街区；然后下高架走主干道，接近目标所在区域；最后拐进巷子，在小区里兜一圈找到那家店。为什么这样最快？因为高架路少、视野远、能快速拉近距离；而巷子密、门牌杂，但能精确指向每个目标。 HNSW（Hierarchical Navigable Small World，分层可导航小世界图）算法的设计思路，与这套城市路网导航逻辑如出一辙。在向量检索的世界里，我们会把用户、商品、文档变成高维向量——例如一张图片被编码成256维数字坐标。当用户抛来一个查询向量时，系统要在海量向量中快速找到“最相似”的那一批。朴素做法是逐条暴力比对，如同在没有路网的城市里挨家敲门；而HNSW把数据点组织成一张分层地图：顶层稀疏、底层稠密，搜索时从顶层长距离跳跃，逐层下探，最后在底层精确定位。它是向量数据库与推荐系统中主流的近似最近邻（ANN）算法。

岗位关联

理解HNSW，你就掌握了从“全量扫描”走向“对数级查询”的关键一跃，这也是向量数据库、推荐系统、RAG架构中召回模块最重要的底层原理。

可视化演示
算法背景：为什么需要近似最近邻
小世界图：六度分隔与贪心导航
分层结构：从高架到小巷
构建流程：新店接入路网
邻居策略：挑选互补的同行
搜索机制：从入口到候选队列
参数调优：三个旋钮的平衡
工程对比：HNSW与IVF-PQ
AI 应用场景
Python 演示
常见误区
面试题

可视化演示

动态演示HNSW算法的核心机制，通过架构/数据/状态/性能四种模式展示关键概念与交互流程。

本节配有交互动效（进入视口后自动加载，约 3KB）。

HNSW算法：一HNS 一、HNSW分层图结构与跳表思二、小世界图与可导航性原理核心机制可视化 HNSW算法整体架构与关键组件

算法背景：为什么需要近似最近邻

想象你经营一家线上书店，读者刚读完《三体》，你想立刻推荐几本气质相近的书。推荐引擎先把每本书变成一串高维坐标——embedding向量，语义越接近的书，坐标越贴近。问题随之而来：面对一千万本书，怎样快速找到那几本“最近”的？最朴素的办法是逐本计算距离再排序，如同在迷宫般的书库里挨家挨户翻找。数据少时还能忍，数据一多，每次查询就是百万亿次浮点运算，延迟直接爆表。

于是“近似最近邻”（ANN）登场：它允许我们稍微放松“绝对最近”的要求，换取秒回的查询速度。HNSW正是这一赛道里兼顾召回率、速度与内存的标杆算法。它不把所有向量排成一排挨个比较，而是把它们组织成一张“分层地图”，从宏观切入逐步细化，对应现实就是从“上高架”到“钻小巷”的导航智慧。

衡量两个向量是否相似，最常用的尺子是欧氏距离。两个点越近，语义越相似：

有了这把“距离尺子”，HNSW要解决的核心问题就变成：用最快的路径找到距离查询点最近的那些点，而不是傻乎乎地走遍全城。

\displaystyle d(\mathbf{p},\mathbf{q}) = \sqrt{\sum_{i=1}^{n}(p_i - q_i)^2}

距离越小，说明两个向量的语义越接近，检索时排名越靠前。

逐维差分两个向量的每一维相减，得到这一维上的偏差。
$\mathbf{p} - \mathbf{q}$
平方求和对每个偏差平方后累加，消除正负抵消并放大差异。
$\sum_{i=1}^{n}(p_i - q_i)^2$
开方还原对平方和开根号，得到可比较的欧氏距离。
$\sqrt{\sum_{i=1}^{n}(p_i - q_i)^2}$

小世界图：六度分隔与贪心导航

社会学有个著名现象叫“六度分隔”：你和地球上任一陌生人之间，平均只隔着五个中间人。这是因为社交网络中存在少量“长连接”——你的朋友圈里总有人认识其他圈子的人。把这种现象搬到向量空间，就得到小世界图（NSW）。图中的每个点连接若干邻居，其中一小部分边格外长，能一步跨越很远。

NSW的搜索方式十分朴素：从任意起点出发，每一步都走向距离目标更近的邻居，直到无法再近，这就是贪心搜索。它基本不走回头路，每一步都在缩小包围圈。但原始NSW有个明显的毛病：早期插入的节点容易变成“超级枢纽”——连接很多但位置偏僻，搜索时经常被带偏，路径冗长低效。

单步贪心决策可以用公式表示——从当前节点v的邻居集合中，选择离查询q最近的那个节点作为下一步：

小世界图虽然已有不错的导航性，但单层的结构在高维数据上仍会绕路。解决问题的关键，是把“一张图”升级为“多层级的路网”。

\displaystyle v_{\text{next}} = \arg\min_{u \in N(v)} d(u, q)

每一步都只选当前视野内最近的方向，像在巷子里问路：只问隔壁几家店，朝着目标方向移动。

邻居候选当前节点v的邻居集合N(v)构成候选池，下一步只能从这些邻居里选。
$u \in N(v)$
距离比较对每个邻居计算与查询点的距离，并找出最小的距离值。
$\min_{u \in N(v)} d(u, q)$
取最小者arg min 返回使距离最小的那个邻居，作为下一步的落脚点。
$v_{\text{next}} = \arg\min_{u \in N(v)} d(u, q)$

分层结构：从高架到小巷

在城市导航中，你不会每拐一个弯就重新判断方向。先上高架完成长距离跃迁，再走主干道接近区域，最后钻进小区精确定位。如果所有道路都是同一个等级，导航就会在小路里反复试错。HNSW把同样的直觉用在向量图上：构建多层图，上层稀疏、下层稠密。

HNSW借鉴了跳表的分层思想：跳表通过多层链表实现O(log N)的查找，HNSW则用多层图实现近邻搜索。顶层只有少量“代表性节点”，边很长，能快速跨越广阔空间；底层包含全部节点，边短而密，负责精确收敛。搜索时从顶层入口出发，沿层间通道逐级下探，每下一层，视野就更精细一层。

节点属于哪一层由概率决定，通常服从指数衰减：越往上越稀有。设mL为层衰减系数（通常取 1/ln(M)），节点至少出现在第l层的概率为：

这就是“高速路口少但一上去就能跑很远”的数学表达：顶层稀少提供长跳能力，底层稠密提供精确定位。

\displaystyle P(L \ge \ell) = \text{mL}^{\ell}

概率随层数指数下降，保证顶层节点稀少、底层全员在岗，就像高架出口远远少于小区路口。

随机层高L是节点所在的最高层数，由随机过程决定，与数据内容无关。
$P(L \ge \ell)$
衰减基数mL是介于0和1之间的系数，控制每上一层还剩多少比例的节点。
$\text{mL}^{\ell}$
指数效应层数越大，概率快速下降，顶层只留下极少数“枢纽”。
$P(L \ge \ell) = \text{mL}^{\ell}$

构建流程：新店接入路网

一座新城的路网不是天然存在的。每开一家新店，就要把它接入现有道路：先判断这家店该被高速覆盖还是只需小巷可达，然后从高速入口出发，逐级下探到对应等级的路段，找到邻近路口，铺设双向连接。HNSW的构建过程与此几乎一一对应。

插入一个新向量分为四步：第一步，随机决定节点的最高层l；第二步，从全局顶层入口开始，在每一层做贪心搜索；第三步，在层l及以下各层选出距离最近的邻居集合；第四步，建立双向边——既让新节点指向邻居，也让邻居回指新节点。这样图始终保持“可双向导航”的性质，查询时才能从任意入口顺利到达。

插入时搜索逐层下降的范围可以表示为：

每一层下探时，以上一层的最近点为新入口，保证搜索只在高层的“路口”间跳跃，而不是从底层重新漫游。这一设计让构建阶段的耗时同样接近对数级。

就像新店开张时，物流车先走高速再下省道，最后在巷口停靠，沿途把包裹递给经过的每个站点，HNSW的插入也把连接一步步“铺”到每个经过的层。

\displaystyle \ell = L_{\max}, L_{\max} - 1, \ldots, l

插入搜索从最高层一直下探到该节点实际存在的层，之后才开始建立连接。

初始最高层搜索从图当前的最高层入口开始，先做宏观定位。
$\ell = L_{\max}$
逐层递减每层搜索结束后，把最优点传给下一层作为入口继续下行。
$\ell \leftarrow \ell - 1$
到达目标层下探到该节点所在层l即停止，并在该层及以下各层建边。
$\ell = l$

邻居策略：挑选互补的同行

小区门口的商业街如果全是奶茶店，顾客来了只能买到奶茶；真正好逛的街区，奶茶店、便利店、水果店错落分布，互相引流。图的邻居选择同理——如果某个节点的邻居全挤在同一方向，搜索路径就会视野狭窄，容易陷入局部死角。

HNSW在每层选边有两种策略。第一种是简单策略：直接选距离最近的m个节点，计算快，但容易让邻居扎堆。第二种是启发式策略：逐个候选评估，只有当一个候选比“已入选的所有邻居”都更靠近新节点时才保留，从而保证每个邻居都提供不同的方向信息。

启发式保留判据是：候选e要被选入结果集S，前提是它比S中任意已选邻居更靠近新节点q：

这就像招商时问：“这位新店主能带旺街区的哪个角落？如果和现有店铺完全重叠，就不必引进了。”多样化邻居让搜索路径更笔直。

\displaystyle d(e, q) < \min_{r \in S} d(e, r)

这条判据衡量“有没有给S带来新的方向”，避免选一圈互相挨得很近的冗余邻居。

候选到新点先计算未入选候选e到新节点q的距离。
$d(e, q)$
最近已选者找出候选e到已选邻居集合S中最近的那个节点。
$\min_{r \in S} d(e, r)$
方向性比较若e比那个最近已选者还近，说明e提供了新方向，保留；否则丢弃。
$d(e, q) < \min_{r \in S} d(e, r)$

搜索机制：从入口到候选队列

导航App的搜索总是一路收窄：上高架确定大方向，下高架在主干道间切换，进入小区后放慢速度对比几栋楼。每一步都不跑回头路，但每层都会保留多个候选路口，以防选错。HNSW的在线查询正是这样运行的。

查询从顶层入口点出发，每一层的贪心搜索不只盯一个最优点，而是维护一个大小为efSearch的候选队列。队列里始终装着当前最有希望的efSearch个节点，每访问一个新节点，就把它的邻居并入队列，再按距离排序、截断。逐层下探后，底层继续扩展，直到队列中最优的点不再变化。

当访问到节点v时，队列的更新规则是：把v的所有邻居并入候选池，再按与查询点的距离排序，只保留前efSearch个：

这就像导航同时显示三条备选路线：始终保留最好的几条，等快到小区附近再最终确定走哪条巷子。

\displaystyle C_{\text{new}} = \mathrm{top\text{-}ef}\big(C \cup N(v)\big)

efSearch越大，候选池越宽，越接近全局最优，但单次查询的耗时也越高。

并入邻居把当前节点v的邻居纳入候选池，扩大搜索视野。
$C \cup N(v)$
按距排序所有候选按到查询点的距离升序排列，近的靠前。
$\text{sort by } d(\cdot, q)$
窗口截断只保留排在前efSearch的节点，控制每一层的搜索成本。
$\mathrm{top\text{-}ef}(C \cup N(v))$

参数调优：三个旋钮的平衡

开车导航时，司机关注三件事：路网修多密、修路时勘探多细、出发前比较几条路线。HNSW的参数正好对应这三件事：M控制每层最多连几条边，efConstruction控制建图时花多大力气搜索，efSearch控制查询时看多少候选。

参数之间相互牵制：M太大，图变密，内存与构建时间上涨；efConstruction太小，建图粗糙，后续查询容易卡壳；efSearch太小，查询快但召回率打折。没有一组参数能同时让所有指标最优，取舍是工程常态。实际部署通常从M=16、efConstruction=200、efSearch=100起步，再根据延迟与召回曲线微调。

在合理配置下，HNSW查询的期望步数接近对数：

这就是HNSW相对暴力扫描最有吸引力的优势——数据量翻倍，查询时间只是微增，而不是翻倍。

调参就像调导航偏好：赶时间就少绕路（小efSearch），求稳妥就多比较几条路线（大efSearch），最终在速度和精度之间找到自己的平衡点。

\displaystyle E[T_{\text{search}}] = O(\log N)

期望对数复杂度的含义：一千万条数据时大约只需几十步探索，远低于全量扫描的千万次比较。

期望复杂度E[T]表示一次查询的平均探索步数，是随机性下的数学期望。
$E[T_{\text{search}}]$
分层收益节点层数期望约为log N，每下探一层都跨越指数级的数据规模。
$L \approx \log N$
常数上限每层只需常数步就能找到下一层入口，因此总步数为对数级。
$O(\log N)$

工程对比：HNSW与IVF-PQ

搬家时，杂物多但预算充足，你会叫一辆大卡车一次拉完；预算紧张，就只能把衣物抽真空压缩，多装几趟。向量索引也有类似的取舍：HNSW像大卡车，IVF-PQ像真空压缩。HNSW把全部原始向量和邻接指针放在内存里，查询精度高、速度快；代价是内存占用高。IVF-PQ先把向量聚成若干类，再做乘积量化压缩，省内存但有一定精度损失。

HNSW在千万级以内、内存充足的场景表现最好；IVF-PQ则更适合亿级以上、内存受限的场景。两者的关键差异可以从内存估算看出。HNSW的内存占用大致为：

其中N是向量数，d是向量维度，M是每层最大邻居数。原始向量加图指针全部驻留内存，好处是查询极快，坏处是数据量一大就放不下。

选型像选运输方案：路途中等选HNSW大卡车，快而贵；货量巨大选IVF-PQ压缩车，省而稳，关键在于认清自己的数据规模与部署预算。

\displaystyle M_{\text{HNSW}} \approx N \times (4d + 16M) \text{ bytes}

上亿数据且内存紧张时，通常考虑IVF-PQ或磁盘索引；数据量中等且延迟敏感，HNSW更合适。

向量本体每个d维float向量占4d字节，这部分无法压缩。
$4d$
图结构指针每个节点约2M个邻居指针，每个指针占8字节。
$2M \times 8 = 16M$
全量求和两者相加后乘以节点总数N，就是整张图的近似内存占用。
$N \times (4d + 16M)$

AI 应用场景

电商商品相似推荐

阶段：召回阶段

解决的问题：传统协同过滤依赖用户行为，对冷启动商品无能为力；基于embedding的向量召回把商品图像与标题编码为向量，但亿级商品下暴力KNN不可行。HNSW在商品向量库上建立分层索引，查询时毫秒级返回候选商品，再交给精排模型细筛，兼顾速度与召回。

具体案例：某跨境电商平台每晚用HNSW对1亿商品向量建索引，用户点击一个商品后，召回系统在5毫秒内返回数百个相似商品，再由CTR模型排序展示，整体推荐GMV提升约12%。

RAG知识库文档检索

阶段：检索阶段

解决的问题：大模型幻觉问题常通过RAG缓解，需要先从知识库中找出相关文档片段。把文档切块并embedding后，HNSW索引让每次对话只扫描很少的候选块，为LLM提供精准上下文，显著降低检索延迟并提升回答准确率。

具体案例：某企业客服机器人知识库约300万文档块，使用HNSW索引后平均检索延迟从120ms降到8ms，召回率保持在95%以上，回答准确率明显提升。

Python 演示

python84 行

import mathimport random  class TinyHNSW:    """极简HNSW：两层结构，演示从稀疏到稠密的分层贪心搜索。"""     def __init__(self, top_size=8):        self.top_size = top_size        self.coords = []        self.is_top = []        self.edge0 = []        self.edge1 = []        self.entry = None     def _dist(self, i, q):        return math.dist(self.coords[i], q)     def insert(self, coord):        idx = len(self.coords)        self.coords.append(tuple(coord))        top = (idx == 0) or (random.random() < 0.4)        self.is_top.append(top)        self.edge0.append(set())        self.edge1.append(set())        if idx > 0:            candidates = list(range(idx))            for _ in range(2):                if not candidates:                    break                best = min(candidates, key=lambda j: self._dist(j, idx))                self.edge0[idx].add(best)                self.edge0[best].add(idx)                candidates.remove(best)        if top:            if self.entry is None:                self.entry = idx            upper = [j for j in range(idx) if self.is_top[j]]            if upper:                best = min(upper, key=lambda j: self._dist(j, idx))                self.edge1[idx].add(best)                self.edge1[best].add(idx)     def search(self, q, steps=5):        if self.entry is None:            return None, []        cur = self.entry        path = [cur]        for _ in range(steps):            nxt = None            for nb in list(self.edge1[cur]):                if self._dist(nb, q) < self._dist(cur, q):                    nxt = nb                    break            if nxt is None:                break            cur = nxt            path.append(cur)        if self.edge0[cur]:            cur = min(self.edge0[cur], key=lambda j: self._dist(j, q))            path.append(cur)        for _ in range(steps):            best = cur            for nb in self.edge0[cur]:                if self._dist(nb, q) < self._dist(best, q):                    best = nb            if best == cur:                break            cur = best            path.append(cur)        return cur, path  if __name__ == '__main__':    random.seed(42)    ann = TinyHNSW(top_size=12)    for _ in range(50):        ann.insert((random.uniform(0, 10), random.uniform(0, 10)))    query = (5.0, 5.0)    ans, route = ann.search(query, steps=5)    if ans is not None:        print('query:', query)        print('found:', ann.coords[ans])        print('route nodes:', len(route))

目的：用50个随机二维点构建一个极简两层HNSW，演示“顶层粗导航→底层精搜索”的完整过程。

top = (idx == 0) or (random.random() < 0.4)第一个节点必定入顶层当作入口，其余约40%概率入顶层，模拟概率分层。
best = min(candidates, key=lambda j: self._dist(j, idx))从底层候选中选距离最近的节点，实现“简单选择”策略。
self.edge0[best].add(idx)邻居也回指新节点，保证连接是双向的，图可双向导航。
upper = [j for j in range(idx) if self.is_top[j]]只与顶层已有点相连，保持顶层稀疏，边少而长跳。
if self._dist(nb, q) < self._dist(cur, q):贪心决策：只走能更接近目标的边，否则停下换层。
cur = min(self.edge0[cur], key=lambda j: self._dist(j, q))从顶层节点下探到它最近的底层邻居，实现“下高架”。

常见误区

误区很多人看到“分层”就以为HNSW是树结构，每个节点只属于一层、有唯一父节点，搜索像二叉树一样从根往下找。

正解HNSW是图不是树。同一个节点会出现在多个层，且每层都有多个邻居；分层只控制“粗到细”的导航节奏，不约束父子关系。就像同一家店既在高架出口能看到招牌，也在巷口能看到招牌，它同时属于两个级别的“路网”。

为何常见：数据库里的B+树、跳表都是分层索引，容易让人望文生义，把“层级”直接等同于“树”。

误区既然efSearch能提高召回率，那每次查询都设置成几千上万，效果一定最好，还省去调参麻烦。

正解efSearch与延迟近似线性增长，当它超过一定值后，召回率收益递减，但延迟肉眼可见地上涨。生产中通常用离线recall@10指标结合P99延迟曲线来找“甜蜜点”，而不是盲目调大。

为何常见：只看效果不看成本，忽略了召回率与延迟的此消彼长关系。

误区HNSW那么快，把全库数据都塞进内存建HNSW就好了，其他算法都可以淘汰。

正解HNSW需要存储原始向量和图的邻接指针，内存开销大。对百亿级数据、或内存远小于数据集规模的场景，IVF-PQ、DiskANN等磁盘或压缩索引更可行。HNSW很优秀，但不万能。

为何常见：算法的光环容易让人忽视内存成本与数据规模这些工程约束。

误区反正建图后包含的向量集合是一样的，先插谁后插谁应该无关紧要，结果都一样。

正解HNSW是增量构建，早期节点决定全局入口和主干边。插入顺序不同，图的拓扑差异可能很大，某些顺序会形成偏科的路网，导致查询绕路。批量导入通常比逐条在线插入能得到更稳定的索引。

为何常见：混淆了“离线批量索引”与“在线增量构建”两种模式的差异，忽略了增量过程的路径依赖。

面试题

Q1. HNSW中的"H"（Hierarchical）指的是什么？

单选题 · easy

A.分层多级图结构← 正确答案
B.哈希函数加速映射
C.混合近邻算法集成
D.高维向量压缩编码

答案：A。HNSW的核心是“分层可导航小世界图”，H代表分层结构，用不同密度的多层图实现从粗到细的导航。它不是哈希、不是多算法集成，也不是专门做向量压缩。

Q2. 在HNSW中，节点被分配到更高层的机制是？

单选题 · mid

A.按插入时间均匀分配
B.按概率指数衰减随机分配← 正确答案
C.按坐标均值聚类分配
D.按节点度数大小排序分配

答案：B。层分配采用指数衰减的概率模型，层数越高概率越低，保证顶层稀疏、底层稠密。它依赖随机过程而非数据内容，与时间、聚类、度数均无关。

Q3. 以下哪些属于HNSW的邻居选择策略？

多选题 · mid

A.直接取距离最近的邻居← 正确答案
B.启发式多样化筛选邻居← 正确答案
C.倒排列表剪枝压缩邻居
D.随机游走采样选择邻居

答案：AB。HNSW提供两种邻居策略：简单策略直接取最近节点，启发式策略通过方向性判据筛掉冗余邻居。倒排列表是IVF的机制，随机游走不是HNSW的建边方式。

Q4. 增大efSearch时，查询端会发生什么？

单选题 · mid

A.召回率上升而延迟上升← 正确答案
B.召回率下降而延迟下降
C.召回率不变内存翻倍
D.构建时间显著变长

答案：A。efSearch控制查询时候选队列大小，队列越大探索越充分，召回率升高，但距离排序耗时也增加，延迟上升。它不影响构建阶段与内存占用。

Q5. 与暴力搜索相比，HNSW查询复杂度的期望值大约是？

单选题 · easy

A.O(N²) 平方级复杂度
B.O(N) 线性级复杂度
C.O(log N) 对数级复杂度← 正确答案
D.O(1) 常数级复杂度

答案：C。HNSW利用分层导航，期望查询步数为O(log N)。完全不可能做到O(1)，也不是线性或平方级，否则分层就没有意义了。

Q6. 关于HNSW与IVF-PQ的对比，以下说法正确的是？

多选题 · hard

A.HNSW的内存占用通常更高← 正确答案
B.HNSW查询速度总是比IVF-PQ慢
C.IVF-PQ需要对向量做量化压缩← 正确答案
D.HNSW的召回率恒低于IVF-PQ

答案：AC。HNSW存储全部原始向量和邻接指针，内存更高；IVF-PQ用乘积量化压缩向量所以更省内存。但查询速度与召回率没有“总是/恒”的绝对关系，取决于数据规模与参数配置。

Q7. 构建HNSW索引时，efConstruction参数的核心作用是？

单选题 · mid

A.控制建图时候选队列的大小← 正确答案
B.控制向量量化的比特数
C.控制最多聚类簇的数量
D.控制每层最短路径长度

答案：A。efConstruction决定插入节点时每层搜索候选队列的宽度，队列越宽，建图质量越高但耗时越长。它与量化比特数、聚类数量、路径长度无关。

Q8. HNSW中参数M直接影响的是？

单选题 · mid

A.每层最大邻居连接数← 正确答案
B.向量的特征维度数
C.训练集样本数量
D.查询返回的最大条数

答案：A。M是每层最多允许建立的邻居边数。它决定图的连通密度，影响内存与搜索路径长度，与向量维度、样本量、返回条数没有直接关系。

Q9. 为什么HNSW要先在顶层做“粗导航”再逐层下探？

单选题 · hard

A.减少逐点比较的总步数← 正确答案
B.顶层存储的数据质量更高
C.顶层包含全部的精确向量
D.底层查询不支持任何过滤

答案：A。顶层稀疏且边跨度大，一次跳跃能跨越大量节点，大幅减少需要比较的点数。顶层并不存储更高质量数据，也不包含精确向量全集，与底层过滤能力无关。

Q10. 关于HNSW的构建流程，以下说法正确的是？

多选题 · easy

A.新节点需要从顶层开始搜索← 正确答案
B.建立的连接需要双向回指← 正确答案
C.每个节点只能属于一个层
D.插入顺序不影响最终图结构

答案：AB。插入新节点时从顶层入口搜索，逐层下探；建边时邻居也要回指新节点，保证双向导航。节点可以同时存在于多个层，且插入顺序会影响图拓扑，所以C和D错误。