刚来到一座陌生城市时，你想找一家藏在老巷里的咖啡馆。最笨的办法是从街角开始挨家挨户敲门询问，就像在千万个向量里逐个比对；聪明人则打开手机地图，先看整座城市的卫星图——只能看清几条主干道，锁定咖啡馆的大致区域；再放大到片区地图，辨认出几条主要路网；最后落到街区地图，在小巷里精确找到门牌。整个过程只需几分钟，而不是挨家挨户敲一整天。 HNSW（分层可导航小世界）索引，正是把这种“地图缩放”的智慧搬进了向量数据库。海量向量就像城市里数量爆炸的地标，距离计算就像走路的成本。HNSW 用一层又一层的“图版地图”组织向量：高层稀疏管全局，低层稠密管细节。查询时从宏观的高层开始，逐层放大，最后在最底层完成精查找，从而把“恨不得全城搜索”的暴力扫描，变成“点到点导航”的快速旅行。这正是向量数据库能做到毫秒级近邻检索的底层秘密。

岗位关联

掌握 HNSW 是理解向量数据库核心引擎的必经之路。无论你将来做 RAG 应用、推荐召回，还是数据库内核开发，这都是值得好好听的一堂“地图驾驶课”。

目录
  1. 可视化演示
  2. 暴力检索瓶颈
  3. 小世界图原理
  4. 多层图结构
  5. 搜索算法
  6. 插入与连接策略
  7. 参数调优
  8. 工程实现
  9. AI 应用场景
  10. Python 演示
  11. 常见误区
  12. 面试题

可视化演示

动态演示HNSW索引原理与向量数据库的核心机制，通过入门/进阶/实战/优化四种模式展示关键概念与交互流程。

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

HNSW索引原理与向量数据库：小世界图 小世界图拓扑与可导航性原理 分层跳表式导航与逐层搜索机制 核心机制可视化 HNSW索引原理与向量数据库整体架构与关键组件

暴力检索瓶颈

想象你第一次来到一座陌生城市，要找一家咖啡馆，却没有地图。最笨的办法是从街头第一间屋子开始，挨家挨户敲门问“咖啡馆在哪儿”。店铺少时这招管用；可当整座城市有上千万扇门，敲门的时间会直接失控。向量检索也面临同样的尴尬——数据量一大，简单枚举就不可行了。

对计算机而言，每个“地标”是一个高维向量。检索“与查询最像的地标”，本质是计算查询向量与所有向量的距离，再取距离最近的一批。这种朴素实现叫暴力扫描，也叫线性扫描，它不做任何预组织，把每个向量都算一遍。它虽然准确，但代价极高。

假设库里有 N 个向量，每个 D 维。一次查询要算 N 次距离，每次距离要遍历 D 个维度，于是总耗时 T 与 N×D 成正比。数据量达到千万级、维度达到百级时，单次查询就需要几十亿次浮点运算，延迟从毫秒级恶化到秒级。这就是高维检索的第一道坎：线性成本。

把“敲门”换成“算距离”，把“门牌号”换成“向量”，暴力检索就是一张没有地图的导航：每条街都走一遍才知道咖啡店在哪。要让向量数据库在海量数据下真正可用，必须先造出那张能“指方向”的地图。

Tbrute=O(N×D)T_{\text{brute}} = O(N \times D)
一句话解释：N 是向量条数，D 是向量维度，两者的乘积决定了暴力扫描的计算量。数据量或维度任意一方变大，耗时都线性恶化，这就是必须引入索引的根本原因。
  1. T 代表单次查询总耗时下标 brute 表示“暴力扫描”，整个等式想表达的意思是：不做任何索引时，一次查询的耗时随数据规模线性上升。
    TbruteT_{\text{brute}}
  2. N 是向量总条数库里的每条数据都要和查询向量算一次距离，所以计算次数至少是 N 的量级。
    NN
  3. D 是向量维度两个 D 维向量算距离，需要逐维度求差、平方、累加，维度越高，单次距离计算越贵。
    DD
  4. O(·) 表示复杂度趋势大 O 记号忽略常数系数，只关心“随规模增长的趋势”，这里两者相乘得到总计算量。
    O(N×D)O(N \times D)

小世界图原理

你听过“六度分隔”吗？世界上任意两个人，平均只需要经过五六层熟人关系就能建立联系。你认识的朋友也许只在同一个小区，但朋友的朋友，可能住在城市的另一端。这些“关键连接”让陌生人之间可以快速触达。

把每个向量看作一个“地标节点”，如果两个向量足够近（距离小），就画一条边把它们连起来，海量向量便被编织成一张可导航的邻近图。有了图，搜索就变成“接力跑”：从任意一个节点出发，每次都走向所有邻居里离目标最近的那个，直到逼近目标。这种策略叫贪婪导航。

仅仅连接“自己最近的几个邻居”，会让图变成无数个小团块，导航反而绕远。小世界图的精髓是存在少量长程连接——它们像社交网络里的“跨界朋友”，把相距遥远的区域直接牵在一起。加上这些跳板之后，图上两点间的平均跳跃次数可以从 O(√N) 量级压到 O(log N)。这正是 HNSW 毫秒级延迟的理论基石。

城市地图如果只把每条街画成网格，从一个小区到另一个小区要穿过很多路口；但有了高架、地铁这类“长程通道”，一两次换乘就能跨越大半个城市。长程连接，就是小世界图上最值钱的一张“地铁票”。

Tnav=O(log⁡N)T_{\text{nav}} = O(\log N)
一句话解释：导航步数只随数据量对数增长。数据扩大 100 倍，导航步数只增加很少几步，这就是“小世界”导航的威力。
  1. Tnav 是平均导航步数它表示从任意起点走到目标节点，沿途需要经过多少条边。
    TnavT_{\text{nav}}
  2. log N 来自长程连接有了跨区域跳板，每一步都可能跳过指数级更大的区域，所以步数从线性压到对数。
    log⁡N\log N
  3. O(·) 表示整体量级当数据量翻倍，导航步数只增加一个常数，这与暴力扫描的线性增长形成鲜明对比。
    O(log⁡N)O(\log N)

多层图结构

打开电子地图，你第一眼看到的是卫星图，街道寥寥；往下放大才出现主干道；再放大到街区，连巷口都一清二楚。如果一开始就把所有街道铺满屏幕，眼睛会瞬间失去方向。地图分层，是为了“先宏观定位，再微观找人”。

HNSW 也把一张巨大的邻近图拆成若干层。最高层只有少数“地标节点”和稀疏长程边，负责提供全局方向感；最低层包含全部节点和边，负责精确匹配。每个节点按概率决定自己被放入哪些层：被放入的层越高，说明它越是网络中的“核心枢纽”。

设概率 p 表示节点出现在相邻上一层的比例（通常取 0.5 左右），一个节点恰好出现在第 L 层的概率是 p 的 L 次方。这意味着高层节点数呈指数衰减，搜索时高层飞快、低层细致。这种“指数多层”的灵感直接来自跳表：跳表用多层链表把 O(N) 查找压到 O(log N)，HNSW 把它从链表推广到了更自由的图结构。

地图的“卫星图→街景”和 HNSW 的“高层→低层”异曲同工：高层负责告诉你“目标大概在那个方向”，低层负责“精确到门牌”。没有高层的指引，搜索从一开始就会在大街小巷里彻底迷失。

P(level=L)=pLP(\text{level}=L) = p^{L}
一句话解释：p 是相邻层之间的保留比例，层数越高，节点出现概率按指数快速下降，形成“下密上疏”的金字塔结构。
  1. P 表示节点出现在第 L 层的概率层越高，节点越少，出现概率越小，这正是高层能“总览全局”的原因。
    P(level=L)P(\text{level}=L)
  2. p 是相邻层保留比例p 越大，高层节点越多，整个图越高；p 越小，高层越稀疏，通常取 0.3~0.6。
    pp
  3. 指数次幂 p^L每升高一层，概率就再乘一次 p，于是形成指数衰减的尖塔结构。
    pLp^{L}

搜索算法

现在正式演示一次“地图导航”。你打开 App 找咖啡馆：卫星图锁定城市，放大后沿主干道向东走，再放大进老城区，最后在小巷里看到目标。每一次放大，视野更细，方向更正。

HNSW 搜索完全模拟这个过程。入口是最高层的某个节点，算法在每一层做两件事：先“贪婪前进”——不断走向当前节点所有邻居中离查询最近的那个；等无法再前进时，把当前落脚点记下来，作为下一层的入口，然后降层继续。这套流程叫逐层下降。

到了最底层，还需要一个容量为 ef 的候选窗口。每访问一个节点，就把它的邻居并入候选集，只保留与查询最近的 ef 条。用一个小顶堆维护“待访问”，用另一个堆维护“当前最优”，当待访问堆顶的距离已经超过当前最优堆中最差的那个，说明不可能再有惊喜，搜索终止并输出 top-k。ef 越大，候选窗口越宽，结果越接近暴力扫描，但比较次数也随之上升。

这就像导航地图的“进度条”：先宏观扫过去，规划主干道路线，再逐步放大，直到小巷。上层帮你避开低层的漫无目的，这就是分层搜索省时间的核心原因。

W←TopK⁡ef(W∪N(c))\mathcal{W} \leftarrow \operatorname{TopK}_{ef}\big(\mathcal{W} \cup \mathcal{N}(c)\big)
一句话解释：每次访问节点 c，都把自己的邻居 N(c) 并入候选集 W，然后只保留距离最近的 ef 个。这个“并入-截断”的循环，就是最底层精查找的心脏。
  1. W 是候选集合它像一个长度固定的窗口，只保存当前与查询最近的 ef 个候选，是“最优 ef 个”的滚动榜单。
    W\mathcal{W}
  2. N(c) 是当前节点的邻居每贪心访问一个新节点，就把它的所有邻居都拉进来“参选”。
    N(c)\mathcal{N}(c)
  3. 并集操作把原有候选和新邻居合并，不让任何潜在更优点被遗漏。
    W∪N(c)\mathcal{W} \cup \mathcal{N}(c)
  4. TopK 截断按距离排序之后只留下最近的 ef 个，保证候选窗口规模恒定、计算量可控。
    TopK⁡ef(⋅)\operatorname{TopK}_{ef}(\cdot)

插入与连接策略

城市里新开一家咖啡馆，怎么把它加进地图？测绘员会先在卫星图上找到它属于哪个片区，再在片区地图上确定附近街道，最后让新馆子和周围几家老店建立“相互指引”的关系。

插入新向量的流程和这几乎一样。先用类似搜索的流程逐层定位，找到新节点附近的老节点；然后在新节点出现的每一层，挑选 M 个最近邻居，为双方建立双向边，写入对方的邻居表。整个过程可以拆成三步：随机分配层号、逐层找地基、逐层连路网。

选“M 个最近邻居”时不能只盯距离。如果只连距离最近的 M 个，城市里的节点会挤成一个个马蜂窝，导航反而绕远。真实 HNSW 使用启发式挑选规则：先取距离最近的一个，再从候选里依次挑“离已有邻居集合最远”的节点补足 M 个。这样连接既有向心性，又有发散性，图既连通又便于导航。

新店开张，不仅要认识紧挨着的便利店，还要认识几条街外的大型商场，这样顾客无论从哪个方向来，都能顺着路网找到它。M 就是“交朋友的上限”——朋友交得多，信息全但维护成本高；交得少，圈子小但导航绕远。

N(v)=arg⁡min⁡∣S∣≤M∑u∈Sd(v,u)\mathcal{N}(v) = \arg\min_{|S| \le M} \sum_{u \in S} d(v, u)
一句话解释：这是“照距离选邻居”的简化写法：在所有不超过 M 个节点的子集中，选总距离最小的一组作为邻居。工程实现还会引入多样性启发式，避免邻居扎堆。
  1. N(v) 是最终邻居集合这是新节点 v 在某层选出来的邻居，将用于双向连线。
    N(v)\mathcal{N}(v)
  2. arg min 表示寻找最优组合在候选节点集合中，穷举或近似搜索一个“总距离最小”的组合。
    arg⁡min⁡∣S∣≤M\arg\min_{|S| \le M}
  3. 求和式度量“近”选出的 M 个邻居与 v 的距离之和越小，说明该层局部连接越紧凑。
    ∑u∈Sd(v,u)\sum_{u \in S} d(v,u)

参数调优

地图的精细度是一把双刃剑。分辨率提高，看得越清，但加载越慢，纸张也越厚。导航工具的“精度”和“速度”永远在打架。

HNSW 的使用者手里有三个旋钮。M 控制每个节点的“朋友上限”，决定图的密度；efConstruction 控制建索引时每层候选窗口的宽窄，相当于修路时预留多少备选路段；efSearch 控制查询时最底层候选窗口，相当于导航时多留几条绕行备选路线。

M 大，图更密，导航步数下降，但内存和构建时间线性上升；efSearch 大，召回率明显提升，但每次查询的比较次数变多。实践中常用组合是 M=16、efConstruction=100、efSearch=50~200，可以达到 95%~99% 的召回率，同时把延迟维持在毫秒级。值得注意的是，efSearch 只影响查询，不影响索引构建，因此线上可以动态调大来应急提召回。

导航软件会让你选“更优路线”还是“更快路线”，HNSW 的调参也是同样的权衡：想要召回率更高，就把候选窗口开大；想要省内存，就收紧 M。调参的本质，是找到属于自己数据规模和延迟预算的平衡点。

Tquery≈O(log⁡N⋅Mavg)T_{\text{query}} \approx O(\log N \cdot M_{\text{avg}})
一句话解释：查询总开销约等于“层数 × 每层平均访问邻居数”。M 决定后者，所以 M 是查询延迟和内存占用的主要杠杆。
  1. Tquery 是单次查询耗时它是层数成本与每层邻居比较成本的乘积呈现。
    TqueryT_{\text{query}}
  2. log N 是层数成本从最高层降到最低层大约要走对数级层数。
    log⁡N\log N
  3. Mavg 是平均邻居数每一层贪婪比较时都要扫一遍当前节点的邻居，平均邻居数决定单层成本。
    MavgM_{\text{avg}}

工程实现

把地图印成册子还要考虑三件事：纸张厚度（内存）、旧路翻新（增删改）、同时被多人查阅（并发）。一个真正能落地的向量数据库，必须把这些“细节账”算清楚。

HNSW 从论文走向生产，还要翻越三座大山：内存布局、删除更新、并发安全。

第一，内存布局：HNSW 是纯内存索引，每个节点要存向量本身、层号和每层邻居指针。邻居指针一般 8 字节，所以占用约等于“节点数 × 平均度 × 8 字节”。生产实现常使用 Arena 内存池复用内存，减少碎片。第二，删除更新：直接删节点会撕裂图的连通性，生产级实现普遍用“墓碑”标记延迟删除，再在后台压缩层内连接关系，甚至重建局部子图。第三，并发安全：索引同时被多个查询线程读，插入线程还要改边，常见方案是无锁读加单写者，或用版本号做快照隔离，让读线程永远看不到半更新状态。

地图册越印越厚会放不下书架，老路改建不及时会让导航绕远，多人同时翻同一页还会扯坏书页。工程上每解决一个问题，HNSW 就从“论文玩具”向着“生产系统”迈进一大步。

Mem≈N×Mavg×8 B\text{Mem} \approx N \times M_{\text{avg}} \times 8 \, \text{B}
一句话解释：索引内存约等于“节点数 × 平均邻居数 × 每个邻居指针 8 字节”。这也是为什么 M 不能无限调大——每条边都是要付内存租金的。
  1. Mem 表示索引总内存估算的是把整张多层图放进内存所需的空间。
    Mem\text{Mem}
  2. N 个节点各存一份每个向量都要作为节点保存，节点数越多，基础内存越大。
    NN
  3. 平均度乘 8 字节每个邻居指针用 64 位（8 字节）存储，平均 M 个邻居就是 M 倍指针开销。
    Mavg×8BM_{\text{avg}} \times 8\text{B}

AI 应用场景

RAG 知识库语义召回

阶段：检索增强生成（RAG）的召回阶段

解决的问题：RAG 需要从百万级文档片段中取回与问题最相关的 top-k 内容。暴力扫描延迟太高，关键词倒排又丢失语义信息。HNSW 索引把问题向量与文档向量的最近邻搜索压缩到毫秒级，让大模型在生成前能“读”到真正相关的材料。

具体案例：某企业客服机器人接入 500 万条 FAQ 片段，每条用 Embedding 模型编码成 768 维向量并写入 HNSW 索引。用户提问后，系统在约 15ms 内召回 top-20 候选片段，交给大模型汇总答案，整体响应从原来的 2 秒降到 300ms。

向量数据库索引内核

阶段：索引构建与查询执行

解决的问题：生产级向量数据库（如 Milvus、Qdrant）需要把 HNSW 变成可靠的索引内核，包括内存池分配、删除墓碑、并发读写控制、多副本一致性。直接用论文原版代码无法支撑真实业务，必须做大量工程加固。

具体案例：某向量数据库团队用 C++ 实现 HNSW，在底层引入 Arena 内存分配器，将千万级 128 维向量的索引内存占用压缩 30%；删除采用墓碑标记加后台压缩，避免图连通性劣化；查询使用无锁读，插入使用单写者，支撑了每秒上万次混合读写。

推荐系统召回

阶段：推荐系统召回阶段（候选集生成）

解决的问题：推荐场景中，用户向量要与数百万商品向量逐一算相似度，逐对计算不现实。HNSW 在牺牲极小召回率的前提下，把候选集从全量压缩到数百个，让精排模型可以集中算力做细致打分。

具体案例：某短视频推荐系统每晚用增量任务把 500 万内容向量建入 HNSW 索引，在线实时用用户行为向量做查询，8ms 内取回 300 个候选，再输入深度学习精排模型，综合点击率提升 11%。

Python 演示

python90 行
import math, random, heapqimport numpy as np MAX_LEVEL = 8 def dist(a, b):    return float(np.linalg.norm(a - b)) class Node:    def __init__(self, vec, level):        self.vec = np.array(vec, dtype=float)        self.level = level        self.links = [[] for _ in range(MAX_LEVEL + 1)] class HNSW:    """teaching HNSW: layered graph, greedy search, bidirectional link"""     def __init__(self, M=6, ef=16, decay=0.6):        self.M = M        self.ef = ef        self.decay = decay        self.nodes = []        self.g_level = 0     def _rand_level(self):        return int(-math.log(random.random()) * self.decay)     def _search_layer(self, q, layer, k, entry=None):        entry = entry or self.nodes[0]        seen = {id(entry)}        frontier = [(dist(q, entry.vec), entry)]        topk = [(-dist(q, entry.vec), entry)]        while frontier:            d, cur = heapq.heappop(frontier)            if d > -topk[0][0] and len(topk) == k:                break            for nb in cur.links[layer]:                if id(nb) in seen:                    continue                seen.add(id(nb))                dd = dist(q, nb.vec)                if len(topk) < k or dd < -topk[0][0]:                    heapq.heappush(frontier, (dd, nb))                    heapq.heappush(topk, (-dd, nb))                    if len(topk) > k:                        heapq.heappop(topk)        return [n for _, n in topk]     def insert(self, vec):        node = Node(vec, self._rand_level())        if not self.nodes:            self.nodes.append(node)            self.g_level = node.level            return        self.nodes.append(node)        entry = self.nodes[0]        for layer in range(self.g_level, min(node.level, self.g_level) - 1, -1):            best = self._search_layer(vec, layer, 1, entry)            if best:                entry = best[0]        for layer in range(min(node.level, self.g_level), -1, -1):            nbrs = self._search_layer(vec, layer, self.M, entry)            node.links[layer] = nbrs            for nb in nbrs:                nb.links[layer].append(node)                if len(nb.links[layer]) > self.M:                    nb.links[layer] = sorted(                        nb.links[layer], key=lambda x: dist(x.vec, node.vec))[:self.M]        self.g_level = max(self.g_level, node.level)     def search(self, q, k=5):        if not self.nodes:            return []        entry = self.nodes[0]        res = []        for layer in range(self.g_level, -1, -1):            res = self._search_layer(q, layer, k if layer == 0 else 1, entry)            if res:                entry = res[0]        return res if __name__ == "__main__":    random.seed(42)    index = HNSW(M=6, ef=16)    items = [[random.gauss(0, 1) for _ in range(4)] for _ in range(20)]    for v in items:        index.insert(v)    ans = index.search(items[0], 5)    for node in ans:        print(round(dist(items[0], node.vec), 4))
目的：这是一个教学版 HNSW，完整演示了“随机分配层号、分层搜索、每层选 M 邻居双向连接”三个核心步骤。运行后可以看到查询向量返回的 5 个最近邻距离。
  1. class HNSW:定义分层可导航小世界索引类，核心数据结构。
  2. self.links = [[] for _ in range(MAX_LEVEL + 1)]每个节点为所有层预先准备邻居列表，避免访问高层时报错。
  3. entry = entry or self.nodes[0]如果没有指定入口，从全局首个节点开始导航。
  4. if d > -topk[0][0] and len(topk) == k:若待探索的最近距离已超过当前最优集合中最远距离，提前终止搜索。
  5. node.links[layer] = nbrs把该层选出的邻居写入新节点的邻居表。
  6. nb.links[layer].append(node)在既有节点的邻居表中反向加入新节点，实现双向连接。
  7. if len(nb.links[layer]) > self.M:反向更新时邻居数超过 M，触发修剪。
  8. res = self._search_layer(q, layer, k if layer == 0 else 1, entry)最底层返回 k 个结果，中间层只取 1 个接力点。

常见误区

误区以为用了 HNSW 后，返回的一定是全局最近邻，和暴力扫描结果完全一致。做测试时发现偶尔不一致，还以为是程序有 bug。

正解HNSW 是近似最近邻（ANN）算法。它通过分层、贪心和剪枝大幅减少访问节点数，可能漏掉全局最优。召回率通常在 90%~99% 之间，不是 100%。如果业务必须精确，只能暴力扫描，或者把 efSearch 调到极大值来逼近暴力结果。

为何常见：多数演示数据量小、分布均匀，HNSW 恰好全部命中，让人误以为它是精确算法。

误区连接越多，导航可走的路越多，召回率肯定越高，于是把 M 调到 64、128，结果内存爆了，查询反而变慢。

正解M 过大会让内存线性膨胀、插入成本暴涨；而且过密的图会让贪心选择在局部绕圈，召回率提升十分有限。通常 M 在 8~32 之间就有很好的性价比，核心原则是“够用就好”。

为何常见：直观上觉得“路多=走得快”，忽略了图密度增加后维护和比较的成本。

误区把节点从图和邻居表里移除，再更新相关指针，不就行了吗？链表删除的经验让人想当然。

正解直接删除会破坏小世界图的连通性，周边节点再也无法通过这个枢纽到达远处，后续查询可能断崖式失败。生产级实现用墓碑标记延迟删除，之后在后台压缩或局部重建连接。

为何常见：经典数据结构课上的“删除节点”经验过于深入人心，没意识到图结构对连通性的高度依赖。

误区HNSW 叫最近邻索引，连边时自然应该把最近的 M 个点全连上，这样最准。

正解全连最近点会导致邻居“扎堆”成一团，跨区域长程边不足，导航步数反而飙升。HNSW 会使用多样性启发式：先取最近点，再逐步挑选离已有集合较远的点，保证局部近邻和全局可达性都兼顾。

为何常见：把“检索结果要最近”和“构图连边要最近”混为一谈，混淆了目的和手段。

误区所有索引参数都应该在建索引时定好，efSearch 改了之后，不重建索引就不会生效。

正解efSearch 是纯查询参数，只影响搜索时底层候选窗口大小，不需要重建索引，运行时可以随时调大调小。真正需要重建的是 efConstruction，因为它在构建阶段决定候选质量。

为何常见：对“构建参数”和“查询参数”的边界不清楚，把所有参数都当作“建索引时一次性定死”的配置。

面试题

Q1. HNSW 出现之前，向量检索常用暴力扫描，它的单次查询耗时与什么有关？

单选题 · easy

  • A.与向量总数成正比增加← 正确答案
  • B.与向量总数成反比下降
  • C.与向量总数完全无关
  • D.与向量总数成平方增长

答案：A。暴力扫描要对每个向量都算一次距离，N 个向量就做 N 次，所以耗时与向量总数成正比。它既不是反比，也不是平方，更不可能无关。这也是为什么数据量一大，暴力扫描就撑不住。

Q2. 小世界图能把图导航步数从什么量级降下来？

单选题 · mid

  • A.线性级别降低到平方级别
  • B.线性级别降低到对数级别← 正确答案
  • C.对数级别降低到常数级别
  • D.平方级别降低到立方级别

答案：B。小世界图依靠长程连接，让每一步都能跨越很大区域，把平均导航步数从 O(N) 压到 O(log N)。对数增长意味着数据翻倍只增加常数步，这是 HNSW 快于暴力扫描的关键。

Q3. HNSW 中一个节点出现在第 L 层的概率是？

单选题 · mid

  • A.第 L 层概率为均匀分布
  • B.第 L 层概率为平方放大
  • C.第 L 层概率按 p^L 衰减← 正确答案
  • D.第 L 层概率为常数不变

答案：C。层级分配采用指数衰减，某个节点出现在第 L 层的概率是 p^L，其中 p 是相邻层保留比例。因此层越高节点越少，高层才能保持稀疏、快速导航。

Q4. HNSW 搜索过程中，在非最底层的主要任务是？

单选题 · mid

  • A.遍历该层所有节点再选优
  • B.贪心走向更近的邻居节点← 正确答案
  • C.随机选一个邻居跳过去
  • D.反向连接所有已访问点

答案：B。每一层都用贪心策略：从当前节点出发，走向所有邻居中离查询最近的那个，直到局部最优，再携带这个落脚点下降到下一层。随机跳跃和全层遍历都不是 HNSW 的做法。

Q5. 关于 HNSW 的 M 参数，以下哪些说法正确？

多选题 · mid

  • A.M 决定每层最多邻居数← 正确答案
  • B.M 过大内存占用上升← 正确答案
  • C.M 太小图导航变慢← 正确答案
  • D.M 只影响插入不影响查询

答案：ABC。M 是每层邻居数量上限，直接影响内存和查询延迟，因此 A、B 正确；M 过小会缺少跳板，导航绕路，C 也正确；M 同时影响插入和查询，D 错误。

Q6. 关于 efSearch 参数，下列说法正确的是？

多选题 · hard

  • A.只在查询阶段发生作用← 正确答案
  • B.只在构建索引阶段生效
  • C.数值越大召回率越高← 正确答案
  • D.数值越小查询延迟越低← 正确答案

答案：ACD。efSearch 是查询时底层候选窗口的大小，不影响构建，所以 A 正确、B 错误。窗口越大，保留的候选越多，召回率越高但比较次数也变多，因此 C、D 正确。

Q7. 向量数据库删除 HNSW 中的节点时，工程上常用哪些手段？

多选题 · mid

  • A.直接物理删除该节点
  • B.用墓碑标记延迟删除← 正确答案
  • C.后台压缩重建连接关系← 正确答案
  • D.永久锁定所有相关层

答案：BC。直接物理删除会破坏图连通性，所以用墓碑标记延迟删除，再在后台压缩或局部重建连接，B、C 正确。直接删除和锁定相关层都不是合理做法。

Q8. HNSW 查询导航的起点通常在哪里？

单选题 · easy

  • A.最底层的任一随机节点
  • B.最高层图的入口节点← 正确答案
  • C.更新最多的热点节点
  • D.距离查询最远的节点

答案：B。搜索从最高层的入口节点开始，因为高层节点稀疏，能快速确定全局方向，再逐层下降精确查找。从底层随机开始等于放弃分层优势。

Q9. 线上查询发现召回率不足，最先应该调整哪个参数？

单选题 · hard

  • A.将 efSearch 调大← 正确答案
  • B.将 efSearch 调小
  • C.将 decay 参数降为零
  • D.将 M 参数直接清零

答案：A。efSearch 是查询参数，运行时即可调大，能立刻提升召回率。efConstruction 需要重建索引，M 不能清零，decay 降零更是破坏层级结构。所以先调 efSearch。

Q10. 关于 HNSW 的分层导航机制，叙述正确的是？

多选题 · extreme

  • A.顶层结果指引低层方向← 正确答案
  • B.底层承担最终精度排序← 正确答案
  • C.每层都维持候选集窗口← 正确答案
  • D.高层候选集必须大于底层

答案：ABC。高层找到的落脚点是低层的入口，相当于大方向指引，A 正确；最底层用 ef 候选窗口做精排序，B 正确；每层都有候选集，只是容量不同，C 正确；高层通常只保留 1 个接力点，反而比底层小，D 错误。