从街道到高速公路-HNSW分层近邻搜索原理与工程实践

目录

1. 背景与动机

1.1 问题定义

给定一个包含 N 个 d 维向量的数据集

D

=

{

x

1

,

x

2

,

…

,

x

N

}

D = \\{x_1, x_2, \\ldots, x_N\\}

D={x1​,x2​,…,xN​}，以及一个查询向量

q

q

q，精确最近邻搜索的目标是：

x

∗

=

arg

⁡

min

⁡

x

i

∈

D

∥

q

−

x

i

∥

x^* = \\arg\\min_{x_i \\in D} \\|q – x_i\\|

x∗=argxi​∈Dmin​∥q−xi​∥

当 N 达到百万甚至亿级别，且维度 d 较高（如 128~1024）时，暴力搜索需要计算 N 次距离，耗时无法满足在线服务需求（通常要求 < 10ms）。

1.2 为什么需要近似而非精确？

在实际应用中（推荐系统、语义搜索、图像检索），用户对"第 3 名和第 4 名顺序互换"并不敏感，但对"等待时间从 5ms 变成 500ms"非常敏感。因此，允许 1%~5% 的精度损失，换取 100~1000 倍的速度提升，是合理的工程取舍。

1.3 已有方法的局限

NSW（Navigable Small World） 在低层表现优异，但存在两个核心问题：

HNSW 通过引入分层结构解决了这两个问题。

2. 前置知识：小世界网络（Navigable Small World）

2.1 什么是小世界网络

"小世界"概念来自社会网络：地球上任意两个人之间，平均只需约 6 个中间人即可建立联系（六度分隔理论）。

在图论中，一个可导航的小世界网络具有以下特征：

• 大部分边是短程边（连接空间上相近的节点）
• 少量长程边（连接空间上远离的节点）
• 从任意节点出发，通过贪心策略（每步走向离目标更近的邻居）可以在 $O(\log N)$

#mermaid-svg-pJ9uTXHUlzbx1a0h{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-pJ9uTXHUlzbx1a0h .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-pJ9uTXHUlzbx1a0h .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-pJ9uTXHUlzbx1a0h .error-icon{fill:#552222;}#mermaid-svg-pJ9uTXHUlzbx1a0h .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-pJ9uTXHUlzbx1a0h .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-pJ9uTXHUlzbx1a0h .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-pJ9uTXHUlzbx1a0h .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-pJ9uTXHUlzbx1a0h .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-pJ9uTXHUlzbx1a0h .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-pJ9uTXHUlzbx1a0h .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-pJ9uTXHUlzbx1a0h .marker{fill:#333333;stroke:#333333;}#mermaid-svg-pJ9uTXHUlzbx1a0h .marker.cross{stroke:#333333;}#mermaid-svg-pJ9uTXHUlzbx1a0h svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-pJ9uTXHUlzbx1a0h p{margin:0;}#mermaid-svg-pJ9uTXHUlzbx1a0h .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-pJ9uTXHUlzbx1a0h .cluster-label text{fill:#333;}#mermaid-svg-pJ9uTXHUlzbx1a0h .cluster-label span{color:#333;}#mermaid-svg-pJ9uTXHUlzbx1a0h .cluster-label span p{background-color:transparent;}#mermaid-svg-pJ9uTXHUlzbx1a0h .label text,#mermaid-svg-pJ9uTXHUlzbx1a0h span{fill:#333;color:#333;}#mermaid-svg-pJ9uTXHUlzbx1a0h .node rect,#mermaid-svg-pJ9uTXHUlzbx1a0h .node circle,#mermaid-svg-pJ9uTXHUlzbx1a0h .node ellipse,#mermaid-svg-pJ9uTXHUlzbx1a0h .node polygon,#mermaid-svg-pJ9uTXHUlzbx1a0h .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-pJ9uTXHUlzbx1a0h .rough-node .label text,#mermaid-svg-pJ9uTXHUlzbx1a0h .node .label text,#mermaid-svg-pJ9uTXHUlzbx1a0h .image-shape .label,#mermaid-svg-pJ9uTXHUlzbx1a0h .icon-shape .label{text-anchor:middle;}#mermaid-svg-pJ9uTXHUlzbx1a0h .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-pJ9uTXHUlzbx1a0h .rough-node .label,#mermaid-svg-pJ9uTXHUlzbx1a0h .node .label,#mermaid-svg-pJ9uTXHUlzbx1a0h .image-shape .label,#mermaid-svg-pJ9uTXHUlzbx1a0h .icon-shape .label{text-align:center;}#mermaid-svg-pJ9uTXHUlzbx1a0h .node.clickable{cursor:pointer;}#mermaid-svg-pJ9uTXHUlzbx1a0h .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-pJ9uTXHUlzbx1a0h .arrowheadPath{fill:#333333;}#mermaid-svg-pJ9uTXHUlzbx1a0h .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-pJ9uTXHUlzbx1a0h .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-pJ9uTXHUlzbx1a0h .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-pJ9uTXHUlzbx1a0h .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-pJ9uTXHUlzbx1a0h .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-pJ9uTXHUlzbx1a0h .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-pJ9uTXHUlzbx1a0h .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-pJ9uTXHUlzbx1a0h .cluster text{fill:#333;}#mermaid-svg-pJ9uTXHUlzbx1a0h .cluster span{color:#333;}#mermaid-svg-pJ9uTXHUlzbx1a0h div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-pJ9uTXHUlzbx1a0h .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-pJ9uTXHUlzbx1a0h rect.text{fill:none;stroke-width:0;}#mermaid-svg-pJ9uTXHUlzbx1a0h .icon-shape,#mermaid-svg-pJ9uTXHUlzbx1a0h .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-pJ9uTXHUlzbx1a0h .icon-shape p,#mermaid-svg-pJ9uTXHUlzbx1a0h .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-pJ9uTXHUlzbx1a0h .icon-shape .label rect,#mermaid-svg-pJ9uTXHUlzbx1a0h .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-pJ9uTXHUlzbx1a0h .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-pJ9uTXHUlzbx1a0h .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-pJ9uTXHUlzbx1a0h :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

入口节点

节点2

节点3

节点4

节点5

目标节点

小世界网络中的贪心搜索路径：入口节点（蓝色）出发，每步选择离目标（红色）最近的邻居前进，最终收敛到目标节点。

2.2 Delaunay 图与 NSW

理想的近邻图是 Delaunay 图——每个节点的邻居是其在 Voronoi 单元中相邻的所有节点。Delaunay 图保证贪心搜索一定能找到全局最近邻，但构建复杂度为

O

(

N

⌈

d

/

2

⌉

)

O(N^{\\lceil d/2 \\rceil})

O(N⌈d/2⌉)，在高维下完全不可行。

NSW 是 Delaunay 图的近似：通过随机插入节点并连接其近邻，逐步构建一个"足够好"的图，使贪心搜索大概率能找到最近邻。

2.3 NSW 的搜索过程

#mermaid-svg-WjHyCaCJ1MzhXCyP{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-WjHyCaCJ1MzhXCyP .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-WjHyCaCJ1MzhXCyP .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-WjHyCaCJ1MzhXCyP .error-icon{fill:#552222;}#mermaid-svg-WjHyCaCJ1MzhXCyP .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-WjHyCaCJ1MzhXCyP .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-WjHyCaCJ1MzhXCyP .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-WjHyCaCJ1MzhXCyP .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-WjHyCaCJ1MzhXCyP .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-WjHyCaCJ1MzhXCyP .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-WjHyCaCJ1MzhXCyP .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-WjHyCaCJ1MzhXCyP .marker{fill:#333333;stroke:#333333;}#mermaid-svg-WjHyCaCJ1MzhXCyP .marker.cross{stroke:#333333;}#mermaid-svg-WjHyCaCJ1MzhXCyP svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-WjHyCaCJ1MzhXCyP p{margin:0;}#mermaid-svg-WjHyCaCJ1MzhXCyP .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-WjHyCaCJ1MzhXCyP .cluster-label text{fill:#333;}#mermaid-svg-WjHyCaCJ1MzhXCyP .cluster-label span{color:#333;}#mermaid-svg-WjHyCaCJ1MzhXCyP .cluster-label span p{background-color:transparent;}#mermaid-svg-WjHyCaCJ1MzhXCyP .label text,#mermaid-svg-WjHyCaCJ1MzhXCyP span{fill:#333;color:#333;}#mermaid-svg-WjHyCaCJ1MzhXCyP .node rect,#mermaid-svg-WjHyCaCJ1MzhXCyP .node circle,#mermaid-svg-WjHyCaCJ1MzhXCyP .node ellipse,#mermaid-svg-WjHyCaCJ1MzhXCyP .node polygon,#mermaid-svg-WjHyCaCJ1MzhXCyP .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-WjHyCaCJ1MzhXCyP .rough-node .label text,#mermaid-svg-WjHyCaCJ1MzhXCyP .node .label text,#mermaid-svg-WjHyCaCJ1MzhXCyP .image-shape .label,#mermaid-svg-WjHyCaCJ1MzhXCyP .icon-shape .label{text-anchor:middle;}#mermaid-svg-WjHyCaCJ1MzhXCyP .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-WjHyCaCJ1MzhXCyP .rough-node .label,#mermaid-svg-WjHyCaCJ1MzhXCyP .node .label,#mermaid-svg-WjHyCaCJ1MzhXCyP .image-shape .label,#mermaid-svg-WjHyCaCJ1MzhXCyP .icon-shape .label{text-align:center;}#mermaid-svg-WjHyCaCJ1MzhXCyP .node.clickable{cursor:pointer;}#mermaid-svg-WjHyCaCJ1MzhXCyP .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-WjHyCaCJ1MzhXCyP .arrowheadPath{fill:#333333;}#mermaid-svg-WjHyCaCJ1MzhXCyP .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-WjHyCaCJ1MzhXCyP .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-WjHyCaCJ1MzhXCyP .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-WjHyCaCJ1MzhXCyP .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-WjHyCaCJ1MzhXCyP .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-WjHyCaCJ1MzhXCyP .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-WjHyCaCJ1MzhXCyP .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-WjHyCaCJ1MzhXCyP .cluster text{fill:#333;}#mermaid-svg-WjHyCaCJ1MzhXCyP .cluster span{color:#333;}#mermaid-svg-WjHyCaCJ1MzhXCyP div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-WjHyCaCJ1MzhXCyP .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-WjHyCaCJ1MzhXCyP rect.text{fill:none;stroke-width:0;}#mermaid-svg-WjHyCaCJ1MzhXCyP .icon-shape,#mermaid-svg-WjHyCaCJ1MzhXCyP .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-WjHyCaCJ1MzhXCyP .icon-shape p,#mermaid-svg-WjHyCaCJ1MzhXCyP .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-WjHyCaCJ1MzhXCyP .icon-shape .label rect,#mermaid-svg-WjHyCaCJ1MzhXCyP .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-WjHyCaCJ1MzhXCyP .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-WjHyCaCJ1MzhXCyP .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-WjHyCaCJ1MzhXCyP :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

节点1

节点2

节点3

节点4

节点5

节点6

节点7

节点8

查询点 q

NSW 单层搜索示意：边代表近邻连接，红色节点为查询点 q，搜索从入口点出发，每步移向离 q 最近的邻居，直到局部最优。

NSW 的问题：入口点可能在图的"边缘"，搜索初期需要经过大量节点才能进入"主干"，这部分步数占总搜索步数的很大比例。

3. HNSW 核心设计：分层结构

3.1 灵感来源：跳表（Skip List）

HNSW 的分层设计直接借鉴了跳表（Skip List）数据结构。跳表通过在链表上叠加多层"快速通道"，使搜索复杂度从 O(N) 降至 O(log N)。

#mermaid-svg-iiWDiGvibYgZJOj4{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-iiWDiGvibYgZJOj4 .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-iiWDiGvibYgZJOj4 .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-iiWDiGvibYgZJOj4 .error-icon{fill:#552222;}#mermaid-svg-iiWDiGvibYgZJOj4 .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-iiWDiGvibYgZJOj4 .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-iiWDiGvibYgZJOj4 .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-iiWDiGvibYgZJOj4 .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-iiWDiGvibYgZJOj4 .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-iiWDiGvibYgZJOj4 .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-iiWDiGvibYgZJOj4 .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-iiWDiGvibYgZJOj4 .marker{fill:#333333;stroke:#333333;}#mermaid-svg-iiWDiGvibYgZJOj4 .marker.cross{stroke:#333333;}#mermaid-svg-iiWDiGvibYgZJOj4 svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-iiWDiGvibYgZJOj4 p{margin:0;}#mermaid-svg-iiWDiGvibYgZJOj4 .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-iiWDiGvibYgZJOj4 .cluster-label text{fill:#333;}#mermaid-svg-iiWDiGvibYgZJOj4 .cluster-label span{color:#333;}#mermaid-svg-iiWDiGvibYgZJOj4 .cluster-label span p{background-color:transparent;}#mermaid-svg-iiWDiGvibYgZJOj4 .label text,#mermaid-svg-iiWDiGvibYgZJOj4 span{fill:#333;color:#333;}#mermaid-svg-iiWDiGvibYgZJOj4 .node rect,#mermaid-svg-iiWDiGvibYgZJOj4 .node circle,#mermaid-svg-iiWDiGvibYgZJOj4 .node ellipse,#mermaid-svg-iiWDiGvibYgZJOj4 .node polygon,#mermaid-svg-iiWDiGvibYgZJOj4 .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-iiWDiGvibYgZJOj4 .rough-node .label text,#mermaid-svg-iiWDiGvibYgZJOj4 .node .label text,#mermaid-svg-iiWDiGvibYgZJOj4 .image-shape .label,#mermaid-svg-iiWDiGvibYgZJOj4 .icon-shape .label{text-anchor:middle;}#mermaid-svg-iiWDiGvibYgZJOj4 .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-iiWDiGvibYgZJOj4 .rough-node .label,#mermaid-svg-iiWDiGvibYgZJOj4 .node .label,#mermaid-svg-iiWDiGvibYgZJOj4 .image-shape .label,#mermaid-svg-iiWDiGvibYgZJOj4 .icon-shape .label{text-align:center;}#mermaid-svg-iiWDiGvibYgZJOj4 .node.clickable{cursor:pointer;}#mermaid-svg-iiWDiGvibYgZJOj4 .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-iiWDiGvibYgZJOj4 .arrowheadPath{fill:#333333;}#mermaid-svg-iiWDiGvibYgZJOj4 .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-iiWDiGvibYgZJOj4 .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-iiWDiGvibYgZJOj4 .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-iiWDiGvibYgZJOj4 .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-iiWDiGvibYgZJOj4 .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-iiWDiGvibYgZJOj4 .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-iiWDiGvibYgZJOj4 .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-iiWDiGvibYgZJOj4 .cluster text{fill:#333;}#mermaid-svg-iiWDiGvibYgZJOj4 .cluster span{color:#333;}#mermaid-svg-iiWDiGvibYgZJOj4 div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-iiWDiGvibYgZJOj4 .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-iiWDiGvibYgZJOj4 rect.text{fill:none;stroke-width:0;}#mermaid-svg-iiWDiGvibYgZJOj4 .icon-shape,#mermaid-svg-iiWDiGvibYgZJOj4 .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-iiWDiGvibYgZJOj4 .icon-shape p,#mermaid-svg-iiWDiGvibYgZJOj4 .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-iiWDiGvibYgZJOj4 .icon-shape .label rect,#mermaid-svg-iiWDiGvibYgZJOj4 .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-iiWDiGvibYgZJOj4 .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-iiWDiGvibYgZJOj4 .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-iiWDiGvibYgZJOj4 :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

第 0层（底层）

1

2

3

4

5

6

7

8

9

第 1层

1

4

7

9

第 2层（顶层）

1

9

跳表示例：搜索目标值 5。从顶层逐层下降——第 2 层 1→9（9 超过 5，下降），第 1 层 1→4→7（7 超过 5，下降），第 0 层 4→5（命中目标，绿色节点）。

HNSW 将这个思想从一维有序链表推广到了高维向量空间。

3.2 分层结构

HNSW 构建一个 L+1 层的多层图（从第 0 层到第 L 层）：

• 第 0 层：包含所有 N 个节点，边最密集，是"底层公路网"
• 第 1 层：包含约 N/M 个节点，边较稀疏，是"省级公路"
• 第 2 层：包含约 N/M² 个节点，边更稀疏，是"高速公路"
• 第 L 层：通常只包含 1~2 个节点，是"顶层入口"

#mermaid-svg-M0o8aY4ihXh2g87Z{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-M0o8aY4ihXh2g87Z .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-M0o8aY4ihXh2g87Z .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-M0o8aY4ihXh2g87Z .error-icon{fill:#552222;}#mermaid-svg-M0o8aY4ihXh2g87Z .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-M0o8aY4ihXh2g87Z .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-M0o8aY4ihXh2g87Z .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-M0o8aY4ihXh2g87Z .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-M0o8aY4ihXh2g87Z .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-M0o8aY4ihXh2g87Z .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-M0o8aY4ihXh2g87Z .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-M0o8aY4ihXh2g87Z .marker{fill:#333333;stroke:#333333;}#mermaid-svg-M0o8aY4ihXh2g87Z .marker.cross{stroke:#333333;}#mermaid-svg-M0o8aY4ihXh2g87Z svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-M0o8aY4ihXh2g87Z p{margin:0;}#mermaid-svg-M0o8aY4ihXh2g87Z .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-M0o8aY4ihXh2g87Z .cluster-label text{fill:#333;}#mermaid-svg-M0o8aY4ihXh2g87Z .cluster-label span{color:#333;}#mermaid-svg-M0o8aY4ihXh2g87Z .cluster-label span p{background-color:transparent;}#mermaid-svg-M0o8aY4ihXh2g87Z .label text,#mermaid-svg-M0o8aY4ihXh2g87Z span{fill:#333;color:#333;}#mermaid-svg-M0o8aY4ihXh2g87Z .node rect,#mermaid-svg-M0o8aY4ihXh2g87Z .node circle,#mermaid-svg-M0o8aY4ihXh2g87Z .node ellipse,#mermaid-svg-M0o8aY4ihXh2g87Z .node polygon,#mermaid-svg-M0o8aY4ihXh2g87Z .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-M0o8aY4ihXh2g87Z .rough-node .label text,#mermaid-svg-M0o8aY4ihXh2g87Z .node .label text,#mermaid-svg-M0o8aY4ihXh2g87Z .image-shape .label,#mermaid-svg-M0o8aY4ihXh2g87Z .icon-shape .label{text-anchor:middle;}#mermaid-svg-M0o8aY4ihXh2g87Z .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-M0o8aY4ihXh2g87Z .rough-node .label,#mermaid-svg-M0o8aY4ihXh2g87Z .node .label,#mermaid-svg-M0o8aY4ihXh2g87Z .image-shape .label,#mermaid-svg-M0o8aY4ihXh2g87Z .icon-shape .label{text-align:center;}#mermaid-svg-M0o8aY4ihXh2g87Z .node.clickable{cursor:pointer;}#mermaid-svg-M0o8aY4ihXh2g87Z .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-M0o8aY4ihXh2g87Z .arrowheadPath{fill:#333333;}#mermaid-svg-M0o8aY4ihXh2g87Z .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-M0o8aY4ihXh2g87Z .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-M0o8aY4ihXh2g87Z .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-M0o8aY4ihXh2g87Z .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-M0o8aY4ihXh2g87Z .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-M0o8aY4ihXh2g87Z .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-M0o8aY4ihXh2g87Z .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-M0o8aY4ihXh2g87Z .cluster text{fill:#333;}#mermaid-svg-M0o8aY4ihXh2g87Z .cluster span{color:#333;}#mermaid-svg-M0o8aY4ihXh2g87Z div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-M0o8aY4ihXh2g87Z .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-M0o8aY4ihXh2g87Z rect.text{fill:none;stroke-width:0;}#mermaid-svg-M0o8aY4ihXh2g87Z .icon-shape,#mermaid-svg-M0o8aY4ihXh2g87Z .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-M0o8aY4ihXh2g87Z .icon-shape p,#mermaid-svg-M0o8aY4ihXh2g87Z .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-M0o8aY4ihXh2g87Z .icon-shape .label rect,#mermaid-svg-M0o8aY4ihXh2g87Z .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-M0o8aY4ihXh2g87Z .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-M0o8aY4ihXh2g87Z .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-M0o8aY4ihXh2g87Z :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

第 1 层 — 中等密度，'省道'

第 2 层 — 稀疏连接，'高速公路'

第 3 层（顶层）— 入口层，通常仅 1 个节点

第 0 层 — 最密集，'街道网络'（包含所有 N 个节点）

●

●

●

●

●

●

●

●

●

●

●

●

入口节点 ★

节点A

节点B

节点C

节点A

节点B

节点C

节点D

节点E

HNSW 分层结构侧视：顶层（蓝色）仅 1 个入口节点，越往下节点越多、边越密。第 0 层包含全部数据节点，连接最为密集。

3.3 节点出现在哪一层？

每个节点在插入时，通过以下方式决定它出现在哪些层：

设 ml = 1 / ln(M) （M 为最大连接数，通常取 16~64）

对节点 x：
生成随机数 r ∈ (0, 1)
层数 l = floor(-ln(r) * ml)

其中 ml = 1 / ln(M)，因此：
l = floor(-ln(r) / ln(M))

等价于：P(x 出现在第 l 层) ≈ 1/M^l

推导过程：节点出现在第 l 层的概率等于

P

(

l

−

1

<

−

ln

⁡

(

r

)

⋅

m

l

≤

l

)

P(l-1 < -\\ln(r) \\cdot ml \\le l)

P(l−1<−ln(r)⋅ml≤l)，即

P

(

−

ln

⁡

(

r

)

∈

(

(

l

−

1

)

/

m

l

,

l

/

m

l

]

)

P(-\\ln(r) \\in ((l-1)/ml, l/ml])

P(−ln(r)∈((l−1)/ml,l/ml])。由于

−

ln

⁡

(

r

)

-\\ln(r)

−ln(r) 服从指数分布

E

x

p

(

1

)

Exp(1)

Exp(1)，其 CDF 为

1

−

e

−

t

1 – e^{-t}

1−e−t，因此：

P

(

l

)

=

e

−

(

l

−

1

)

/

m

l

−

e

−

l

/

m

l

=

e

−

(

l

−

1

)

/

m

l

(

1

−

e

−

1

/

m

l

)

P(l) = e^{-(l-1)/ml} – e^{-l/ml} = e^{-(l-1)/ml}(1 – e^{-1/ml})

P(l)=e−(l−1)/ml−e−l/ml=e−(l−1)/ml(1−e−1/ml)

当 M=16 时，

m

l

=

1

/

ln

⁡

(

16

)

≈

0.361

ml = 1/\\ln(16) \\approx 0.361

ml=1/ln(16)≈0.361，各层概率约为：

#mermaid-svg-QmEp13BCF4URXdqA{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-QmEp13BCF4URXdqA .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-QmEp13BCF4URXdqA .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-QmEp13BCF4URXdqA .error-icon{fill:#552222;}#mermaid-svg-QmEp13BCF4URXdqA .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-QmEp13BCF4URXdqA .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-QmEp13BCF4URXdqA .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-QmEp13BCF4URXdqA .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-QmEp13BCF4URXdqA .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-QmEp13BCF4URXdqA .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-QmEp13BCF4URXdqA .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-QmEp13BCF4URXdqA .marker{fill:#333333;stroke:#333333;}#mermaid-svg-QmEp13BCF4URXdqA .marker.cross{stroke:#333333;}#mermaid-svg-QmEp13BCF4URXdqA svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-QmEp13BCF4URXdqA p{margin:0;}#mermaid-svg-QmEp13BCF4URXdqA :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

节点出现在各层的概率（M=16, ml≈0.361）

第0层

第1层

第2层

第3层

第4层

第5层

100

90

80

70

60

50

40

30

20

10

0

概率 (%)

注：第 0 层包含所有节点（概率 100%）。第 l 层（l≥1）的节点数约为

N

/

M

l

N/M^l

N/Ml，当 M=16 时，第 1 层约 N/16 个节点，第 2 层约 N/256 个节点。

直觉理解：大多数节点只在第 0 层（“街道级”），少数节点上升到高层（“高速公路级”），极少数节点到达顶层。高层节点充当"交通枢纽"，为搜索提供远距离跳跃能力。

3.4 各层独立搜索，逐层下降

搜索不是同时在所有层进行，而是从顶层开始，逐层向下：

#mermaid-svg-zT5oSYwyYZL8KpGe{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-zT5oSYwyYZL8KpGe .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-zT5oSYwyYZL8KpGe .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-zT5oSYwyYZL8KpGe .error-icon{fill:#552222;}#mermaid-svg-zT5oSYwyYZL8KpGe .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-zT5oSYwyYZL8KpGe .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-zT5oSYwyYZL8KpGe .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-zT5oSYwyYZL8KpGe .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-zT5oSYwyYZL8KpGe .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-zT5oSYwyYZL8KpGe .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-zT5oSYwyYZL8KpGe .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-zT5oSYwyYZL8KpGe .marker{fill:#333333;stroke:#333333;}#mermaid-svg-zT5oSYwyYZL8KpGe .marker.cross{stroke:#333333;}#mermaid-svg-zT5oSYwyYZL8KpGe svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-zT5oSYwyYZL8KpGe p{margin:0;}#mermaid-svg-zT5oSYwyYZL8KpGe .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-zT5oSYwyYZL8KpGe .cluster-label text{fill:#333;}#mermaid-svg-zT5oSYwyYZL8KpGe .cluster-label span{color:#333;}#mermaid-svg-zT5oSYwyYZL8KpGe .cluster-label span p{background-color:transparent;}#mermaid-svg-zT5oSYwyYZL8KpGe .label text,#mermaid-svg-zT5oSYwyYZL8KpGe span{fill:#333;color:#333;}#mermaid-svg-zT5oSYwyYZL8KpGe .node rect,#mermaid-svg-zT5oSYwyYZL8KpGe .node circle,#mermaid-svg-zT5oSYwyYZL8KpGe .node ellipse,#mermaid-svg-zT5oSYwyYZL8KpGe .node polygon,#mermaid-svg-zT5oSYwyYZL8KpGe .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-zT5oSYwyYZL8KpGe .rough-node .label text,#mermaid-svg-zT5oSYwyYZL8KpGe .node .label text,#mermaid-svg-zT5oSYwyYZL8KpGe .image-shape .label,#mermaid-svg-zT5oSYwyYZL8KpGe .icon-shape .label{text-anchor:middle;}#mermaid-svg-zT5oSYwyYZL8KpGe .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-zT5oSYwyYZL8KpGe .rough-node .label,#mermaid-svg-zT5oSYwyYZL8KpGe .node .label,#mermaid-svg-zT5oSYwyYZL8KpGe .image-shape .label,#mermaid-svg-zT5oSYwyYZL8KpGe .icon-shape .label{text-align:center;}#mermaid-svg-zT5oSYwyYZL8KpGe .node.clickable{cursor:pointer;}#mermaid-svg-zT5oSYwyYZL8KpGe .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-zT5oSYwyYZL8KpGe .arrowheadPath{fill:#333333;}#mermaid-svg-zT5oSYwyYZL8KpGe .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-zT5oSYwyYZL8KpGe .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-zT5oSYwyYZL8KpGe .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-zT5oSYwyYZL8KpGe .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-zT5oSYwyYZL8KpGe .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-zT5oSYwyYZL8KpGe .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-zT5oSYwyYZL8KpGe .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-zT5oSYwyYZL8KpGe .cluster text{fill:#333;}#mermaid-svg-zT5oSYwyYZL8KpGe .cluster span{color:#333;}#mermaid-svg-zT5oSYwyYZL8KpGe div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-zT5oSYwyYZL8KpGe .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-zT5oSYwyYZL8KpGe rect.text{fill:none;stroke-width:0;}#mermaid-svg-zT5oSYwyYZL8KpGe .icon-shape,#mermaid-svg-zT5oSYwyYZL8KpGe .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-zT5oSYwyYZL8KpGe .icon-shape p,#mermaid-svg-zT5oSYwyYZL8KpGe .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-zT5oSYwyYZL8KpGe .icon-shape .label rect,#mermaid-svg-zT5oSYwyYZL8KpGe .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-zT5oSYwyYZL8KpGe .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-zT5oSYwyYZL8KpGe .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-zT5oSYwyYZL8KpGe :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

第 0 层（底层）

第 1 层

第 2 层

第 3 层（顶层）

★ 入口点

●

●

●

●

●

●

●

●

●

●

●

●

●

●

●

●

●

●

搜索从顶层入口点（蓝色）逐层下降，每层缩小搜索范围，最终在底层（红色）定位到最近邻。

4. 搜索算法详解

4.1 算法伪代码

函数 search(q, efSearch):
// q: 查询向量
// efSearch: 搜索时维护的候选列表大小（通常 32~512）

1. 从顶层入口点 ep 开始
2. 对每一层 l，从顶层到第1层：
a. 在当前层执行贪心搜索
b. 维护一个大小为 1 的优先队列（当前最近邻）
c. 直到无法找到更近的节点
d. 将当前层找到的最近邻作为下一层的入口点
3. 在第0层执行贪心搜索：
a. 维护一个大小为 efSearch 的优先队列
b. 返回 efSearch 个最近邻

4.2 单层贪心搜索详细步骤

函数 greedySearch(q, entryPoint, ef):
candidates = 最小堆（按到 q 的距离排序）
visited = 集合
result = 最大堆（按到 q 的距离排序） // 保存当前最近的 ef 个节点

dist = distance(q, entryPoint)
candidates.push(entryPoint, dist)
result.push(entryPoint, dist)
visited.add(entryPoint)

当 candidates 不为空时循环：
c = candidates.pop()

// 终止条件：c 比 result 中最远的节点还远，后续不可能更优
如果 distance(q, c) > distance(q, result.peek()):
跳出循环

对于 c 的每个邻居 e：
如果 e 未被访问过：
标记 e 为已访问
dist_e = distance(q, e)

如果 dist_e < distance(q, result.peek()) 或 result.size < ef：
candidates.push(e, dist_e)
result.push(e, dist_e)

如果 result.size > ef：
result.pop()

返回 result 中的 ef 个节点

4.3 搜索过程图解

#mermaid-svg-6yQsEw29uz9KGHQC{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-6yQsEw29uz9KGHQC .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-6yQsEw29uz9KGHQC .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-6yQsEw29uz9KGHQC .error-icon{fill:#552222;}#mermaid-svg-6yQsEw29uz9KGHQC .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-6yQsEw29uz9KGHQC .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-6yQsEw29uz9KGHQC .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-6yQsEw29uz9KGHQC .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-6yQsEw29uz9KGHQC .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-6yQsEw29uz9KGHQC .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-6yQsEw29uz9KGHQC .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-6yQsEw29uz9KGHQC .marker{fill:#333333;stroke:#333333;}#mermaid-svg-6yQsEw29uz9KGHQC .marker.cross{stroke:#333333;}#mermaid-svg-6yQsEw29uz9KGHQC svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-6yQsEw29uz9KGHQC p{margin:0;}#mermaid-svg-6yQsEw29uz9KGHQC .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-6yQsEw29uz9KGHQC .cluster-label text{fill:#333;}#mermaid-svg-6yQsEw29uz9KGHQC .cluster-label span{color:#333;}#mermaid-svg-6yQsEw29uz9KGHQC .cluster-label span p{background-color:transparent;}#mermaid-svg-6yQsEw29uz9KGHQC .label text,#mermaid-svg-6yQsEw29uz9KGHQC span{fill:#333;color:#333;}#mermaid-svg-6yQsEw29uz9KGHQC .node rect,#mermaid-svg-6yQsEw29uz9KGHQC .node circle,#mermaid-svg-6yQsEw29uz9KGHQC .node ellipse,#mermaid-svg-6yQsEw29uz9KGHQC .node polygon,#mermaid-svg-6yQsEw29uz9KGHQC .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-6yQsEw29uz9KGHQC .rough-node .label text,#mermaid-svg-6yQsEw29uz9KGHQC .node .label text,#mermaid-svg-6yQsEw29uz9KGHQC .image-shape .label,#mermaid-svg-6yQsEw29uz9KGHQC .icon-shape .label{text-anchor:middle;}#mermaid-svg-6yQsEw29uz9KGHQC .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-6yQsEw29uz9KGHQC .rough-node .label,#mermaid-svg-6yQsEw29uz9KGHQC .node .label,#mermaid-svg-6yQsEw29uz9KGHQC .image-shape .label,#mermaid-svg-6yQsEw29uz9KGHQC .icon-shape .label{text-align:center;}#mermaid-svg-6yQsEw29uz9KGHQC .node.clickable{cursor:pointer;}#mermaid-svg-6yQsEw29uz9KGHQC .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-6yQsEw29uz9KGHQC .arrowheadPath{fill:#333333;}#mermaid-svg-6yQsEw29uz9KGHQC .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-6yQsEw29uz9KGHQC .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-6yQsEw29uz9KGHQC .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-6yQsEw29uz9KGHQC .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-6yQsEw29uz9KGHQC .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-6yQsEw29uz9KGHQC .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-6yQsEw29uz9KGHQC .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-6yQsEw29uz9KGHQC .cluster text{fill:#333;}#mermaid-svg-6yQsEw29uz9KGHQC .cluster span{color:#333;}#mermaid-svg-6yQsEw29uz9KGHQC div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-6yQsEw29uz9KGHQC .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-6yQsEw29uz9KGHQC rect.text{fill:none;stroke-width:0;}#mermaid-svg-6yQsEw29uz9KGHQC .icon-shape,#mermaid-svg-6yQsEw29uz9KGHQC .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-6yQsEw29uz9KGHQC .icon-shape p,#mermaid-svg-6yQsEw29uz9KGHQC .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-6yQsEw29uz9KGHQC .icon-shape .label rect,#mermaid-svg-6yQsEw29uz9KGHQC .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-6yQsEw29uz9KGHQC .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-6yQsEw29uz9KGHQC .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-6yQsEw29uz9KGHQC :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

搜索过程

A (入口点)

B

C

D

E

F

G

H

★ 近邻1

★ 近邻2

★ 近邻3

查询点 q

第 0 层搜索过程：从入口点 A（蓝色）出发逐步扩展邻居，最终收敛到查询点 q（红色）附近的 3 个最近邻（绿色）。

4.4 efSearch 的作用

efSearch 控制搜索的"宽度"：

• efSearch 小（如 16）：搜索快，但可能漏掉真正的最近邻
• efSearch 大（如 256）：搜索慢，但召回率高

#mermaid-svg-sUu02rms2ShTQuf3{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-sUu02rms2ShTQuf3 .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-sUu02rms2ShTQuf3 .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-sUu02rms2ShTQuf3 .error-icon{fill:#552222;}#mermaid-svg-sUu02rms2ShTQuf3 .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-sUu02rms2ShTQuf3 .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-sUu02rms2ShTQuf3 .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-sUu02rms2ShTQuf3 .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-sUu02rms2ShTQuf3 .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-sUu02rms2ShTQuf3 .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-sUu02rms2ShTQuf3 .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-sUu02rms2ShTQuf3 .marker{fill:#333333;stroke:#333333;}#mermaid-svg-sUu02rms2ShTQuf3 .marker.cross{stroke:#333333;}#mermaid-svg-sUu02rms2ShTQuf3 svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-sUu02rms2ShTQuf3 p{margin:0;}#mermaid-svg-sUu02rms2ShTQuf3 .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-sUu02rms2ShTQuf3 .cluster-label text{fill:#333;}#mermaid-svg-sUu02rms2ShTQuf3 .cluster-label span{color:#333;}#mermaid-svg-sUu02rms2ShTQuf3 .cluster-label span p{background-color:transparent;}#mermaid-svg-sUu02rms2ShTQuf3 .label text,#mermaid-svg-sUu02rms2ShTQuf3 span{fill:#333;color:#333;}#mermaid-svg-sUu02rms2ShTQuf3 .node rect,#mermaid-svg-sUu02rms2ShTQuf3 .node circle,#mermaid-svg-sUu02rms2ShTQuf3 .node ellipse,#mermaid-svg-sUu02rms2ShTQuf3 .node polygon,#mermaid-svg-sUu02rms2ShTQuf3 .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-sUu02rms2ShTQuf3 .rough-node .label text,#mermaid-svg-sUu02rms2ShTQuf3 .node .label text,#mermaid-svg-sUu02rms2ShTQuf3 .image-shape .label,#mermaid-svg-sUu02rms2ShTQuf3 .icon-shape .label{text-anchor:middle;}#mermaid-svg-sUu02rms2ShTQuf3 .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-sUu02rms2ShTQuf3 .rough-node .label,#mermaid-svg-sUu02rms2ShTQuf3 .node .label,#mermaid-svg-sUu02rms2ShTQuf3 .image-shape .label,#mermaid-svg-sUu02rms2ShTQuf3 .icon-shape .label{text-align:center;}#mermaid-svg-sUu02rms2ShTQuf3 .node.clickable{cursor:pointer;}#mermaid-svg-sUu02rms2ShTQuf3 .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-sUu02rms2ShTQuf3 .arrowheadPath{fill:#333333;}#mermaid-svg-sUu02rms2ShTQuf3 .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-sUu02rms2ShTQuf3 .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-sUu02rms2ShTQuf3 .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-sUu02rms2ShTQuf3 .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-sUu02rms2ShTQuf3 .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-sUu02rms2ShTQuf3 .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-sUu02rms2ShTQuf3 .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-sUu02rms2ShTQuf3 .cluster text{fill:#333;}#mermaid-svg-sUu02rms2ShTQuf3 .cluster span{color:#333;}#mermaid-svg-sUu02rms2ShTQuf3 div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-sUu02rms2ShTQuf3 .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-sUu02rms2ShTQuf3 rect.text{fill:none;stroke-width:0;}#mermaid-svg-sUu02rms2ShTQuf3 .icon-shape,#mermaid-svg-sUu02rms2ShTQuf3 .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-sUu02rms2ShTQuf3 .icon-shape p,#mermaid-svg-sUu02rms2ShTQuf3 .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-sUu02rms2ShTQuf3 .icon-shape .label rect,#mermaid-svg-sUu02rms2ShTQuf3 .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-sUu02rms2ShTQuf3 .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-sUu02rms2ShTQuf3 .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-sUu02rms2ShTQuf3 :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

efSearch=3（探索更多路径，更可能找到全局最优）

●入口

○

○

○

★目标

○

○

efSearch=1（纯贪心，路径短但可能陷入局部最优）

●入口

○

○

○

★目标

efSearch 控制搜索宽度：efSearch=1 只保留 1 个候选，路径短但可能错过全局最优；efSearch=3 保留 3 个候选，探索更多路径，召回率更高。

5. 插入算法详解

5.1 算法概述

插入新节点时，需要完成两件事：

5.2 插入过程伪代码

函数 insert(q, M, efConstruction):
// 参数：q 为待插入向量，M 为最大连接数，efConstruction 为候选列表大小

1. 确定 q 的最高层 l（随机采样）

2. 从顶层入口点逐层下降到第 l 层：
在每一层找到离 q 最近的 1 个节点作为下一层入口

3. 从第 l 层到第 0 层逐层插入：
a. 在当前层搜索 q 的 efConstruction 个最近邻
b. 从中选择最近的 M 个作为 q 的邻居
// 第 0 层最多选 M_max0 = 2M 个，第 1 层及以上最多选 M 个
c. 建立双向边（q ↔ 邻居）
d. 邻居度数超过上限时执行修剪
e. 将 q 作为下一层入口

4. 如果 l > 当前最高层，将 q 设为新的顶层入口点

5.3 插入过程图解

#mermaid-svg-07Iahi1XUtasQLff{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-07Iahi1XUtasQLff .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-07Iahi1XUtasQLff .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-07Iahi1XUtasQLff .error-icon{fill:#552222;}#mermaid-svg-07Iahi1XUtasQLff .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-07Iahi1XUtasQLff .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-07Iahi1XUtasQLff .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-07Iahi1XUtasQLff .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-07Iahi1XUtasQLff .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-07Iahi1XUtasQLff .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-07Iahi1XUtasQLff .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-07Iahi1XUtasQLff .marker{fill:#333333;stroke:#333333;}#mermaid-svg-07Iahi1XUtasQLff .marker.cross{stroke:#333333;}#mermaid-svg-07Iahi1XUtasQLff svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-07Iahi1XUtasQLff p{margin:0;}#mermaid-svg-07Iahi1XUtasQLff .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-07Iahi1XUtasQLff .cluster-label text{fill:#333;}#mermaid-svg-07Iahi1XUtasQLff .cluster-label span{color:#333;}#mermaid-svg-07Iahi1XUtasQLff .cluster-label span p{background-color:transparent;}#mermaid-svg-07Iahi1XUtasQLff .label text,#mermaid-svg-07Iahi1XUtasQLff span{fill:#333;color:#333;}#mermaid-svg-07Iahi1XUtasQLff .node rect,#mermaid-svg-07Iahi1XUtasQLff .node circle,#mermaid-svg-07Iahi1XUtasQLff .node ellipse,#mermaid-svg-07Iahi1XUtasQLff .node polygon,#mermaid-svg-07Iahi1XUtasQLff .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-07Iahi1XUtasQLff .rough-node .label text,#mermaid-svg-07Iahi1XUtasQLff .node .label text,#mermaid-svg-07Iahi1XUtasQLff .image-shape .label,#mermaid-svg-07Iahi1XUtasQLff .icon-shape .label{text-anchor:middle;}#mermaid-svg-07Iahi1XUtasQLff .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-07Iahi1XUtasQLff .rough-node .label,#mermaid-svg-07Iahi1XUtasQLff .node .label,#mermaid-svg-07Iahi1XUtasQLff .image-shape .label,#mermaid-svg-07Iahi1XUtasQLff .icon-shape .label{text-align:center;}#mermaid-svg-07Iahi1XUtasQLff .node.clickable{cursor:pointer;}#mermaid-svg-07Iahi1XUtasQLff .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-07Iahi1XUtasQLff .arrowheadPath{fill:#333333;}#mermaid-svg-07Iahi1XUtasQLff .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-07Iahi1XUtasQLff .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-07Iahi1XUtasQLff .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-07Iahi1XUtasQLff .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-07Iahi1XUtasQLff .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-07Iahi1XUtasQLff .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-07Iahi1XUtasQLff .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-07Iahi1XUtasQLff .cluster text{fill:#333;}#mermaid-svg-07Iahi1XUtasQLff .cluster span{color:#333;}#mermaid-svg-07Iahi1XUtasQLff div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-07Iahi1XUtasQLff .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-07Iahi1XUtasQLff rect.text{fill:none;stroke-width:0;}#mermaid-svg-07Iahi1XUtasQLff .icon-shape,#mermaid-svg-07Iahi1XUtasQLff .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-07Iahi1XUtasQLff .icon-shape p,#mermaid-svg-07Iahi1XUtasQLff .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-07Iahi1XUtasQLff .icon-shape .label rect,#mermaid-svg-07Iahi1XUtasQLff .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-07Iahi1XUtasQLff .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-07Iahi1XUtasQLff .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-07Iahi1XUtasQLff :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

Step 3：在第 0 层搜索最近邻并建立双向连接

第 0 层（插入后，q 用 ★ 表示）

○

○

○

○

○ — ★ q — ○

○

○

○

○

第 0 层（插入前）

○

○

○

○

○

○

○

○

○

Step 2：在第 1 层搜索最近邻并建立连接

第 1 层（插入后，q 用 ★ 表示）

●

●

★ q

●

●

第 1 层（插入前）

●

●

●

●

●

Step 1：从顶层定位到 q 的最高层

第 1 层

第 2 层

第 3 层

●

●

●

●

●

●

●

●

★ 入口

插入过程分三步：Step 1 从顶层定位到 q 的最高层（第 1 层），Step 2 在第 1 层搜索最近邻并建立连接，Step 3 在第 0 层搜索最近邻并建立双向连接（红色节点为 q）。

5.4 邻居修剪（Shrink）

当一个节点已有 M 个邻居，此时新邻居要加入，需要决定保留哪些边：

#mermaid-svg-818MMQjn7XayVbmP{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-818MMQjn7XayVbmP .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-818MMQjn7XayVbmP .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-818MMQjn7XayVbmP .error-icon{fill:#552222;}#mermaid-svg-818MMQjn7XayVbmP .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-818MMQjn7XayVbmP .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-818MMQjn7XayVbmP .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-818MMQjn7XayVbmP .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-818MMQjn7XayVbmP .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-818MMQjn7XayVbmP .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-818MMQjn7XayVbmP .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-818MMQjn7XayVbmP .marker{fill:#333333;stroke:#333333;}#mermaid-svg-818MMQjn7XayVbmP .marker.cross{stroke:#333333;}#mermaid-svg-818MMQjn7XayVbmP svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-818MMQjn7XayVbmP p{margin:0;}#mermaid-svg-818MMQjn7XayVbmP .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-818MMQjn7XayVbmP .cluster-label text{fill:#333;}#mermaid-svg-818MMQjn7XayVbmP .cluster-label span{color:#333;}#mermaid-svg-818MMQjn7XayVbmP .cluster-label span p{background-color:transparent;}#mermaid-svg-818MMQjn7XayVbmP .label text,#mermaid-svg-818MMQjn7XayVbmP span{fill:#333;color:#333;}#mermaid-svg-818MMQjn7XayVbmP .node rect,#mermaid-svg-818MMQjn7XayVbmP .node circle,#mermaid-svg-818MMQjn7XayVbmP .node ellipse,#mermaid-svg-818MMQjn7XayVbmP .node polygon,#mermaid-svg-818MMQjn7XayVbmP .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-818MMQjn7XayVbmP .rough-node .label text,#mermaid-svg-818MMQjn7XayVbmP .node .label text,#mermaid-svg-818MMQjn7XayVbmP .image-shape .label,#mermaid-svg-818MMQjn7XayVbmP .icon-shape .label{text-anchor:middle;}#mermaid-svg-818MMQjn7XayVbmP .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-818MMQjn7XayVbmP .rough-node .label,#mermaid-svg-818MMQjn7XayVbmP .node .label,#mermaid-svg-818MMQjn7XayVbmP .image-shape .label,#mermaid-svg-818MMQjn7XayVbmP .icon-shape .label{text-align:center;}#mermaid-svg-818MMQjn7XayVbmP .node.clickable{cursor:pointer;}#mermaid-svg-818MMQjn7XayVbmP .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-818MMQjn7XayVbmP .arrowheadPath{fill:#333333;}#mermaid-svg-818MMQjn7XayVbmP .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-818MMQjn7XayVbmP .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-818MMQjn7XayVbmP .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-818MMQjn7XayVbmP .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-818MMQjn7XayVbmP .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-818MMQjn7XayVbmP .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-818MMQjn7XayVbmP .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-818MMQjn7XayVbmP .cluster text{fill:#333;}#mermaid-svg-818MMQjn7XayVbmP .cluster span{color:#333;}#mermaid-svg-818MMQjn7XayVbmP div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-818MMQjn7XayVbmP .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-818MMQjn7XayVbmP rect.text{fill:none;stroke-width:0;}#mermaid-svg-818MMQjn7XayVbmP .icon-shape,#mermaid-svg-818MMQjn7XayVbmP .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-818MMQjn7XayVbmP .icon-shape p,#mermaid-svg-818MMQjn7XayVbmP .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-818MMQjn7XayVbmP .icon-shape .label rect,#mermaid-svg-818MMQjn7XayVbmP .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-818MMQjn7XayVbmP .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-818MMQjn7XayVbmP .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-818MMQjn7XayVbmP :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

方案二：启发式修剪（HNSW 采用，保留视野更广的 M=3 个）

节点 C

A (距离=1)

E (距离=3)

D (距离=4, 但方向不同，保留)

B (距离=2, 但被 A 覆盖，移除)

方案一：简单截断（保留最近的 M=3 个）

节点 C

A (距离=1)

B (距离=2)

E (距离=3)

D (距离=4, 被移除)

邻居修剪策略对比：方案一简单保留距离最近的 M 个邻居；方案二（HNSW 采用）考虑邻居之间的覆盖性——即使某个邻居距离稍远，只要它指向不同方向，仍会被保留，从而让节点的"视野"更广。

HNSW 论文中的启发式修剪算法：

函数 shrink(neighbors, M):
// neighbors 为候选邻居列表（已按距离排序），M 为最大连接数

如果 neighbors.size ≤ M：
返回 neighbors

result = 空列表
对于 neighbors 中的每个节点 e：
如果 result.size ≥ M：
跳出循环

// 覆盖性检查：若 result 中已有比 e 更接近当前节点的邻居，则 e 多余
dominated = false
对于 result 中的每个已有邻居 r：
如果 distance(r, e) < distance(e, currentNode):
dominated = true
跳出循环

如果 not dominated：
result.push(e)

返回 result

5.5 增量构建的特点

HNSW 的一个关键优势是支持增量插入——不需要预先知道所有数据，可以逐条插入新节点。新节点会自动连接到真正的近邻，已有的图结构不会被破坏，只会增加少量新边。相比之下，Annoy 需要一次性构建所有树，IVF-PQ 需要预先聚类，都不支持这种增量模式。

6. 复杂度分析

6.1 搜索复杂度

设数据集大小为 N，最大连接数为 M：

搜索过程：

顶层到第 1 层（共 L 层，每层约 M 步）：
L ≈ log_{1/ml}(N) = ln(N) / ln(1/ml) = ln(N) × M
步数 ≈ L × M = O(M² × ln(N))

第 0 层（efSearch 个候选）：
步数 ≈ efSearch × M

总计：O(M² × ln(N) + efSearch × M)

实际中 M 和 efSearch 是常数，因此简化为 O(log N)

6.2 插入复杂度

插入过程：

定位层数：O(M × log N) // 从顶层下降到第 l 层
每层搜索：O(efConstruction × M × log N)
共 l+1 层，平均 l ≈ ln(M) – 1 // 节点最高层的期望值

总计：O(efConstruction × M × log N)

6.3 空间复杂度

采用有向图视角（每个节点独立维护自己的邻居列表，q ↔ 邻居 意味着两条有向边）：

每个节点在第 0 层最多 M_max0 个出边邻居（通常 M_max0 = 2M）
每个节点在第 l 层（l≥1）最多 M 个出边邻居

第 0 层总边数 ≈ N × M_max0
第 1 层总边数 ≈ (N/M) × M = N （仅约 N/M 个节点出现在第 1 层）
第 2 层总边数 ≈ (N/M²) × M = N/M
…

总边数 ≈ N × M_max0 + N × (1 + 1/M + 1/M² + …)
≈ N × 2M + N × M/(M-1)
≈ N × (2M + M/(M-1))

当 M=16 时，总边数 ≈ N × (32 + 16/15) ≈ 33.1N

空间占用 = 向量存储 + 图结构（边列表，每条边存一个 int32 邻居 ID）
= N × d × 4 bytes + 33.1N × 4 bytes
≈ (4d + 132) × N bytes

注：hnswlib 等实际实现中，第 0 层每个节点最多 2M 个邻居，第 1 层及以上最多 M 个邻居。这保证了第 0 层有更密集的连接以支持精确搜索。

7. 关键参数与调优

7.1 参数总览

7.2 M 的选择

#mermaid-svg-ACYHLDBcS3cZ8svj{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-ACYHLDBcS3cZ8svj .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-ACYHLDBcS3cZ8svj .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-ACYHLDBcS3cZ8svj .error-icon{fill:#552222;}#mermaid-svg-ACYHLDBcS3cZ8svj .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-ACYHLDBcS3cZ8svj .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-ACYHLDBcS3cZ8svj .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-ACYHLDBcS3cZ8svj .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-ACYHLDBcS3cZ8svj .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-ACYHLDBcS3cZ8svj .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-ACYHLDBcS3cZ8svj .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-ACYHLDBcS3cZ8svj .marker{fill:#333333;stroke:#333333;}#mermaid-svg-ACYHLDBcS3cZ8svj .marker.cross{stroke:#333333;}#mermaid-svg-ACYHLDBcS3cZ8svj svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-ACYHLDBcS3cZ8svj p{margin:0;}#mermaid-svg-ACYHLDBcS3cZ8svj :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

M 值对性能的影响（定性趋势）

M=4

M=8

M=16

M=32

M=64

100

90

80

70

60

50

40

30

20

10

0

相对值

经验法则：低维数据（d<32）取 M=8~16；中维数据（32≤d≤256）取 M=16~32；高维数据（d>256）取 M=32~64。

7.3 efSearch 与召回率的关系

#mermaid-svg-WJJS2woNLqYO4NGk{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-WJJS2woNLqYO4NGk .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-WJJS2woNLqYO4NGk .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-WJJS2woNLqYO4NGk .error-icon{fill:#552222;}#mermaid-svg-WJJS2woNLqYO4NGk .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-WJJS2woNLqYO4NGk .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-WJJS2woNLqYO4NGk .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-WJJS2woNLqYO4NGk .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-WJJS2woNLqYO4NGk .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-WJJS2woNLqYO4NGk .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-WJJS2woNLqYO4NGk .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-WJJS2woNLqYO4NGk .marker{fill:#333333;stroke:#333333;}#mermaid-svg-WJJS2woNLqYO4NGk .marker.cross{stroke:#333333;}#mermaid-svg-WJJS2woNLqYO4NGk svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-WJJS2woNLqYO4NGk p{margin:0;}#mermaid-svg-WJJS2woNLqYO4NGk :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

efSearch 与召回率的关系（典型曲线）

50

100

150

200

250

300

350

400

450

500

efSearch

100

98

96

94

92

90

88

86

84

82

80

78

76

召回率 (%)

efSearch 与召回率的关系：efSearch 越大召回率越高，但搜索越慢。经验上，efSearch = 4×M 通常达到 95%+ 召回率，efSearch = 8×M 达到 99%+。

7.4 距离度量选择

HNSW 本身不限制距离函数，但实际使用中：

• 内积（Inner Product）：适合归一化向量的相似度搜索
• L2 距离（欧氏距离）：最通用的选择
• 余弦相似度：等价于归一化后的内积

注意：HNSW 要求距离函数满足三角不等式（是度量空间），否则贪心搜索的理论保证不成立。

8. 与其他 ANN 算法的对比

8.1 综合对比表

8.2 选型决策树

#mermaid-svg-D3xEv48d3iSZsPXu{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-D3xEv48d3iSZsPXu .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-D3xEv48d3iSZsPXu .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-D3xEv48d3iSZsPXu .error-icon{fill:#552222;}#mermaid-svg-D3xEv48d3iSZsPXu .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-D3xEv48d3iSZsPXu .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-D3xEv48d3iSZsPXu .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-D3xEv48d3iSZsPXu .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-D3xEv48d3iSZsPXu .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-D3xEv48d3iSZsPXu .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-D3xEv48d3iSZsPXu .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-D3xEv48d3iSZsPXu .marker{fill:#333333;stroke:#333333;}#mermaid-svg-D3xEv48d3iSZsPXu .marker.cross{stroke:#333333;}#mermaid-svg-D3xEv48d3iSZsPXu svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-D3xEv48d3iSZsPXu p{margin:0;}#mermaid-svg-D3xEv48d3iSZsPXu .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-D3xEv48d3iSZsPXu .cluster-label text{fill:#333;}#mermaid-svg-D3xEv48d3iSZsPXu .cluster-label span{color:#333;}#mermaid-svg-D3xEv48d3iSZsPXu .cluster-label span p{background-color:transparent;}#mermaid-svg-D3xEv48d3iSZsPXu .label text,#mermaid-svg-D3xEv48d3iSZsPXu span{fill:#333;color:#333;}#mermaid-svg-D3xEv48d3iSZsPXu .node rect,#mermaid-svg-D3xEv48d3iSZsPXu .node circle,#mermaid-svg-D3xEv48d3iSZsPXu .node ellipse,#mermaid-svg-D3xEv48d3iSZsPXu .node polygon,#mermaid-svg-D3xEv48d3iSZsPXu .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-D3xEv48d3iSZsPXu .rough-node .label text,#mermaid-svg-D3xEv48d3iSZsPXu .node .label text,#mermaid-svg-D3xEv48d3iSZsPXu .image-shape .label,#mermaid-svg-D3xEv48d3iSZsPXu .icon-shape .label{text-anchor:middle;}#mermaid-svg-D3xEv48d3iSZsPXu .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-D3xEv48d3iSZsPXu .rough-node .label,#mermaid-svg-D3xEv48d3iSZsPXu .node .label,#mermaid-svg-D3xEv48d3iSZsPXu .image-shape .label,#mermaid-svg-D3xEv48d3iSZsPXu .icon-shape .label{text-align:center;}#mermaid-svg-D3xEv48d3iSZsPXu .node.clickable{cursor:pointer;}#mermaid-svg-D3xEv48d3iSZsPXu .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-D3xEv48d3iSZsPXu .arrowheadPath{fill:#333333;}#mermaid-svg-D3xEv48d3iSZsPXu .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-D3xEv48d3iSZsPXu .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-D3xEv48d3iSZsPXu .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-D3xEv48d3iSZsPXu .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-D3xEv48d3iSZsPXu .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-D3xEv48d3iSZsPXu .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-D3xEv48d3iSZsPXu .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-D3xEv48d3iSZsPXu .cluster text{fill:#333;}#mermaid-svg-D3xEv48d3iSZsPXu .cluster span{color:#333;}#mermaid-svg-D3xEv48d3iSZsPXu div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-D3xEv48d3iSZsPXu .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-D3xEv48d3iSZsPXu rect.text{fill:none;stroke-width:0;}#mermaid-svg-D3xEv48d3iSZsPXu .icon-shape,#mermaid-svg-D3xEv48d3iSZsPXu .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-D3xEv48d3iSZsPXu .icon-shape p,#mermaid-svg-D3xEv48d3iSZsPXu .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-D3xEv48d3iSZsPXu .icon-shape .label rect,#mermaid-svg-D3xEv48d3iSZsPXu .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-D3xEv48d3iSZsPXu .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-D3xEv48d3iSZsPXu .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-D3xEv48d3iSZsPXu :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

是

否

< 100 万

100 万 ~ 1 亿

> 1 亿

是

否

是

否

是

否

需要增量插入？

数据规模？

内存受限？

维度 > 256？

维度 < 20？

选择 HNSW

选择 HNSW（最简单，效果最好）

选择 IVF-PQ + HNSW 混合（IVF 分簇，簇内 HNSW）

选择 IVF-PQ

选择 HNSW

选择 HNSW（KD-Tree 和 LSH 不适合高维）

KD-Tree 也可考虑

选择 HNSW（默认最佳选择）

ANN 算法选型决策树：HNSW 是大多数场景的默认选择；超大规模且内存受限时选 IVF-PQ；极低维场景可考虑 KD-Tree。

9. 实现要点与工程实践

9.1 核心数据结构

# HNSW 索引的核心数据结构（伪代码）

class HNSWIndex:
def __init__(self, dim, M=16, ef_construction=200, ml=None):
self.dim = dim # 向量维度
self.M = M # 第 1 层及以上每个节点的最大连接数
self.M_max0 = M * 2 # 第 0 层每个节点的最大连接数（通常更大）
self.ef_construction = ef_construction
self.ml = ml or 1.0 / math.log(M)

self.vectors = {} # 节点 ID → 向量
self.graphs = {} # 层数 → {节点 ID → [邻居 ID 列表]}
self.entry_point = None # 顶层入口节点 ID
self.max_level = 0

class Node:
def __init__(self, id, vector):
self.id = id
self.vector = vector
self.neighbors = {} # 层数 → [邻居 ID 列表]
self.level = 0 # 节点出现的最高层

9.2 距离计算的优化

距离计算是 HNSW 中最频繁的操作，通常占总时间的 80% 以上：

优化手段：

1. SIMD 向量化
– 使用 AVX2/AVX512 指令集
– 一次计算 8~16 个 float32 的乘加

2. 提前终止（Early Termination）
– 计算 L2 距离时，逐个维度累加
– 当部分和已经超过当前最优值时，提前终止

3. 向量量化
– float32 → float16（精度损失极小，速度提升约 2x）
– 或配合 PQ 进一步压缩

4. 缓存友好性
– 邻居列表连续存储
– 向量数据按访问模式对齐

9.3 并发控制

HNSW 的并发挑战：

读操作（搜索）：
– 只读图结构，天然支持并发
– 多个搜索请求可以并行执行

写操作（插入）：
– 插入新节点会修改图结构（增加边）
– 需要加写锁或使用读写锁（RWLock）

工程实践：
1. 读写分离：搜索不加锁，插入加写锁
2. 批量插入：累积一批数据后统一插入，减少锁竞争
3. 副本机制：写操作在副本上进行，定期合并到主索引

9.4 主流开源实现

9.5 典型性能基准

数据集：SIFT-1M（100万个 128 维向量）
硬件：Intel Xeon 2.4GHz，64GB 内存

hnswlib 性能（M=16, efConstruction=200）：

构建时间：约 45 秒
内存占用：约 1.2 GB
搜索延迟（efSearch=64）：约 0.5 ms
召回率（efSearch=64）：约 99.2%

对比暴力搜索：
搜索延迟：约 50 ms
召回率：100%

HNSW 加速比：约 100 倍，代价是损失 0.8% 的精确度

附录：HNSW 搜索算法完整流程图

#mermaid-svg-Q93VmIPJJIpaKjuo{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-Q93VmIPJJIpaKjuo .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-Q93VmIPJJIpaKjuo .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-Q93VmIPJJIpaKjuo .error-icon{fill:#552222;}#mermaid-svg-Q93VmIPJJIpaKjuo .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-Q93VmIPJJIpaKjuo .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-Q93VmIPJJIpaKjuo .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-Q93VmIPJJIpaKjuo .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-Q93VmIPJJIpaKjuo .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-Q93VmIPJJIpaKjuo .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-Q93VmIPJJIpaKjuo .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-Q93VmIPJJIpaKjuo .marker{fill:#333333;stroke:#333333;}#mermaid-svg-Q93VmIPJJIpaKjuo .marker.cross{stroke:#333333;}#mermaid-svg-Q93VmIPJJIpaKjuo svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-Q93VmIPJJIpaKjuo p{margin:0;}#mermaid-svg-Q93VmIPJJIpaKjuo .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-Q93VmIPJJIpaKjuo .cluster-label text{fill:#333;}#mermaid-svg-Q93VmIPJJIpaKjuo .cluster-label span{color:#333;}#mermaid-svg-Q93VmIPJJIpaKjuo .cluster-label span p{background-color:transparent;}#mermaid-svg-Q93VmIPJJIpaKjuo .label text,#mermaid-svg-Q93VmIPJJIpaKjuo span{fill:#333;color:#333;}#mermaid-svg-Q93VmIPJJIpaKjuo .node rect,#mermaid-svg-Q93VmIPJJIpaKjuo .node circle,#mermaid-svg-Q93VmIPJJIpaKjuo .node ellipse,#mermaid-svg-Q93VmIPJJIpaKjuo .node polygon,#mermaid-svg-Q93VmIPJJIpaKjuo .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-Q93VmIPJJIpaKjuo .rough-node .label text,#mermaid-svg-Q93VmIPJJIpaKjuo .node .label text,#mermaid-svg-Q93VmIPJJIpaKjuo .image-shape .label,#mermaid-svg-Q93VmIPJJIpaKjuo .icon-shape .label{text-anchor:middle;}#mermaid-svg-Q93VmIPJJIpaKjuo .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-Q93VmIPJJIpaKjuo .rough-node .label,#mermaid-svg-Q93VmIPJJIpaKjuo .node .label,#mermaid-svg-Q93VmIPJJIpaKjuo .image-shape .label,#mermaid-svg-Q93VmIPJJIpaKjuo .icon-shape .label{text-align:center;}#mermaid-svg-Q93VmIPJJIpaKjuo .node.clickable{cursor:pointer;}#mermaid-svg-Q93VmIPJJIpaKjuo .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-Q93VmIPJJIpaKjuo .arrowheadPath{fill:#333333;}#mermaid-svg-Q93VmIPJJIpaKjuo .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-Q93VmIPJJIpaKjuo .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-Q93VmIPJJIpaKjuo .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-Q93VmIPJJIpaKjuo .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-Q93VmIPJJIpaKjuo .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-Q93VmIPJJIpaKjuo .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-Q93VmIPJJIpaKjuo .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-Q93VmIPJJIpaKjuo .cluster text{fill:#333;}#mermaid-svg-Q93VmIPJJIpaKjuo .cluster span{color:#333;}#mermaid-svg-Q93VmIPJJIpaKjuo div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-Q93VmIPJJIpaKjuo .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-Q93VmIPJJIpaKjuo rect.text{fill:none;stroke-width:0;}#mermaid-svg-Q93VmIPJJIpaKjuo .icon-shape,#mermaid-svg-Q93VmIPJJIpaKjuo .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-Q93VmIPJJIpaKjuo .icon-shape p,#mermaid-svg-Q93VmIPJJIpaKjuo .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-Q93VmIPJJIpaKjuo .icon-shape .label rect,#mermaid-svg-Q93VmIPJJIpaKjuo .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-Q93VmIPJJIpaKjuo .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-Q93VmIPJJIpaKjuo .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-Q93VmIPJJIpaKjuo :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

否

是

查询向量 q

从顶层入口点 ep 开始

确定当前层数 L

在当前层执行贪心搜索维护大小为 1 的候选队列直到无法找到更近的节点

当前层是否是第 0 层？

将当前层找到的最近邻作为下一层的入口点

下降到下一层

在第 0 层执行贪心搜索维护大小为 efSearch 的候选队列返回 efSearch 个最近邻

返回结果

HNSW 搜索算法完整流程：从顶层入口点逐层下降，顶层到第 1 层每层只保留 1 个最近邻作为下一层入口，到达第 0 层后用 efSearch 维护候选队列并返回结果。