土法炼钢兴趣小组的算法知识备份

【数据库研究前沿】向量索引深度：HNSW、DiskANN、SPANN 原理对比

2026-04-21 · database · #vector-index #hnsw #diskann #spann #ivf-pq #scann #ann #faiss #milvus #pgvector #qdrant

文章导航

分类入口
database
标签入口
#vector-index#hnsw#diskann#spann#ivf-pq#scann#ann#faiss#milvus#pgvector#qdrant

源码下载

本文相关源码已整理，共 1 个文件。

打开下载目录 →

目录

向量检索的工程门槛，几乎完全压在索引结构上。暴力扫描在一百万条 768 维向量上还能跑，到一亿条就没人能等。而从一亿跳到十亿、百亿，问题性质又会再次切换：不再是”如何把内存里的图走得更快”，而是”当单机内存装不下所有向量时，怎么让一次查询只读几个磁盘页”。

过去十年，业界围绕这个问题给出了三条主线工程答案：内存图索引 HNSW、单机 SSD 图索引 DiskANN/Vamana，以及把倒排和图索引耦合起来的混合架构 SPANN。外加量化路线的 IVF-PQ 与 ScaNN，构成了当前主流向量数据库背后所有索引的原型。这篇文章不做综述堆砌，而是把这几个算法的核心定理、构建伪代码、查询路径、失效边界摆在一起对比，然后落到 FAISS、Milvus、pgvector、Qdrant 的参数选型，以及一个可跑的 numpy HNSW 最小实现。

系列的上一篇 DB-as-Memory：数据库作为 LLM 外挂记忆 讨论了”为什么数据库要做向量”；存储工程系列的 向量存储与 ANN 索引 已经覆盖过向量存储的基础概念（暴力搜索、KD-Tree、LSH、量化）。本文不重复这些内容，直接进入索引结构的深度对比。

一、ANN 问题定义与三角权衡

1.1 精确 NN 与近似 NN

给定向量集合 \(X = \{x_1, x_2, \dots, x_n\} \subset \mathbb{R}^d\)，距离函数 \(\text{dist}(\cdot, \cdot)\)（通常是欧氏距离 \(L_2\) 或余弦距离 \(1 - \cos\)），对查询向量 \(q\)，最近邻搜索（Nearest Neighbor, NN）是求：

NN(q) = argmin_{x ∈ X} dist(q, x)
Top-k NN(q) = 集合 X 中距离 q 最小的 k 个向量

当 \(n\) 和 \(d\) 都很大时，精确 NN 是困难问题。“维度灾难”（Curse of Dimensionality）可以严格证明：当 \(d \to \infty\)，基于空间划分的精确索引（如 KD-Tree、R-Tree）退化到近似线性扫描。Indyk 和 Motwani 在 1998 年的工作给出了近似最近邻（Approximate Nearest Neighbor, ANN）的正式定义：

\(c\)-近似最近邻：给定 \(c > 1\)，返回的结果 \(x^*\) 满足 \(\text{dist}(q, x^*) \le c \cdot \text{dist}(q, \text{NN}(q))\)。

工程系统里更常用的指标是召回率（Recall）：

Recall@k = |返回的 Top-k ∩ 真实 Top-k| / k

真实 Top-k 由暴力搜索产生。工业界常见的验收标准是 ≥ 0.95 或 0.99。

1.2 召回率、QPS、内存的三角

所有 ANN 索引都在三个指标之间做折中：

这三个指标不能同时最优。HNSW 通常用高内存换取高 QPS 和高 Recall；DiskANN 用磁盘换内存，牺牲少量延迟；IVF-PQ 通过量化压缩内存，但在高 Recall 段衰减明显。基准测试项目 ann-benchmarks（Aumüller et al., 2020）用 Recall–QPS 曲线把这种折中可视化，是选型时的参考起点。

1.3 距离函数的工程细节

距离度量决定了索引构建和查询的所有距离计算，也决定了是否可以用 SIMD 加速、是否可以只存向量范数、是否需要归一化。常见三种：

这些细节对召回率影响很大。常见的”升级到新模型后召回掉 5 个点”多半是忘记归一化或度量不一致。

1.4 评估方法论

评估 ANN 索引至少要说明五件事：数据集（GIST-1M、SIFT-1M、Deep-1B、BigANN）、距离度量、构建参数、查询参数、硬件配置。只说”HNSW 在 M=16 下达到 95% 召回”没有意义，因为同样的 M=16 在 SIFT-1M 和 Deep-10M 上的表现可能差一个数量级。

ann-benchmarks（Aumüller et al.）项目用统一的 Docker 镜像跑几十个算法，并报告 Recall–QPS 曲线。Big-ANN-Benchmarks（NeurIPS 2021、2023 竞赛）则专门面向十亿规模，覆盖了 DiskANN、SPANN、ScaNN、各种量化变体，是目前最严肃的基准之一。本文后文给参数建议时都会指明数据规模。

二、HNSW：分层可导航小世界图

HNSW（Hierarchical Navigable Small World）由 Yury Malkov 和 Dmitry Yashunin 在 2018 年的 TPAMI 论文中正式发表，是当前最广泛使用的内存 ANN 索引。它的前身是 Malkov 2014 年的 NSW（Navigable Small World）。

2.1 小世界图的基本直觉

可导航小世界图（Navigable Small World Graph）是一类特殊的近邻图：节点度数有限，但图的直径是 \(O(\log n)\)，并且贪心路由（每一步选最接近目标的邻居）能以高概率找到真正的最近邻。这种性质来自 Jon Kleinberg 2000 年关于小世界网络的理论工作——在均匀随机的近邻连接之外，额外添加按距离幂律分布的”长程边”（Long-range Link），就能让贪心路由在多项式对数时间内收敛。

HNSW 把这个思路推到分层结构：层数越高的图越稀疏，包含的”长程边”越多；底层图稠密，包含全部节点。查询从顶层开始贪心下行，最终在底层做精细搜索。

Layer 2 (稀疏):   o----------o----o
                  |          |    |
Layer 1 (中等):   o--o---o---o--o-o
                  |  |   |   |  | |
Layer 0 (稠密):   o--o-o-o-o-o-o-o-o (所有节点)

每个节点被分配一个最大层号 \(l\)，分布服从指数衰减：\(P(l = k) = e^{-k/m_L} (1 - e^{-1/m_L})\)，其中 \(m_L\) 是归一化常数（论文里 \(m_L = 1/\ln M\)）。节点同时出现在 \(0, 1, \dots, l\) 的每一层，只在最大层及以下才有出边。

2.2 构建算法

HNSW 构建是逐点插入的过程。关键参数：

插入一个节点 \(x\) 的伪代码：

def insert(hnsw, x):
    l = sample_level(m_L)                      # 为 x 采样最大层号
    ep = hnsw.entry_point                      # 从全局入口开始
    L = hnsw.top_level
    # 自顶向下：在高于 l 的每层做贪心搜索，只保留当前最近点作为下一层入口
    for lc in range(L, l, -1):
        ep = greedy_search(x, ep, ef=1, layer=lc)
    # 在 l 及以下每层：找到 efConstruction 个候选并连边
    for lc in range(min(L, l), -1, -1):
        W = search_layer(x, ep, ef=efConstruction, layer=lc)
        neighbors = select_neighbors(x, W, M if lc > 0 else M0)
        add_bidirectional_links(x, neighbors, layer=lc)
        # 反向剪枝：若邻居的出度超过上限，用 select_neighbors 裁剪
        for n in neighbors:
            if degree(n, lc) > max_degree(lc):
                prune(n, lc)
        ep = W
    if l > L:
        hnsw.entry_point = x
        hnsw.top_level = l

search_layer(x, ep, ef, lc) 在第 \(lc\) 层做贪心扩展：维护候选堆 \(C\)（最小堆，按到 \(x\) 的距离）和结果堆 \(W\)（最大堆，size 上限 \(ef\)），反复从 \(C\) 弹出最近点、扩展其邻居，直到 \(C\) 中的最小距离大于 \(W\) 中的最大距离为止。

select_neighbors 在 HNSW 论文里给出了两种策略：简单的取 Top-\(M\)（selectNeighborsSimple）和启发式的 selectNeighborsHeuristic。后者的核心观察是：如果候选 \(c_i\) 到已选邻居 \(c_j\) 的距离比到 \(x\) 的距离还近，那么 \(c_i\) 更应该连向 \(c_j\) 而不是 \(x\)——这条边是”冗余”的。启发式会跳过这类冗余边，保留方向分散的邻居，实验表明这对高维、聚类数据非常关键。

2.3 查询算法

查询流程几乎是构建的子集：自顶向下用 \(ef=1\) 贪心下行到第 0 层，然后在第 0 层用 search_layer 以 \(efSearch\) 大小搜索，返回距离最近的 \(k\) 个。

def search(hnsw, q, k, efSearch):
    ep = hnsw.entry_point
    for lc in range(hnsw.top_level, 0, -1):
        ep = greedy_search(q, ep, ef=1, layer=lc)
    W = search_layer(q, ep, ef=efSearch, layer=0)
    return top_k_closest(W, k)

\(efSearch\) 必须 \(\ge k\)。增大 \(efSearch\) 单调提高召回率，但延迟也线性上升——这是 HNSW 最重要的运行时调参旋钮。

2.4 参数经验值

根据 hnswlib（HNSW 作者官方实现）文档和 ann-benchmarks 数据：

数据规模 \(M\) \(efConstruction\) 起始 \(efSearch\)
1 万–10 万 16 100 50
100 万 16–32 200 100
1000 万 32–48 400 200–400
1 亿 48–64 500 400–800

经验规则：

2.5 HNSW 的工程痛点

这些痛点直接催生了 DiskANN 和 SPANN。

2.6 HNSW 家族中的近亲：NSW、NSG、KGraph

HNSW 并非”图索引”的唯一代表，在它之前与之后都有重要的变体：

工程上最常见的仍是 HNSW：它的参数调优成熟、开源实现多、分析工具齐全。NSG 适合”离线建索引一次、在线只查询、追求极高召回”的场景。

2.7 HNSW 的长期维护与删除问题

HNSW 索引是”慢慢腐烂”的：

这些问题在纯静态索引时代不明显，但在 online vector service 里构成了持续的运维成本。HNSW 的”动态性优化”是学术界仍在推进的开放问题。

2.8 为什么 HNSW 在工业界几乎是默认选择

尽管 HNSW 在论文里只是 2016 年提出的（Malkov 的 NSW 更早），但到 2024 年，它在工业界接近默认状态。原因有几个：

HNSW 的”统治力”也意味着它成了后续研究的对照组——几乎每一篇 ANN 论文都会在 HNSW 参数最优点上与自己比较。这反过来也让其他算法难以撼动 HNSW 的地位：一个稍微更好的图结构，可能在工程成熟度上远不如老牌 HNSW。

2.9 Python 封装层的隐形成本

hnswlib、faiss、usearch 等库都有 Python 绑定，但使用方式会显著影响性能：

三、DiskANN / Vamana：单机 SSD 上的十亿级向量

DiskANN 由微软印度研究院 Subramanya 等人在 2019 年 NeurIPS 发表。核心贡献是提出了新的图索引 Vamana，并给出了一套 SSD 友好的查询布局，使得单机 64 GB 内存 + 一块 NVMe SSD 就能服务十亿级向量的 ANN 查询。

3.1 为什么 HNSW 不能直接放到 SSD

把 HNSW 的邻接表刷到磁盘，看起来是一件自然的事，但实际上不可行：

DiskANN 的回应是：砍掉层次结构，改用单层图；强制图度数上限；把每个节点的邻接表和向量打包在一个 SSD 扇区内；查询时用 beam search 做批量预取。

3.2 Vamana 图：RobustPrune 剪枝

Vamana 只有一层图，每个节点度数上限固定为 \(R\)（论文里 \(R = 64 \sim 128\)）。构建过程：

  1. 用任意候选集（随机、或来自其他索引）作为初始图。
  2. 对每个节点 \(p\) 做一次贪心搜索，得到访问到的候选点集合 \(\mathcal{V}\)。
  3. 对 \(\mathcal{V}\) 调用 RobustPrune(p, V, α, R) 得到新的邻居集。
  4. 迭代两轮：第一轮 \(\alpha = 1\)，第二轮 \(\alpha = 1.2\)。

RobustPrune 的伪代码：

def RobustPrune(p, V, alpha, R):
    V = sorted(V, key=lambda v: dist(p, v))
    N = []
    while V and len(N) < R:
        p_star = V.pop(0)            # 取距离 p 最近的候选
        N.append(p_star)
        # 过滤掉被 p_star 占优的候选
        V = [v for v in V if alpha * dist(p_star, v) > dist(p, v)]
    return N

这个剪枝规则和 HNSW 的启发式选邻居非常像，但多了一个 \(\alpha \ge 1\) 的”松紧”参数。\(\alpha = 1\) 对应最严格的剪枝（HNSW 的原始启发式），更大的 \(\alpha\) 保留更多”次优”邻居，增加图的健壮性。论文证明 \(\alpha > 1\) 时图是”\(\alpha\)-可导航”的：贪心搜索能在 \(O(\log n)\) 步收敛到一个不劣于真值 \(\alpha\) 倍的解。

实测 Vamana 比 HNSW 在相同召回下邻居数可以少 30%–50%，这直接决定了能否把图塞进 SSD。

3.3 SSD 布局与查询

DiskANN 的磁盘格式：

查询流程（beam search，束宽 \(L\)）：

def disk_search(q, L, k):
    # 1. 从内存中的 PQ 码计算初始距离估计
    # 2. 维护候选堆 C 和结果堆 W，size = L
    # 3. 每次从 C 弹出最近点，读 SSD 拿到其邻接表 + 精度向量
    # 4. 用精度向量计算 q 到该点的真实距离，更新 W
    # 5. 用 PQ 估计邻居到 q 的距离，加入 C
    # 直到 C 中最小估计距离 > W 中最大真实距离

关键技巧：

论文报告：单机 64 GB 内存、1 块 NVMe，1 billion SIFT-1B 数据集上达到 95% ，QPS 约 5000，平均延迟约 5 ms。同等召回下纯内存索引的吞吐更高，但成本相差一个数量级。

3.4 FreshDiskANN：支持增量更新

原始 DiskANN 是静态索引。Singh 等人 2021 年的 FreshDiskANN 扩展了动态能力：

这个架构和 LSM-Tree 的设计哲学高度一致——前台 Memtable 吸收写入，后台 Compaction 合并到磁盘。FreshDiskANN 把 ANN 索引从静态工件变成了持续服务的数据库组件。

3.5 Vamana / DiskANN 参数与适用场景

参数 典型值 作用
\(R\) 64–128 图最大出度，决定 SSD 块大小
\(L_{\text{build}}\) 100–200 构建时的候选队列大小
\(\alpha\) 1.2 RobustPrune 松紧度
\(L_{\text{search}}\) 64–200 查询时 beam 宽度

适用场景：

不适用：

3.6 DiskANN 实现的几个工程细节

读 DiskANN 开源代码（microsoft/DiskANN）会发现几个容易被文章忽略但很关键的工程点：

这些细节决定了一份”DiskANN 论文照着写”的实现能否在基准上接近论文数字。通常差距在 3–10 倍。

四、SPANN：倒排+图的磁盘混合索引

SPANN（Chen et al., NeurIPS 2021）来自微软另一组，是另一条走向磁盘的路线。它不改造图索引，而是回到经典的 IVF（倒排文件）思路：把向量按聚类分成多个 posting list，查询时只读相关 posting list。与 FAISS 的 IVF 最大的区别是：“posting list 本身可以放在磁盘上”。

4.1 架构总览

内存：
  - 中心点（Centroids）+ 小规模 HNSW 用来路由查询到 top-m 个 posting list

磁盘：
  - 每个 posting list 是一段连续向量（原始精度）
  - 多副本（replication）把边界向量复制到多个 posting list

训练过程：

  1. 对全量向量做 k-means 聚类，产生 \(K\) 个中心点（\(K \approx n/100 \sim n/1000\)）。
  2. 每个向量分配到距离最近的中心点，形成 posting list。
  3. 对每个中心点训练一个小型 HNSW 图，用来快速找到 top-m 个 posting list。

查询过程：

def spann_search(q, m, k):
    # 1. 在内存 HNSW 上找 q 的 top-m 个 posting list
    lists = hnsw_search(q, centroids, m)
    # 2. 从 SSD 读取这 m 个 posting list
    candidates = []
    for l in lists:
        candidates.extend(read_posting_list(l))
    # 3. 对合并集合做精排
    return top_k(candidates, q, k)

4.2 两个关键优化

A. 动态 posting list 长度。朴素 IVF 是均匀切分，每个 posting list 大小相近。SPANN 观察到：不同区域的密度差异巨大，均匀切分会让稠密区域的 posting list 过长，稀疏区域过短。它让每个 posting list 的长度自适应，限制上限（防止单个 list 过长导致一次 I/O 代价太高）。

B. 边界点复制。ANN 的召回丢失主要发生在查询向量恰好落在多个聚类边界上——真值可能在某个没被访问到的 posting list 里。SPANN 的做法是：对每个向量 \(x\)，复制到它距离 top-\(\tau\) 个中心点对应的 posting list 里（\(\tau = 8\) 典型值）。这让边界召回大幅提升，代价是磁盘空间放大 \(\tau\) 倍（但论文给出了基于距离阈值的筛选，实际放大约 2–3 倍）。

4.3 和 DiskANN 的对比

维度 DiskANN SPANN
索引形态 单层图 倒排表 + 路由图
磁盘访问模式 图游走，多跳随机读 少数 posting list 顺序读
单次查询 I/O 次数 数十到上百（随机） 几到几十（较大块）
内存占用 PQ 码 + 邻接缓存 中心点 HNSW + 必要索引
调参复杂度 \(R\), \(L\), \(\alpha\) \(K\), \(m\), \(\tau\)
更新友好性 差（FreshDiskANN 弥补） 好（posting list 易于增删）

工程选择取决于访问模式：

目前 SPANN 在微软 Bing、SPTAG 等项目中有生产部署。开源实现 SPTAG（Space Partition Tree and Graph）包含了 SPANN 的核心代码。

五、量化路线：IVF-PQ 与 ScaNN 的位置

5.1 IVF-PQ 家族

乘积量化（Product Quantization, PQ）由 Jégou 等人在 2011 年提出，思路是把 \(d\) 维向量切成 \(m\) 段，每段用 \(k\)-means 量化（典型 \(k = 256\)，单段编码 1 字节），一个 \(d=768\) 向量被压缩成 \(m=96\) 字节（压缩比 32×）。查询时用非对称距离计算（Asymmetric Distance Computation, ADC），距离近似误差可控。

IVF-PQ = IVF（粗量化分桶）+ PQ（桶内细量化），是 FAISS 中 IndexIVFPQ 的结构：

典型参数：\(K = \sqrt{n} \sim 4\sqrt{n}\)，\(n_{\text{probe}} = 10 \sim 100\)，PQ 段数 \(m = d/4\) 到 \(d/2\)。

IVF-PQ 的优势是内存极省，适合”内存放下但召回可以妥协”的场景。它的上限是召回率——在 95% 以上需要很大的 \(n_{\text{probe}}\)，延迟就不再有优势。

5.2 ScaNN：各向异性量化

ScaNN（Guo et al., ICML 2020）来自 Google，对 PQ 做了一个关键改进。经典 PQ 量化目标是最小化重建误差 \(\|x - \hat{x}\|^2\)，但 ANN 真正关心的是量化后内积 \(\langle q, \hat{x}\rangle\) 与真值 \(\langle q, x\rangle\) 的误差。ScaNN 的各向异性量化损失（Anisotropic Quantization Loss）在方向上做区分：与 \(x\) 平行方向的误差权重更大，因为它直接影响到与相关查询的内积。

论文里在 GloVe-1M 等数据集上 ScaNN 比 IVF-PQ 的 曲线高 2–5 个百分点。ScaNN 开源实现（google-research/scann）也被集成到 Vertex AI Matching Engine。

5.3 量化和图索引不是二选一

真实系统里，量化通常作为图索引的”加速器”共存：

选型原则：

六、FAISS 与向量数据库选型

6.1 FAISS：工具箱还是数据库

FAISS（Johnson et al., 2021）是 Meta 开源的向量检索工具库，提供几十种索引实现（IndexFlatL2、IndexIVFPQ、IndexHNSWFlat、IndexHNSWPQ、IndexScalarQuantizer、IndexBinaryFlat 等）和 GPU 加速版本。FAISS 本身不是数据库——它没有元数据、标量字段、过滤、事务、持久化协议、分布式分片。

典型工作流：

import faiss
import numpy as np

d = 128
nb = 100_000
xb = np.random.randn(nb, d).astype("float32")

# HNSW
index = faiss.IndexHNSWFlat(d, 32)     # M=32
index.hnsw.efConstruction = 200
index.add(xb)
index.hnsw.efSearch = 64
D, I = index.search(xq, k=10)

FAISS 作为底层库的角色清晰：Milvus 最初的向量搜索核心调用 FAISS；pgvector 的 ivfflat 实现独立于 FAISS 但思路相近。

6.2 Milvus、pgvector、Qdrant、Weaviate 的定位

系统 索引内核 存储架构 过滤支持 适用场景
Milvus 2.x FAISS + 自研 HNSW/DiskANN 分布式、存算分离（MinIO + etcd + Pulsar） 标量字段 + 多种过滤策略 十亿级向量、生产级向量库
pgvector 自研 HNSW、IVFFlat 嵌入 PostgreSQL SQL 任意条件 已有 PG 生态、千万级以下
Qdrant 自研 HNSW（Rust） 单机或集群 丰富的 payload 索引 中等规模、强过滤需求
Weaviate 自研 HNSW（Go） 单机或集群 GraphQL / 模块化向量化 带 schema 的半结构化
Vespa HNSW + 自研 Yahoo 搜索系 强 搜索+推荐业务

几个常被忽视的选型点：

6.3 参数调优的一套流程

无论用哪个系统，参数调优的套路基本一致：

  1. 确定召回目标：先跑一次暴力搜索得到真值（Top-100），再决定业务对 的要求（0.9 / 0.95 / 0.99）。
  2. 固定构建参数：HNSW 先用 \(M=16, efC=200\) 或 \(M=32, efC=400\) 建一次。
  3. 扫查询参数：从小的 \(efSearch\) 开始扫，记录 Recall–QPS 曲线，取达标点。
  4. 验证内存与延迟：确认 P50/P99 满足业务约束。
  5. 再考虑压缩：如果内存不够才加 PQ/SQ8，观察召回衰减。

不要一上来就调十几个参数。每次只改一个，记录对照。

6.4 常见的反模式

几个在生产环境里反复出现的错误选型姿势：

A. 用 IVFFlat 的 lists 当成万能旋钮。很多文章说 lists = sqrt(n)，但这是一个下限经验。在 1 亿向量时 sqrt(n) = 10000，每个 list 一万条，\(n_{\text{probe}} = 10\) 扫 10 万候选，延迟不小且召回难到 95%。实际上超过千万级就应该换到 HNSW 或 DiskANN。

B. 把 pgvector 当成万能向量库。pgvector 优点是和 PG 生态无缝，但它不是专用向量库。万级 QPS + 亿级向量场景下，pgvector 的并发瓶颈（PG 的共享缓冲池、锁）会显现，这时 Milvus/Qdrant 是更合适的选择。

C. 盲目追求最新算法。学术界每年有十几个新的 ANN 算法发表，但工业实现能赶上论文节奏的屈指可数。生产选型应该以”有持续维护的开源实现 + 公开的 benchmark 数据”为门槛，而不是”最新发表”。

D. 忽视冷启动。HNSW 索引构建完成后通常要预热：跑一批”假查询”让操作系统 page cache 把索引页加载进内存。没有预热的首批查询延迟会比稳态高一个数量级。这在自动伸缩环境里尤其要注意。

E. 忽视监控指标。向量索引服务至少要监控：Recall（用 shadow query）、P50/P95/P99 延迟、QPS、索引内存占用、删除比例、查询时的平均 distance computation 次数。后者是诊断”参数退化”最好的单一指标。

6.5 多租户场景下的部署模式

多租户是向量数据库一个被低估的难题。三种典型部署：

选择取决于租户规模分布：长尾分布（少数大租户 + 很多小租户）最适合分层。均匀分布可以共享集群。百千级大租户可以每个独立。

6.6 何时不需要向量数据库

反问一个常被忽视的问题：哪些场景不需要专用向量库？

七、最小 HNSW 复现（numpy，可跑 1k 向量）

下面给出一个约 180 行的纯 numpy HNSW 实现，放在 demo/hnsw_numpy.py 。它实现了分层插入、启发式选邻居、贪心查询，并附带一个基准脚本对比暴力搜索。

7.1 核心代码骨架

# demo/hnsw_numpy.py （节选，完整版见 demo 目录）
import math
import heapq
import numpy as np

class HNSW:
    def __init__(self, d, M=16, efC=100, efS=50, seed=0):
        self.d = d
        self.M = M
        self.M0 = 2 * M
        self.efC = efC
        self.efS = efS
        self.mL = 1.0 / math.log(M)
        self.rng = np.random.default_rng(seed)
        self.data = []                    # [np.ndarray, ...]
        self.levels = []                  # 每个节点的最高层
        self.graph = []                   # graph[layer][node] -> list of neighbors
        self.entry = -1
        self.top_level = -1

    def _dist(self, a, b):
        return float(np.dot(a - b, a - b))

    def _sample_level(self):
        r = self.rng.random()
        return int(-math.log(r + 1e-12) * self.mL)

search_layer 是整个算法的核心：

    def _search_layer(self, q, ep, ef, layer):
        visited = {ep}
        d_ep = self._dist(q, self.data[ep])
        candidates = [(d_ep, ep)]         # 最小堆
        results = [(-d_ep, ep)]           # 最大堆（存负距离）
        while candidates:
            d_c, c = heapq.heappop(candidates)
            if -results[0][0] < d_c and len(results) >= ef:
                break
            for n in self.graph[layer].get(c, ()):
                if n in visited:
                    continue
                visited.add(n)
                d_n = self._dist(q, self.data[n])
                if len(results) < ef or d_n < -results[0][0]:
                    heapq.heappush(candidates, (d_n, n))
                    heapq.heappush(results, (-d_n, n))
                    if len(results) > ef:
                        heapq.heappop(results)
        return results

启发式选邻居（简化版）：

    def _select_neighbors(self, cand, M):
        # cand: list of (dist_to_q, node_id), dist 越小越近
        cand = sorted(cand, key=lambda x: x[0])
        chosen = []
        for d, n in cand:
            if len(chosen) >= M:
                break
            ok = True
            for _, c in chosen:
                if self._dist(self.data[n], self.data[c]) < d:
                    ok = False
                    break
            if ok:
                chosen.append((d, n))
        return [n for _, n in chosen]

插入：

    def insert(self, x):
        x = np.asarray(x, dtype=np.float32)
        idx = len(self.data)
        self.data.append(x)
        l = self._sample_level()
        self.levels.append(l)
        # 扩展层
        while len(self.graph) <= l:
            self.graph.append({})
        if idx == 0:
            self.entry = 0
            self.top_level = l
            for lc in range(l + 1):
                self.graph[lc][idx] = []
            return
        ep = self.entry
        # 顶层到 l+1：贪心下行
        for lc in range(self.top_level, l, -1):
            W = self._search_layer(x, ep, 1, lc)
            ep = W[0][1]
        # l 到 0：正式插入
        for lc in range(min(self.top_level, l), -1, -1):
            W = self._search_layer(x, ep, self.efC, lc)
            cand = [(-d, n) for d, n in W]
            max_deg = self.M0 if lc == 0 else self.M
            nbrs = self._select_neighbors(cand, max_deg)
            self.graph[lc][idx] = nbrs
            for n in nbrs:
                self.graph[lc].setdefault(n, []).append(idx)
                if len(self.graph[lc][n]) > max_deg:
                    n_cand = [(self._dist(self.data[n], self.data[m]), m)
                              for m in self.graph[lc][n]]
                    self.graph[lc][n] = self._select_neighbors(n_cand, max_deg)
            ep = nbrs[0] if nbrs else ep
        if l > self.top_level:
            self.top_level = l
            self.entry = idx

查询：

    def search(self, q, k):
        q = np.asarray(q, dtype=np.float32)
        ep = self.entry
        for lc in range(self.top_level, 0, -1):
            W = self._search_layer(q, ep, 1, lc)
            ep = W[0][1]
        W = self._search_layer(q, ep, self.efS, 0)
        W = sorted([(-d, n) for d, n in W])
        return [(n, d) for d, n in W[:k]]

7.2 基准测试

demo/bench.py 对 1000 个 64 维向量建索引，比较与暴力搜索的 ：

import numpy as np
from hnsw_numpy import HNSW

rng = np.random.default_rng(42)
n, d = 1000, 64
X = rng.standard_normal((n, d)).astype("float32")
Q = rng.standard_normal((50, d)).astype("float32")

# 真值
def brute(q, k=10):
    diff = X - q
    dist = (diff * diff).sum(axis=1)
    return np.argsort(dist)[:k]

hnsw = HNSW(d=d, M=8, efC=100, efS=50)
for i in range(n):
    hnsw.insert(X[i])

recall = 0.0
for q in Q:
    truth = set(brute(q).tolist())
    pred = set(n for n, _ in hnsw.search(q, 10))
    recall += len(truth & pred) / 10
print("Recall@10 =", recall / len(Q))

在 1000 向量、\(M=8\)、\(efS=50\) 的默认设置下， 通常在 0.95 以上。调小 \(efS\)（比如 10）能看到召回率下降；调大 \(M\) 或 \(efC\) 能恢复召回。这个 demo 不追求性能（纯 Python、无 SIMD），只用来让读者实际感受 HNSW 的行为。完整代码见 demo/ 目录。

7.3 运行

cd post/db-frontier/08-vector-index/demo
python -m venv .venv && source .venv/bin/activate
pip install numpy
python bench.py

预期输出：Recall@10 = 0.96 左右（随机数种子和参数略有浮动）。

八、GPU 原生向量索引的位置

CPU 索引之外，近几年 GPU 原生 ANN 也逐渐进入视野，主要代表是 NVIDIA cuVS 里的 CAGRA（CUDA ANN Graph，2023）：

CAGRA 的优势：批量查询吞吐（batch size > 256）远超 CPU 图索引，单卡 A100 上千万级向量可以跑到每秒数万次 k=10 查询。但在单查询低延迟场景下 GPU 上下文切换和 PCIe 传输的开销使优势消失。

工程上 GPU 索引合适的使用位置：

在线低延迟单查询服务仍以 CPU 索引为主。FAISS 也长期维护 GPU 版本的 IndexFlat / IndexIVFPQ / IndexHNSW，场景类似。

十亿级 GPU 部署还需要考虑：多卡分片（每卡一部分向量）、CPU-GPU 数据传输优化、索引在 GPU 上的内存对齐。一个完整的 GPU 向量系统（如内部被称为 “Meta AI Similarity Search”）背后的工程复杂度不下于分布式 CPU 索引。

8.3 何时选 CPU、何时选 GPU

粗略的判断：

混合部署也常见：GPU 跑”近邻候选生成”（高吞吐），CPU 做”精排”（低延迟、访问原始向量）。这种两级架构在推荐系统里很普遍，和向量索引架构天然契合。

九、十亿规模的真实生产经验

几个公开的生产参考（来自论文、技术博客和会议分享）：

这些生产经验的共同点：没有一个系统只用一种索引。热数据用 HNSW，温数据用 DiskANN，冷数据用 IVF-PQ，批量分析用 GPU。索引层级化与存储层级化是对称的。

十、索引构建的吞吐与内存工程

论文里对构建阶段的分析通常比较粗线条，但在生产里构建吞吐和峰值内存往往决定了能不能用。

10.1 HNSW 构建的单线程瓶颈

hnswlib 的官方实现构建阶段大部分操作都需要持有整张图的写锁——add_point 内部的邻居选择和反向边更新都要互斥。这导致：

生产里常用的绕法：

10.2 内存占用粗算

预估 HNSW 的内存需要（单位：字节）：

\[ \text{Mem} \approx n \times d \times 4 + n \times M \times 4 \times \bar{L} \]

其中 \(\bar{L}\) 是层数均值（通常 \(\bar{L} \approx 1 / (1 - e^{-1/m_L})\)，\(m_L = 1/\ln M\)）。举例：\(n = 10^8, d = 768, M = 32\)，向量部分 \(\approx 286\,\text{GB}\)，图部分 \(\approx 32\,\text{GB}\)，合计 \(\approx 318\,\text{GB}\)。再加上 build 时的 1.5×，峰值接近 500 GB。

预估之后再决定是否需要走 DiskANN 或量化。不做预估就开建是最常见的失败来源之一。

10.3 动态维度

少数业务会问”我能否支持变长 embedding（比如 256 / 512 / 768 多种维度混存）？“目前任何主流 ANN 索引都不直接支持。应对方式：

十一、开放问题与参考阅读

到 2024 年底，向量索引仍有几个公认的开放问题：

几本值得通读的参考材料：

参考文献

  1. Yu. A. Malkov, D. A. Yashunin. “Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs.” IEEE TPAMI, 42(4), 824–836, 2020. https://arxiv.org/abs/1603.09320
  2. Subramanya, S. J., Devvrit, Kadekodi, R., Krishaswamy, R., Simhadri, H. V. “DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node.” NeurIPS, 2019. https://papers.nips.cc/paper/2019/hash/09853c7fb1d3f8ee67a61b6bf4a7f8e6-Abstract.html
  3. Singh, A., Subramanya, S. J., Krishnaswamy, R., Simhadri, H. V. “FreshDiskANN: A Fast and Accurate Graph-Based ANN Index for Streaming Similarity Search.” arXiv:2105.09613, 2021.
  4. Chen, Q., Zhao, B., Wang, H., et al. “SPANN: Highly-efficient Billion-scale Approximate Nearest Neighbor Search.” NeurIPS, 2021. https://arxiv.org/abs/2111.08566
  5. Jégou, H., Douze, M., Schmid, C. “Product Quantization for Nearest Neighbor Search.” IEEE TPAMI, 33(1), 117–128, 2011.
  6. Guo, R., Sun, P., Lindgren, E., et al. “Accelerating Large-Scale Inference with Anisotropic Vector Quantization.” ICML, 2020. https://arxiv.org/abs/1908.10396
  7. Johnson, J., Douze, M., Jégou, H. “Billion-Scale Similarity Search with GPUs.” IEEE Trans. Big Data, 7(3), 535–547, 2021.
  8. Aumüller, M., Bernhardsson, E., Faithfull, A. “ANN-Benchmarks: A Benchmarking Tool for Approximate Nearest Neighbor Algorithms.” Information Systems, 87, 101374, 2020.
  9. Wang, J., Yi, X., Guo, R., et al. “Milvus: A Purpose-Built Vector Data Management System.” SIGMOD, 2021.
  10. Indyk, P., Motwani, R. “Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality.” STOC, 1998.
  11. FAISS, https://github.com/facebookresearch/faiss
  12. hnswlib, https://github.com/nmslib/hnswlib
  13. Microsoft SPTAG (含 SPANN 实现), https://github.com/microsoft/SPTAG
  14. DiskANN 开源实现, https://github.com/microsoft/DiskANN
  15. pgvector, https://github.com/pgvector/pgvector
  16. Qdrant, https://github.com/qdrant/qdrant
  17. Milvus, https://github.com/milvus-io/milvus

上一篇：DB-as-Memory：数据库作为 LLM 外挂记忆 下一篇：向量与标量的混合过滤检索：ACORN、Milvus、pgvector 的算法权衡

同主题继续阅读

把当前热点继续串成多页阅读，而不是停在单篇消费。

2025-09-17 · storage

【存储工程】向量存储与 ANN 索引

给定一条 768 维的文本嵌入向量（Embedding），要从一亿条同维度向量中找出最相似的 10 条。暴力计算需要对每条向量做 768 次乘法和一次求和——一亿条就是 768 亿次浮点运算，单核 CPU 跑完需要几十秒。如果这个操作发生在每一次用户搜索请求中，系统根本无法响应。

By .