HNSW：图索引如何击败树索引

在高维向量检索领域，树结构索引（KD-tree、Ball-tree）在维度超过 20 之后就退化为暴力扫描，哈希方法（LSH）虽然理论优美但召回率难以调优——而 HNSW（Hierarchical Navigable Small World）凭借分层图结构和贪心搜索，在精度、速度、内存之间找到了工程上最优的平衡点。自 2016 年 Malkov 和 Yashunin 发表论文以来，HNSW 已经成为 Faiss、Milvus、Weaviate、Pinecone、Qdrant 等几乎所有主流向量数据库的默认索引算法。

这篇文章从 NSW 图的直觉出发，逐层推导出 HNSW 的设计，给出完整的 C 语言实现，讨论参数调优和工程陷阱，最后对比 Vamana（DiskANN）等竞品算法。

下图展示了 HNSW 的分层图结构以及搜索路径：

一、从最近邻搜索说起

问题定义

给定一个包含 N 个 d 维向量的数据库 X = {x_1, x_2, …, x_N}，对于查询向量 q，找到 k 个与 q 距离最小的向量。距离度量通常是欧氏距离（L2）或余弦距离。

精确最近邻（Exact KNN）的暴力解法需要 O(Nd) 的时间复杂度——当 N = 10 亿、d = 768 时，单次查询需要数秒。工程上不可接受。

近似最近邻（Approximate Nearest Neighbor，ANN）允许返回”足够接近”的结果，将查询时间降低到亚线性甚至对数级别。评价指标有两个：

• Recall@k：返回的 k 个结果中，有多少是真正的 top-k 近邻。
• QPS（Queries Per Second）：每秒能处理多少次查询。

好的 ANN 算法要在 Recall 和 QPS 之间找到帕累托最优。

主流方法分类

ANN 算法大致分为四个流派：

图索引在 ANN-Benchmarks 上长期霸榜，HNSW 是其中的王者。

二、NSW：可导航小世界图

小世界现象

1998 年 Watts 和 Strogatz 发现，在一个规则网格上随机添加少量长程连接，就能将任意两点之间的平均最短路径从 O(N) 缩短到 O(log N)。这就是”小世界现象”——六度分隔理论的数学模型。

在图索引的语境下，如果我们构建一个近邻图（每个向量连接到它的 k 个最近邻），搜索算法可以从任意节点出发，贪心地走向距离查询点更近的邻居。问题是：纯近邻图容易形成局部簇，贪心搜索可能陷入局部最优。

NSW 的构建

NSW（Navigable Small World）的关键洞察：早期插入的节点会自然形成长程连接。

构建过程如下：

1. 将所有向量随机打乱顺序。
2. 依次插入每个向量 v：
   • 在当前图中执行贪心搜索，找到离 v 最近的 M 个节点。
   • 在 v 和这 M 个节点之间建立双向边。

为什么这能产生小世界结构？考虑前几个插入的节点——它们被插入时，图很小，“最近邻”实际上可能在向量空间中很远。这些”远程”边在图长大之后就变成了长程连接，充当高速公路。

插入顺序:  v1 -> v2 -> v3 -> ... -> vN

早期: v1 和 v2 距离可能很远，但被连接
     -> 后来变成了 "长程高速公路"

后期: v_{N-1} 和 v_N 周围已有很多节点
     -> 连接到真正的近邻，形成 "本地道路"

NSW 搜索

搜索算法是标准的贪心最佳优先搜索（Greedy Best-First Search）：

算法: NSW-Search(graph, query, ef)
输入: graph - NSW 图
      query - 查询向量
      ef    - 候选列表大小（搜索宽度）
输出: 距离 query 最近的 k 个节点

1. candidates = {随机选择一个入口节点}
2. visited = {}
3. result = {}
4. while candidates 非空:
5.     c = candidates 中离 query 最近的节点
6.     if dist(c, query) > dist(result 中最远的节点, query):
7.         break   // 无法再改进
8.     for each neighbor n of c:
9.         if n not in visited:
10.            visited.add(n)
11.            if |result| < ef or dist(n, query) < dist(result 中最远, query):
12.                candidates.add(n)
13.                result.add(n)
14.                if |result| > ef:
15.                    移除 result 中最远的节点
16. return result 中最近的 k 个节点

NSW 的问题

NSW 的搜索复杂度是多项式级的：O(N^{1/d} * log N)。在高维（d 大）时接近 O(log N)，但有一个根本问题——搜索路径的早期阶段非常低效。

从随机入口点到目标区域，贪心搜索需要穿越整个图。在 N = 100 万时，早期的”粗定位”阶段可能需要数百步，而每步都要计算距离——这些计算中的大部分都浪费在了远离目标的区域。

HNSW 的核心贡献就是用分层结构解决这个问题。

三、HNSW 的分层设计

跳表的类比

HNSW 的灵感来自跳表（Skip List）。在跳表中：

• Level 0 包含所有元素。
• Level 1 包含约 1/2 的元素。
• Level 2 包含约 1/4 的元素。
• 搜索从最高层开始，逐层下降，每层都跳过大量不需要比较的元素。

HNSW 将同样的思想应用到图上：

• Layer 0 包含所有向量，每个向量的最大邻居数为 M_max0（通常是 2*M）。
• Layer 1 包含约 1/mL 的向量（mL 是层乘子，通常 mL = 1/ln(M)）。
• Layer 2 包含约 1/mL^2 的向量。
• 以此类推，直到最高层只有少数几个向量。

Layer L (最高层):  ●───────────────────────────●
                   少量节点，长程连接

Layer 2:           ●────●──────●────────●──────●
                   更多节点，中程连接

Layer 1:           ●──●──●──●──●──●──●──●──●──●
                   较多节点，短程连接

Layer 0:           ●●●●●●●●●●●●●●●●●●●●●●●●●●●
                   所有节点，M_max0 个邻居

层分配

每个新插入的向量被分配一个随机层级 l，服从几何分布：

l = floor(-ln(uniform(0, 1)) * mL)

其中 mL = 1/ln(M)。这保证了：

• 大多数向量只存在于 Layer 0（概率约 1 - 1/M）。
• 少数向量被提升到高层，充当”高速公路”。
• 期望层数为 O(1)，最高层期望为 O(log_M(N))。

这和跳表的概率提升完全一致——区别在于每一层不是链表，而是一个近邻图。

为什么分层有效

分层带来了搜索复杂度从多项式到对数的飞跃。直觉上：

1. 高层：节点稀疏，边相当于长程跳跃。贪心搜索在高层快速定位到目标的大致区域，每步跳跃的”信息增益”很大。
2. 低层：节点密集，边连接近邻。搜索在低层精细定位，每步微调位置。
3. 分离关注点：粗定位和精细定位在不同层完成，互不干扰。

Malkov 和 Yashunin 在论文中证明了 HNSW 的搜索复杂度为 O(log N)，与 NSW 的多项式复杂度形成鲜明对比。

四、插入算法

完整流程

插入一个新向量 q 的过程：

算法: HNSW-Insert(hnsw, q, M, M_max, M_max0, efConstruction, mL)
输入: hnsw - HNSW 索引
      q    - 待插入的向量
      其余为超参数

1. l = floor(-ln(uniform(0, 1)) * mL)    // 随机层级
2. ep = hnsw.entry_point                  // 当前入口点
3. L  = hnsw.max_layer                    // 当前最高层

   // 阶段一：从最高层贪心下降到 l+1 层，只保留 1 个最近邻
4. for lc = L down to l+1:
5.     W = SEARCH-LAYER(hnsw, q, ep, ef=1, lc)
6.     ep = W 中离 q 最近的节点

   // 阶段二：从第 l 层到第 0 层，在每层找 efConstruction 个候选并连接
7. for lc = l down to 0:
8.     W = SEARCH-LAYER(hnsw, q, ep, efConstruction, lc)
9.     neighbors = SELECT-NEIGHBORS(q, W, M, lc)
10.    将 q 添加到第 lc 层
11.    for each n in neighbors:
12.        在 q 和 n 之间添加双向边
13.        if n 在第 lc 层的邻居数 > M_max (或 M_max0 for lc=0):
14.            收缩 n 的邻居列表（保留最近的 M_max 个）
15.    ep = W 中离 q 最近的节点

   // 如果新节点的层级高于当前最高层，更新入口点
16. if l > L:
17.    hnsw.entry_point = q
18.    hnsw.max_layer = l

SEARCH-LAYER

这是 HNSW 搜索的核心子程序，实现了在单层图上的 beam search：

算法: SEARCH-LAYER(hnsw, q, ep, ef, layer)
输入: q     - 查询向量
      ep    - 入口点（集合）
      ef    - 候选列表大小
      layer - 搜索的层

1. visited = {ep}
2. candidates = 小顶堆(ep)         // 按距离升序
3. result = 大顶堆(ep)             // 按距离降序，最远的在堆顶
4. while candidates 非空:
5.     c = candidates.pop_min()     // 取最近的候选
6.     f = result.peek_max()        // result 中最远的
7.     if dist(c, q) > dist(f, q):
8.         break                    // 所有候选都比当前最差结果更远
9.     for each neighbor e of c at layer:
10.        if e not in visited:
11.            visited.add(e)
12.            f = result.peek_max()
13.            if |result| < ef or dist(e, q) < dist(f, q):
14.                candidates.push(e)
15.                result.push(e)
16.                if |result| > ef:
17.                    result.pop_max()   // 弹出最远的
18. return result

SELECT-NEIGHBORS：简单版 vs 启发式版

简单版：直接返回候选集中距离 q 最近的 M 个节点。

启发式版（论文推荐）：优先选择那些”从不同方向接近 q”的邻居，而不仅仅是距离最近的。具体地，按距离排序后依次考虑每个候选 e：只有当 e 比已选中的任何邻居都更接近 q 时，才将 e 加入结果。

算法: SELECT-NEIGHBORS-HEURISTIC(q, candidates, M)
1. result = {}
2. 对 candidates 按 dist(., q) 升序排序
3. for each e in candidates:
4.     if |result| >= M:
5.         break
6.     if e 比 result 中所有已选节点都更接近 q:
7.         result.add(e)
8.        // 即: dist(e, q) < min_{r in result} dist(e, r)
9. return result

启发式选择的好处是避免所有邻居都聚集在同一个方向，提高图的连通性和搜索的多样性。这对低维数据尤其重要——在高维空间中，由于维度诅咒，向量在各个方向上都比较均匀，简单版已经足够好。

五、搜索算法

K-NN 搜索

HNSW 的 k 最近邻搜索建立在上述子程序之上：

算法: HNSW-KNN-Search(hnsw, q, K, ef)
输入: q  - 查询向量
      K  - 返回的近邻数
      ef - 搜索宽度（ef >= K）

1. ep = hnsw.entry_point
2. L  = hnsw.max_layer

   // 从最高层到第 1 层：贪心搜索，每层只保留 1 个最近邻
3. for lc = L down to 1:
4.     W = SEARCH-LAYER(hnsw, q, ep, ef=1, lc)
5.     ep = W 中离 q 最近的节点

   // 在第 0 层：beam search，搜索宽度为 ef
6. W = SEARCH-LAYER(hnsw, q, ep, ef, layer=0)
7. return W 中最近的 K 个节点

搜索的核心特点：

• 上层贪心，底层 beam：上层只需要快速定位大致区域，所以 ef=1 就够了。底层需要高精度，所以使用完整的 beam search。
• ef 控制精度-速度权衡：ef 越大，搜索越精确（候选越多）但越慢。通常 ef 在 64 到 500 之间。
• 距离计算次数：大部分距离计算发生在 Layer 0。上层的搜索步数只有 O(log N)，代价几乎可以忽略。

搜索复杂度分析

HNSW 搜索的期望复杂度：

• 上层搜索：每层 O(1) 个距离计算，共 O(log N) 层，总计 O(log N)。
• Layer 0 搜索：O(ef * M) 个距离计算。
• 总计：O(log N + ef * M)。

由于 ef 和 M 都是常数（与 N 无关），搜索复杂度为 O(log N)。但在实践中，距离计算的常数因子很重要——每次距离计算需要 O(d) 次浮点运算。

六、参数调优

关键参数

HNSW 有四个核心参数：

M 的影响

M 是最重要的参数，直接控制图的密度和搜索质量：

M 偏小：图太稀疏，连通性不足，搜索容易陷入局部最优。尤其在有聚类结构的数据上，不同簇之间可能断连。

M 偏大：图太密集，每步搜索要计算更多距离，拖慢速度。同时内存开销线性增长：每个向量存储 M 个邻居 ID（4 字节 int），M=64 时每向量额外 256 字节。

经验法则：对 128 维数据，M=16 通常够用；对 768 维数据（BERT 嵌入），M=32 可能更好。

efConstruction 的影响

efConstruction 控制构建时搜索候选的数量。越大，找到的邻居质量越高，但构建越慢。

efConstruction 与构建时间的关系（SIFT1M, M=16）：

efConstruction  构建时间   Recall@10 (ef=50)
     64           35s         0.92
    128           62s         0.95
    200          101s         0.97
    400          195s         0.98
    800          380s         0.985

efConstruction 只影响构建质量，不影响查询速度。因此：构建时尽量用大的 efConstruction（时间允许的话）。一般设为 M 的 10-20 倍。

ef 的影响

ef 是查询时最重要的旋钮，实时调整精度-速度权衡：

ef 与查询性能的关系（SIFT1M, M=16, efConstruction=200）：

ef    Recall@10    QPS (单线程)
10      0.82        12000
50      0.97         4200
100     0.99         2300
200     0.997        1200
500     0.999         500

在生产环境中，ef 通常按 SLA 需求设定：如果要求 99% 的 Recall@10，ef=100 左右；如果要求 99.9%，需要 ef=200 以上。

mL 层乘子

mL = 1/ln(M) 是论文推荐的最优值。实践中很少需要调整。mL 越大，高层节点越多，搜索越快但内存越大；mL 越小，高层节点越少，搜索的”粗定位”阶段变慢。

七、距离计算优化

距离计算是 HNSW 的性能瓶颈。对于 d=768 的向量，一次 L2 距离计算需要 768 次乘法和 768 次加法。优化手段包括：

SIMD 加速

使用 SIMD（Single Instruction, Multiple Data）指令并行计算多个维度的距离：

#include <immintrin.h>

float l2_distance_avx2(const float *a, const float *b, int dim) {
    __m256 sum = _mm256_setzero_ps();
    int i = 0;
    for (; i + 7 < dim; i += 8) {
        __m256 va = _mm256_loadu_ps(a + i);
        __m256 vb = _mm256_loadu_ps(b + i);
        __m256 diff = _mm256_sub_ps(va, vb);
        sum = _mm256_fmadd_ps(diff, diff, sum);
    }
    /* 水平归约 */
    __m128 hi = _mm256_extractf128_ps(sum, 1);
    __m128 lo = _mm256_castps256_ps128(sum);
    __m128 s = _mm_add_ps(hi, lo);
    s = _mm_hadd_ps(s, s);
    s = _mm_hadd_ps(s, s);
    float result;
    _mm_store_ss(&result, s);
    /* 处理剩余维度 */
    for (; i < dim; i++) {
        float d = a[i] - b[i];
        result += d * d;
    }
    return result;
}

AVX-256 可以一次处理 8 个 float，理论上 8 倍加速。AVX-512 可以处理 16 个。Faiss 的 HNSW 实现默认使用 SIMD。

PQ 预过滤

在 HNSW 搜索过程中，大量距离计算其实只是为了判断”这个候选值不值得进入结果集”。可以先用低精度的距离估计快速过滤，只对通过过滤的候选计算精确距离。

乘积量化（PQ）预过滤：

1. 将 d 维向量分成 m 个子空间，每个子空间 d/m 维。
2. 对每个子空间独立做 k-means 聚类（通常 k=256），得到码本。
3. 每个向量用 m 个字节编码（每个子空间一个聚类中心 ID）。
4. 预计算查询向量到所有聚类中心的距离表。
5. PQ 距离只需查 m 次表并求和，复杂度 O(m) 而非 O(d)。

原始距离计算:  O(d) = O(768)  浮点运算
PQ 距离估计:   O(m) = O(96)   查表+加法
加速比:        约 8x

两阶段搜索：用 PQ 距离做 beam search，对最终候选集用精确距离重排。这种策略在 Faiss 的 HNSW+PQ 实现中被广泛使用。

内存预取

HNSW 的搜索模式对缓存非常不友好——每次跳转到一个新邻居节点，都需要读取该节点的向量数据和邻居列表，几乎必然 cache miss。

使用软件预取（prefetch）可以在处理当前节点时，提前将下一个节点的数据加载到缓存：

/* 在遍历当前节点的邻居列表时，预取下一个邻居的数据 */
for (int i = 0; i < num_neighbors; i++) {
    int neighbor_id = neighbors[i];
    /* 预取下一个邻居的向量数据 */
    if (i + 1 < num_neighbors) {
        __builtin_prefetch(vectors + neighbors[i + 1] * dim, 0, 1);
    }
    float dist = l2_distance(query, vectors + neighbor_id * dim, dim);
    /* ... 更新候选集 ... */
}

八、C 语言实现

以下是 HNSW 核心算法的 C 语言实现，包含图结构、插入、搜索三个部分。为了清晰起见，省略了错误处理和内存管理细节。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <float.h>

#define MAX_LAYERS   16
#define M_DEFAULT    16
#define M_MAX0       32
#define EF_CONSTRUCTION 200

typedef struct {
    int    id;
    int    layer;                       /* 该节点的最高层 */
    int    num_neighbors[MAX_LAYERS];   /* 每层的邻居数 */
    int   *neighbors[MAX_LAYERS];       /* 每层的邻居 ID 列表 */
    float *vector;                      /* d 维向量 */
} HnswNode;

typedef struct {
    HnswNode *nodes;
    int    num_nodes;
    int    max_nodes;
    int    dim;
    int    max_layer;
    int    entry_point;
    int    M;
    int    M_max0;
    int    ef_construction;
    float  mL;
} HnswIndex;

/* ---- 辅助结构：最大堆和最小堆 ---- */
typedef struct { int id; float dist; } HeapItem;
typedef struct {
    HeapItem *data;
    int size, cap;
} Heap;

static Heap *heap_new(int cap) {
    Heap *h = calloc(1, sizeof(Heap));
    h->data = malloc(sizeof(HeapItem) * cap);
    h->cap = cap;
    return h;
}

static void heap_free(Heap *h) { free(h->data); free(h); }

static void swap_item(HeapItem *a, HeapItem *b) {
    HeapItem t = *a; *a = *b; *b = t;
}

/* 最小堆：candidates 用，取最近的候选 */
static void min_heap_push(Heap *h, int id, float dist) {
    h->data[h->size] = (HeapItem){id, dist};
    int i = h->size++;
    while (i > 0) {
        int p = (i - 1) / 2;
        if (h->data[p].dist <= h->data[i].dist) break;
        swap_item(&h->data[p], &h->data[i]);
        i = p;
    }
}

static HeapItem min_heap_pop(Heap *h) {
    HeapItem top = h->data[0];
    h->data[0] = h->data[--h->size];
    int i = 0;
    for (;;) {
        int s = i, l = 2*i+1, r = 2*i+2;
        if (l < h->size && h->data[l].dist < h->data[s].dist) s = l;
        if (r < h->size && h->data[r].dist < h->data[s].dist) s = r;
        if (s == i) break;
        swap_item(&h->data[i], &h->data[s]);
        i = s;
    }
    return top;
}

/* 最大堆：result 用，弹出最远的结果 */
static void max_heap_push(Heap *h, int id, float dist) {
    h->data[h->size] = (HeapItem){id, dist};
    int i = h->size++;
    while (i > 0) {
        int p = (i - 1) / 2;
        if (h->data[p].dist >= h->data[i].dist) break;
        swap_item(&h->data[p], &h->data[i]);
        i = p;
    }
}

static HeapItem max_heap_pop(Heap *h) {
    HeapItem top = h->data[0];
    h->data[0] = h->data[--h->size];
    int i = 0;
    for (;;) {
        int s = i, l = 2*i+1, r = 2*i+2;
        if (l < h->size && h->data[l].dist > h->data[s].dist) s = l;
        if (r < h->size && h->data[r].dist > h->data[s].dist) s = r;
        if (s == i) break;
        swap_item(&h->data[i], &h->data[s]);
        i = s;
    }
    return top;
}

/* ---- 距离计算 ---- */
static float l2_dist(const float *a, const float *b, int dim) {
    float sum = 0.0f;
    for (int i = 0; i < dim; i++) {
        float d = a[i] - b[i];
        sum += d * d;
    }
    return sum;
}

/* ---- visited 标记（简易位图） ---- */
static char *visited_new(int n) { return calloc(n, 1); }
static void  visited_free(char *v) { free(v); }

/* ---- 随机层级 ---- */
static int random_layer(float mL) {
    double r = (double)rand() / RAND_MAX;
    if (r == 0.0) r = 1e-9;
    return (int)(-log(r) * mL);
}

/* ---- 核心：单层搜索 ---- */
static Heap *search_layer(HnswIndex *idx, const float *query,
                          int entry_id, int ef, int layer) {
    float entry_dist = l2_dist(query, idx->nodes[entry_id].vector, idx->dim);
    Heap *candidates = heap_new(ef + 128);
    Heap *result     = heap_new(ef + 128);
    char *visited    = visited_new(idx->max_nodes);

    min_heap_push(candidates, entry_id, entry_dist);
    max_heap_push(result, entry_id, entry_dist);
    visited[entry_id] = 1;

    while (candidates->size > 0) {
        HeapItem c = min_heap_pop(candidates);
        float f_dist = result->data[0].dist; /* 最大堆堆顶 = 最远结果 */
        if (c.dist > f_dist)
            break;

        HnswNode *node = &idx->nodes[c.id];
        int nn = node->num_neighbors[layer];
        for (int i = 0; i < nn; i++) {
            int nid = node->neighbors[layer][i];
            if (visited[nid]) continue;
            visited[nid] = 1;

            float d = l2_dist(query, idx->nodes[nid].vector, idx->dim);
            f_dist = result->data[0].dist;

            if (result->size < ef || d < f_dist) {
                min_heap_push(candidates, nid, d);
                max_heap_push(result, nid, d);
                if (result->size > ef)
                    max_heap_pop(result);
            }
        }
    }
    heap_free(candidates);
    visited_free(visited);
    return result; /* 调用方负责释放 */
}

/* ---- 为节点添加邻居 ---- */
static void add_neighbor(HnswNode *node, int layer, int neighbor_id, int max_m) {
    int n = node->num_neighbors[layer];
    if (n < max_m) {
        node->neighbors[layer][n] = neighbor_id;
        node->num_neighbors[layer] = n + 1;
    }
}

/* ---- 收缩邻居列表：保留距离最近的 max_m 个 ---- */
static void shrink_neighbors(HnswIndex *idx, int node_id,
                             int layer, int max_m) {
    HnswNode *node = &idx->nodes[node_id];
    int n = node->num_neighbors[layer];
    if (n <= max_m) return;

    /* 计算每个邻居到 node 的距离 */
    HeapItem *items = malloc(sizeof(HeapItem) * n);
    for (int i = 0; i < n; i++) {
        int nid = node->neighbors[layer][i];
        items[i].id = nid;
        items[i].dist = l2_dist(idx->nodes[node_id].vector,
                                idx->nodes[nid].vector, idx->dim);
    }
    /* 简单选择排序取前 max_m 个（生产中应该用 nth_element） */
    for (int i = 0; i < max_m; i++) {
        int best = i;
        for (int j = i + 1; j < n; j++) {
            if (items[j].dist < items[best].dist) best = j;
        }
        HeapItem tmp = items[i]; items[i] = items[best]; items[best] = tmp;
    }
    for (int i = 0; i < max_m; i++)
        node->neighbors[layer][i] = items[i].id;
    node->num_neighbors[layer] = max_m;
    free(items);
}

/* ---- 初始化索引 ---- */
HnswIndex *hnsw_new(int dim, int max_nodes, int M) {
    HnswIndex *idx = calloc(1, sizeof(HnswIndex));
    idx->dim = dim;
    idx->max_nodes = max_nodes;
    idx->nodes = calloc(max_nodes, sizeof(HnswNode));
    idx->M = M;
    idx->M_max0 = 2 * M;
    idx->ef_construction = EF_CONSTRUCTION;
    idx->mL = 1.0 / log((double)M);
    idx->entry_point = -1;
    idx->max_layer = -1;
    return idx;
}

/* ---- 插入 ---- */
void hnsw_insert(HnswIndex *idx, int id, const float *vec) {
    HnswNode *q = &idx->nodes[id];
    q->id = id;
    q->vector = malloc(sizeof(float) * idx->dim);
    memcpy(q->vector, vec, sizeof(float) * idx->dim);

    int l = random_layer(idx->mL);
    if (l >= MAX_LAYERS) l = MAX_LAYERS - 1;
    q->layer = l;

    for (int i = 0; i <= l; i++) {
        int cap = (i == 0) ? idx->M_max0 : idx->M;
        q->neighbors[i] = calloc(cap, sizeof(int));
    }

    if (idx->entry_point < 0) {
        idx->entry_point = id;
        idx->max_layer = l;
        idx->num_nodes = 1;
        return;
    }

    int ep = idx->entry_point;
    int L  = idx->max_layer;

    /* 阶段一：贪心下降 */
    for (int lc = L; lc > l; lc--) {
        Heap *W = search_layer(idx, vec, ep, 1, lc);
        if (W->size > 0) ep = W->data[0].id; /* 只有 1 个结果 */
        heap_free(W);
    }

    /* 阶段二：逐层搜索并连接 */
    int top = (l < L) ? l : L;
    for (int lc = top; lc >= 0; lc--) {
        Heap *W = search_layer(idx, vec, ep, idx->ef_construction, lc);
        int max_m = (lc == 0) ? idx->M_max0 : idx->M;

        /* 选择最近的 M 个邻居 */
        int sel = (W->size < idx->M) ? W->size : idx->M;
        HeapItem *sorted = malloc(sizeof(HeapItem) * W->size);
        int cnt = W->size;
        for (int i = 0; i < cnt; i++)
            sorted[i] = W->data[i];
        /* 按距离排序 */
        for (int i = 0; i < sel; i++) {
            int best = i;
            for (int j = i + 1; j < cnt; j++)
                if (sorted[j].dist < sorted[best].dist) best = j;
            HeapItem tmp = sorted[i]; sorted[i] = sorted[best]; sorted[best] = tmp;
        }

        for (int i = 0; i < sel; i++) {
            int nid = sorted[i].id;
            add_neighbor(q, lc, nid, max_m);
            add_neighbor(&idx->nodes[nid], lc, id, max_m);
            if (idx->nodes[nid].num_neighbors[lc] > max_m)
                shrink_neighbors(idx, nid, lc, max_m);
        }

        /* 更新 ep 为本层最近的结果 */
        if (cnt > 0) ep = sorted[0].id;
        free(sorted);
        heap_free(W);
    }

    if (l > L) {
        idx->entry_point = id;
        idx->max_layer = l;
    }
    idx->num_nodes++;
}

/* ---- K-NN 搜索 ---- */
int *hnsw_search(HnswIndex *idx, const float *query, int k, int ef) {
    if (idx->entry_point < 0) return NULL;

    int ep = idx->entry_point;
    int L  = idx->max_layer;

    for (int lc = L; lc > 0; lc--) {
        Heap *W = search_layer(idx, query, ep, 1, lc);
        if (W->size > 0) ep = W->data[0].id;
        heap_free(W);
    }

    Heap *W = search_layer(idx, query, ep, ef, 0);

    /* 提取最近的 k 个 */
    int *result = malloc(sizeof(int) * k);
    int cnt = (W->size < k) ? W->size : k;
    /* 将最大堆转换为有序结果 */
    HeapItem *arr = malloc(sizeof(HeapItem) * W->size);
    for (int i = 0; i < W->size; i++) arr[i] = W->data[i];
    for (int i = 0; i < cnt; i++) {
        int best = i;
        for (int j = i + 1; j < W->size; j++)
            if (arr[j].dist < arr[best].dist) best = j;
        HeapItem tmp = arr[i]; arr[i] = arr[best]; arr[best] = tmp;
        result[i] = arr[i].id;
    }
    free(arr);
    heap_free(W);
    return result;
}

这段代码实现了 HNSW 的完整生命周期：创建索引、逐条插入向量、执行 K-NN 搜索。核心函数 search_layer 大约 40 行，实现了论文中的 Algorithm 2。

几个关键实现细节：

1. visited 数组使用简单的 char 数组而非位图，牺牲少量空间换取更快的访问速度。生产实现中通常使用 per-query 的递增计数器，避免每次搜索都 memset。
2. 邻居收缩使用了简单的选择排序。生产代码应该使用 std::nth_element 或 Floyd-Rivest 算法。
3. 内存分配非常粗糙——每个节点的向量和邻居列表都是独立 malloc 的。生产实现会使用大块内存池，将同一层的邻居列表紧凑排列以提高缓存命中率。

九、Vamana：DiskANN 的图索引

设计动机

HNSW 的主要缺点是内存消耗大。对于 N = 10 亿、d = 128 的数据集：

向量数据:  10^9 * 128 * 4 bytes = 512 GB
邻居列表:  10^9 * 32 * 4 bytes  =  128 GB (M=16, 含 M_max0)
总计:      约 640 GB

这远超单机内存容量。Microsoft Research 的 DiskANN（2019）提出了 Vamana 图索引，专为磁盘场景设计。

Vamana 的核心改进

单层图，有界出度（bounded degree）：Vamana 不使用分层结构，而是构建一个单层的有向图，每个节点的出度严格限制为 R（通常 R=64 或 R=128）。

RobustPrune 算法：Vamana 的邻居选择算法比 HNSW 的启发式更激进。给定候选集 V 和参数 alpha >= 1：

算法: RobustPrune(node p, candidates V, alpha, R)
1. V = V union neighbors(p)  // 合并现有邻居
2. neighbors(p) = {}
3. while V 非空 and |neighbors(p)| < R:
4.     p* = argmin_{v in V} dist(p, v)
5.     neighbors(p).add(p*)
6.     for each v in V:
7.         if alpha * dist(p*, v) <= dist(p, v):
8.             V.remove(v)   // v 被 p* "覆盖"了

alpha > 1 使得 RobustPrune 更倾向于保留长程连接（因为只有当 alpha * dist(p*, v) <= dist(p, v) 时才剪枝，alpha 越大剪枝越不激烈）。这在单层图中至关重要——没有高层的长程高速公路，就需要在单层中显式保留远距离边。

中位数起点：Vamana 使用数据集的中位数向量作为搜索入口点，而非随机选取。这保证了入口点大致在数据分布的中心，减少了搜索的初始距离。

HNSW vs Vamana

Vamana 将每个节点的向量和邻居列表存储在连续的磁盘块中，使得一次 SSD 读取（4KB 页）就能获取搜索所需的所有信息。这是它在磁盘场景下性能优异的关键。

DiskANN 的完整架构

DiskANN 在 Vamana 图之上还叠加了 PQ 压缩：

1. 将全精度向量存储在 SSD 上。
2. 在内存中保留每个向量的 PQ 编码（每向量只需几十字节）。
3. 搜索时先用 PQ 距离做粗排，减少磁盘访问次数。
4. 对 PQ 筛选后的候选，批量读取 SSD 上的全精度向量做精排。

这种”内存 PQ + 磁盘全精度”的架构可以在单台机器上索引 10 亿级向量。

十、Benchmark：HNSW vs IVF-PQ vs LSH

实验设置

测试环境：单台 x86-64 服务器，64 核 AMD EPYC，256GB 内存。单线程查询。

SIFT1M 结果

算法             Recall@10   QPS      构建时间   内存 (MB)
--------------------------------------------------------------
HNSW (M=16)        0.98     4,200      95s        560
HNSW (M=32)        0.99     2,800     210s        820
IVF-PQ (nlist=1k)  0.72    12,000      45s        150
IVF-PQ (nlist=4k)  0.80     8,500      62s        160
IVF-PQ + Refine    0.91     3,200      65s        680
LSH (128 tables)   0.65     5,500      38s        900
LSH (256 tables)   0.78     2,800      75s       1800
Flat (暴力)        1.00       120       -         512

GIST1M 结果

算法             Recall@10   QPS      构建时间   内存 (MB)
--------------------------------------------------------------
HNSW (M=32)        0.97       850     620s       4200
HNSW (M=64)        0.99       420    1400s       5800
IVF-PQ (nlist=4k)  0.55     3,500     180s        320
IVF-PQ + Refine    0.78     1,200     185s       4000
LSH (256 tables)   0.42       800     120s       7200
Flat (暴力)        1.00        15       -        3840

关键结论

1. HNSW 在高召回率区间一骑绝尘。当要求 Recall@10 >= 0.95 时，HNSW 的 QPS 远超其他方法。
2. IVF-PQ 在低召回率/大规模场景有优势。如果允许 Recall = 0.7-0.8 且内存受限，IVF-PQ 是更好的选择。
3. LSH 在高维数据上表现最差。维度越高，LSH 需要的哈希表越多，内存爆炸且召回率仍然不高。
4. 高维度放大了差距。从 128 维到 960 维，HNSW 的优势更加明显。这是因为图索引的搜索复杂度对维度不敏感（O(log N * ef * M * d)），而 LSH 的哈希表数量随维度快速增长。

精度-速度帕累托前沿

在 ANN-Benchmarks（ann-benchmarks.com）上，HNSW 几乎在所有数据集上占据帕累托前沿。唯一能与之竞争的是 ScaNN（Google）在某些特定数据集上利用各向异性量化获得了更好的权衡。

十一、工业实践

主流系统中的 HNSW

Faiss 的 HNSW 用法

import faiss
import numpy as np

dim = 128
nb = 1000000
nq = 10000

# 生成数据
xb = np.random.random((nb, dim)).astype('float32')
xq = np.random.random((nq, dim)).astype('float32')

# 创建 HNSW 索引
M = 32
index = faiss.IndexHNSWFlat(dim, M)
index.hnsw.efConstruction = 200
index.hnsw.efSearch = 64

# 构建索引
index.add(xb)

# 搜索
k = 10
distances, indices = index.search(xq, k)

Milvus 的 HNSW 配置

from pymilvus import Collection, CollectionSchema, FieldSchema, DataType

# 定义 schema
fields = [
    FieldSchema("id", DataType.INT64, is_primary=True),
    FieldSchema("embedding", DataType.FLOAT_VECTOR, dim=768),
]
schema = CollectionSchema(fields)
collection = Collection("articles", schema)

# 创建 HNSW 索引
index_params = {
    "metric_type": "L2",
    "index_type": "HNSW",
    "params": {"M": 16, "efConstruction": 256}
}
collection.create_index("embedding", index_params)

# 搜索
search_params = {"metric_type": "L2", "params": {"ef": 128}}
results = collection.search(
    data=[query_vector],
    anns_field="embedding",
    param=search_params,
    limit=10
)

工程踩坑表

十二、个人观点与总结

HNSW 为什么赢了

HNSW 击败树索引和哈希索引，核心原因有三：

第一，图结构天然适应数据分布。树索引是自顶向下的空间划分，依赖于维度的独立性假设。当维度超过 20，轴对齐的划分方式失去意义。图索引是自底向上的——每个节点连接到它的实际近邻，不做任何关于空间结构的假设。

第二，贪心搜索的效率惊人。在一个构建良好的近邻图上，贪心搜索的每一步都在缩小与目标的距离。搜索路径的长度是 O(log N)，而且路径上的每个节点都贡献了信息——没有浪费。相比之下，树索引在回溯时大量时间花在”验证分支不包含更近的点”上。

第三，分层设计的简洁优雅。跳表的思想被完美移植到图上：用概率分层替代确定性分层，用贪心搜索替代比较排序。这种设计几乎不引入额外复杂度，却将搜索效率从多项式提升到对数。

局限性

HNSW 不是万能的：

1. 内存消耗是最大的痛点。对于十亿级数据集，纯 HNSW 需要数百 GB 内存。DiskANN（Vamana + PQ）是更务实的选择。

2. 动态更新支持不佳。删除节点会破坏图的连通性，目前没有优雅的解决方案。工业界的做法是 segment compaction——将删除操作积累到一定量后重建索引。

3. 带过滤的搜索是一个 open problem。当搜索需要同时满足向量相似度和属性过滤条件时，HNSW 的图遍历会浪费大量时间在不满足过滤条件的节点上。

4. 构建成本高。M=32、efConstruction=200 时，构建一百万个 128 维向量需要约 3 分钟。十亿级数据需要数小时甚至数天。

未来方向

几个值得关注的趋势：

磁盘友好的图索引。DiskANN 已经证明了可行性。未来的方向是将 HNSW 的分层优势和 Vamana 的磁盘友好性结合起来。

学习型图索引。用神经网络学习数据分布，指导图的构建和搜索。例如，学习最优的入口点选择策略，或学习最优的邻居选择函数。

GPU 加速。HNSW 的搜索天然适合 GPU 并行——每个 CUDA 线程处理一个查询，同一 warp 内的线程可以共享距离计算的中间结果。NVIDIA 的 cuVS（前 RAFT）已经提供了 GPU HNSW 实现。

与大模型的协同。RAG（Retrieval-Augmented Generation）将向量检索推到了前所未有的热度。未来的向量索引需要支持更灵活的查询模式——多向量检索、上下文感知的相似度、动态更新的嵌入。

结语

HNSW 是那种”理论上优美，工程上也好用”的罕见算法。它的论文只有 20 页，核心思想可以用一句话概括——“在近邻图上叠加跳表的分层结构”——但这个简单的想法解决了高维近似最近邻搜索的核心难题。

从 2016 年发表至今，HNSW 已经经历了近十年的工业检验。它在 ANN-Benchmarks 上的统治地位至今无人撼动。当你在 ChatGPT 中提问、在 Spotify 中听推荐歌曲、在 Google 搜索中看到图片结果时，背后大概率有一个 HNSW 索引在毫秒级别完成了向量检索。

理解 HNSW 不仅是理解一个算法，更是理解”如何用简单的构建块组合出强大的系统”这一工程哲学。跳表的概率分层，小世界图的贪心导航，beam search 的候选管理——每个组件都不新，但组合在一起就产生了 1+1+1 > 3 的效果。

参考文献

1. Malkov, Y. A., & Yashunin, D. A. (2020). “Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs.” IEEE TPAMI, 42(4), 824-836.
2. Subramanya, S. J., Devvrit, F., Simhadri, H. V., Krishnawamy, R., & Kadekodi, R. (2019). “DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node.” NeurIPS.
3. Malkov, Y. A., & Ponomarenko, A. (2014). “Approximate Nearest Neighbor Algorithm Based on Navigable Small World Graphs.” Information Systems, 45, 61-68.
4. Guo, R., Sun, P., Lindgren, E., Geng, Q., Simcha, D., Chern, F., & Kumar, S. (2020). “Accelerating Large-Scale Inference with Anisotropic Vector Quantization.” ICML.
5. Johnson, J., Douze, M., & Jegou, H. (2019). “Billion-scale Similarity Search with GPUs.” IEEE TBD.
6. Watts, D. J., & Strogatz, S. H. (1998). “Collective Dynamics of ‘Small-World’ Networks.” Nature, 393(6684), 440-442.
7. Pugh, W. (1990). “Skip Lists: A Probabilistic Alternative to Balanced Trees.” Communications of the ACM, 33(6), 668-676.

上一篇: 局部敏感哈希 下一篇: 乘积量化与 IVF-PQ

相关阅读: - 并发跳表 - KD-tree