---
tags: [AI, vector-database, ann]
阶段: 06-Prompt与RAG
难度: ★★☆
created: 2026-10-18
related: "[[Embedding与向量检索]], [[RAG原理与流程]], [[检索优化与重排Rerank]]"
---

# 向量数据库

## 定义

**向量检索系统**（vector search system）是一个四元组 $\mathcal{S}=(E,\mathcal{I},\mathcal{M},\mathcal{Q})$：$E:\mathcal{X}\to\mathbb{R}^{d}$ 是嵌入函数，把对象映射为 $d$ 维向量；$\mathcal{I}$ 是索引结构，把 $N$ 个向量组织为支持近邻查询的数据结构；$\mathcal{M}$ 是元数据存储与过滤条件求值；$\mathcal{Q}$ 是对外查询接口，接受查询向量、$k$、过滤条件与一致性要求。

**精确最近邻**（exact nearest neighbor）返回真实的前 $k$ 个最近向量；**近似最近邻**（approximate nearest neighbor，ANN）返回候选集合 $\hat{S}_k$，只保证以较高概率覆盖真实结果。召回率定义为

$$
\rho=\frac{1}{\lvert Q\rvert}\sum_{q\in Q}\frac{\lvert\hat{S}_k(q)\cap S_k^{\star}(q)\rvert}{k},
$$

其中 $S_k^{\star}(q)$ 是精确检索结果，$Q$ 是查询集合。工程上同时报告召回率与延迟分位数，二者构成一条权衡曲线。

符号约定如下。

| 符号 | 含义 |
|---|---|
| $N$ | 向量总数 |
| $d$ | 向量维度 |
| $k$ | 返回条数 |
| $M$ | HNSW 每个节点在每层的邻居数上限 |
| $M_0$ | HNSW 第 0 层的邻居数上限，通常取 $2M$ |
| $\mathrm{efConstruction}$ | HNSW 构建时的候选队列长度 |
| $\mathrm{efSearch}$ | HNSW 查询时的候选队列长度 |
| $m_L$ | HNSW 层数分布的尺度参数，$m_L=1/\ln M$ |
| $\mathrm{nlist}$ | IVF 的聚类桶数 |
| $\mathrm{nprobe}$ | IVF 查询时扫描的桶数 |
| $m$ | PQ 的子向量个数，每个子向量编码 1 字节 |
| $n_{\text{bits}}$ | PQ 每个子向量的比特数，通常为 8 |
| $s$ | 过滤条件的选择率，满足条件的向量占比 |

其余术语在首次出现处定义：**HNSW**（Hierarchical Navigable Small World）指分层可导航小世界图；**IVF**（inverted file）指倒排文件索引，用聚类把向量分桶；**PQ**（product quantization）指乘积量化，把向量切段后分别编码；**ADC**（asymmetric distance computation）指查询保持原始向量、库中向量用码字近似时的距离计算；**选择率**指过滤条件命中的向量比例。

## 为什么重要

暴力检索的代价随规模线性增长。$N=10^{7}$、$d=768$ 时，向量本身占 $4Nd=30.72$ GB，单次查询要读取全部向量；按 50 GB/s 的有效内存带宽估算，单查询约 0.6 秒，且这一时间与查询难度无关。$N=10^{8}$ 时向量占 307 GB，单机内存无法容纳，必须压缩或分片。ANN 索引把“扫描全部向量”改为“访问少量候选”，使查询延迟与 $N$ 近似对数关系，这是检索系统能够在线服务的前提。

但 ANN 用召回率换延迟，召回率下降会直接传导到生成质量。检索未命中时，生成器只能依据参数化知识作答，答案不可归因；检索返回错误文档时，生成器获得干扰证据。这两类错误无法在生成阶段修复，只能回到索引层解决，失效分析见 [[RAG原理与流程]]。因此向量数据库的核心指标不是“单查询多快”，而是“在目标召回率下的延迟与内存”。

系统层面还有三个不可回避的问题。第一，元数据过滤：业务查询通常带租户、时间、权限、文档类型等条件，过滤与 ANN 的组合会改变召回率。第二，更新与删除：嵌入模型升级需要全量重编码，删除需要处理图结构与倒排表的残留。第三，容量规划：原始向量、图结构、量化码、副本与索引构建的临时空间共同决定单机上限。这三项在原型阶段不可见，在数据量超过内存后才暴露。

在本库中，本篇承接 [[Embedding与向量检索]] 的度量与训练，向下接入 [[RAG原理与流程]] 的检索阶段，并与 [[检索优化与重排Rerank]] 构成“召回—重排”两级结构；工程侧的延迟与成本约束见 [[模型推理优化]]。学习目标是能根据数据规模、召回要求与过滤比例选择索引类型与参数，并能用可复现的实验报告召回率与延迟。

## 原理与推导

### 1 系统组成与数据流

一个完整的向量检索系统包含五个部分，缺一不可。

| 组件 | 职责 | 关键设计点 |
|---|---|---|
| 嵌入服务 | 把文本编码为向量 | 模型版本、维度、归一化、批量吞吐 |
| 索引结构 | 支持近邻查询 | Flat、HNSW、IVF、PQ 及其组合 |
| 元数据存储 | 保存 id、来源、权限、时间等标量字段 | 与向量 id 对齐、过滤下推 |
| 过滤执行 | 在候选集上应用布尔条件 | 预过滤、后过滤、分区 |
| 查询接口 | 参数校验、超时、一致性、监控 | top-k、nprobe、efSearch、重试 |

离线与在线两条链路共用同一套 id 与元数据。

```mermaid
flowchart LR
    DOC[原始文档] --> CH[分块]
    CH --> ENC[嵌入编码]
    ENC --> IDX[索引构建]
    ENC --> META[(元数据与标量字段)]
    Q[查询文本] --> QENC[查询编码]
    QENC --> ANN[ANN 检索]
    IDX --> ANN
    META --> FIL[过滤条件]
    FIL --> ANN
    ANN --> CAND[候选集]
    CAND --> RER[精算或重排]
    RER --> TOP[Top-k 结果]
```

图中的关键约束是两侧必须使用同一嵌入模型与同一归一化方式。模型版本不一致时，查询向量与文档向量位于不同空间，内积失去意义；这类错误不会报错，只会表现为召回率整体下降。

### 2 精确检索的代价与 ANN 的定义

精确检索计算查询与全部向量的内积并取前 $k$：

$$
S_k^{\star}(\mathbf{q})=\operatorname*{arg\,topk}_{i\in\{1,\dots,N\}}\ \mathbf{q}^{\top}\mathbf{x}_i .
$$

时间复杂度为 $O(Nd)$，空间复杂度为 $O(Nd)$。矩阵乘法可以把常数压得很低，但无法改变必须读取全部向量的性质：计算量 $Nd$ 在 GPU 上约需毫秒级，而读取 $4Nd$ 字节受内存带宽限制。$N=10^{7}$、$d=768$ 时数据量为 30.72 GB，超过多数单卡的显存，也超过 CPU 缓存的三个数量级。

ANN 的做法是只访问可能包含近邻的一小部分向量。设访问的候选数为 $C$，则查询代价近似为 $O(Cd)$，加速比约为 $N/C$。代价是可能漏掉真实近邻：若真实近邻不在被访问的候选集中，无论后续如何计算都无法找回。因此 ANN 的评估必须同时给出召回率 $\rho$ 与延迟，单独报告其中一个没有意义。

高维空间使问题更难。维度增大时，最近邻与较远点的距离差异变小，索引用来剪枝的几何条件变弱，这是维度灾难在检索上的表现；HNSW 与 IVF 在高维数据上仍可用，但需要更多候选才能达到相同召回率。

### 3 HNSW：多层图、插入与搜索

HNSW 把向量组织为一张分层图。第 0 层包含全部 $N$ 个节点，越往上节点越少；每个节点出现在从第 0 层到其最高层的一段连续层中。层数按指数分布采样：

$$
P(\text{level}\ge l)=e^{-l/m_L}=M^{-l},\qquad m_L=\frac{1}{\ln M}.
$$

因此第 $l$ 层的期望节点数为 $N M^{-l}$，最高层的期望高度为 $\log_M N$。上层边少而长，负责快速接近目标区域；下层边多而短，负责精确收敛。这一结构使搜索的期望跳数为 $O(\log N)$。

**插入**一个节点 $x$ 的过程如下。

1. 采样层数 $l\sim\lfloor -\ln(U)\cdot m_L\rfloor$，$U$ 为 $(0,1]$ 上的均匀随机数。
2. 从当前最高层 $L$ 向下到第 $l+1$ 层，在每层用贪心策略移动到一个距离 $x$ 更近的邻居，直到无法改进；这是 $ef=1$ 的搜索。
3. 从 $\min(L,l)$ 层向下到第 0 层，在每层用长度为 $\mathrm{efConstruction}$ 的候选队列搜索，得到候选邻居集合。
4. 用启发式规则从候选中选出不超过 $M$（第 0 层为 $M_0$）个邻居，建立双向边。
5. 若某邻居的边数超过上限，按同一启发式规则裁剪其邻接表。
6. 若 $l>L$，更新最高层。

第 4 步的启发式规则是 HNSW 与普通近邻图的关键区别。设候选 $e$ 已按到 $x$ 的距离升序排列，已选邻居集合为 $R$，则仅当

$$
d(e,x)<d(e,r)\quad\text{对任意 }r\in R
$$

成立时才把 $e$ 加入 $R$。该条件要求新邻居与已选邻居之间保持一定间隔，避免所有边都指向同一局部方向。若只取最近的 $M$ 个邻居，图会在密集区域形成团簇，缺少通往其他区域的边，搜索容易陷入局部最优；启发式规则牺牲部分近邻精度，换取图的连通性与可导航性。

**搜索**过程分两段。

1. 从最高层开始，在每层执行贪心搜索，直到当前层无法再靠近查询。
2. 到达第 0 层后，用长度为 $\mathrm{efSearch}$ 的候选队列执行束搜索：维护候选堆与结果堆，每次取出最近的候选，遍历其邻居，若邻居比结果堆中最远元素更近或结果堆未满，则加入并按 $\mathrm{efSearch}$ 裁剪。

最终从结果堆中取前 $k$ 个。$\mathrm{efSearch}\ge k$，且 $\mathrm{efSearch}$ 越大，候选覆盖越充分、召回越高、延迟越大。查询阶段可在线调整该参数，无需重建索引。

| 参数 | 作用 | 增大时的效果 | 典型范围 |
|---|---|---|---|
| $M$ | 每层邻居数上限 | 图更密，召回上升，内存与构建时间线性增长 | 16 到 64 |
| $M_0$ | 第 0 层邻居上限 | 底层连通性更好，内存增加 | $2M$ |
| $\mathrm{efConstruction}$ | 构建候选队列 | 图质量上升，构建变慢 | 100 到 400 |
| $\mathrm{efSearch}$ | 查询候选队列 | 召回上升，延迟上升 | 32 到 256 |

内存由邻接表主导。每个节点在第 0 层保存至多 $M_0=2M$ 个邻居 id，上层合计约 $M/(M-1)\approx1$ 个，故

$$
\text{图内存}\approx 4N(2M+1)\ \text{字节}.
$$

$N=10^{7}$、$M=32$ 时约 2.42 GiB，与原始向量（28.61 GiB）相比很小；若同时保存原始向量用于精算，总内存约为二者之和。删除在 HNSW 中代价高：删除节点会破坏双向边与连通性，FAISS 的 HNSW 索引不实现 `remove_ids`，常见做法是维护有效位掩码并在查询时扩大 $\mathrm{efSearch}$，或定期重建索引。

### 4 IVF：聚类分桶与 nprobe

IVF 用一个粗量化器把向量空间划分为 $\mathrm{nlist}$ 个区域。训练阶段对样本做 k-means，得到质心 $\mathbf{c}_1,\dots,\mathbf{c}_{\mathrm{nlist}}$；写入阶段把每个向量分配到最近质心所属的倒排表：

$$
j(i)=\arg\min_{j}\lVert\mathbf{x}_i-\mathbf{c}_j\rVert_2^2,\qquad L_j=\{i:j(i)=j\}.
$$

查询阶段先计算查询到全部质心的距离，选出最近的 $\mathrm{nprobe}$ 个桶，只扫描这些桶内的向量：

$$
\hat{S}_k=\operatorname*{arg\,topk}_{i\in\bigcup_{j\in\mathcal{P}}\ L_j}\mathbf{q}^{\top}\mathbf{x}_i,
\qquad \lvert\mathcal{P}\rvert=\mathrm{nprobe}.
$$

若各桶大小均衡，候选数为 $N\cdot\mathrm{nprobe}/\mathrm{nlist}$，相对暴力检索的加速比约为 $\mathrm{nlist}/\mathrm{nprobe}$，另需 $O(\mathrm{nlist}\cdot d)$ 的质心比较开销。$N=20000$、$\mathrm{nlist}=64$、$\mathrm{nprobe}=8$ 时候选数约为 2500，实测为 2470，与估算一致。

召回率取决于真实近邻是否落在被探测的桶中。若真实近邻所在桶的质心不是查询的最近 $\mathrm{nprobe}$ 个质心之一，该近邻就无法被找回。桶的划分由 k-means 在训练样本上决定，因此训练样本必须代表线上分布：样本偏斜会使部分区域缺少质心，落在这些区域的查询召回率显著下降。

| 参数 | 作用 | 增大时的效果 | 经验取值 |
|---|---|---|---|
| $\mathrm{nlist}$ | 桶数 | 单桶更小，扫描更快，但质心比较与训练成本上升 | $4\sqrt{N}$ 到 $16\sqrt{N}$ |
| $\mathrm{nprobe}$ | 探测桶数 | 召回上升，延迟线性上升 | $\mathrm{nlist}$ 的 1% 到 10% |
| 训练样本量 | 质心质量 | 更接近真实分布，训练更慢 | 至少 $30\times\mathrm{nlist}$，推荐 $100\times\mathrm{nlist}$ |

IVF 的结构简单，插入只需一次质心比较后追加到对应桶，删除只需从桶中移除，更新成本低于 HNSW。它的弱点是查询时要访问多个桶，且桶的边界由质心决定，对分布漂移敏感；数据分布随时间变化时需要重新训练质心并重建索引。

### 5 PQ：乘积量化、压缩率与精度损失

PQ 把 $d$ 维向量切成 $m$ 段，每段 $d/m$ 维，对每段独立做 k-means，得到 $m$ 个码本，每个码本含 $2^{n_{\text{bits}}}$ 个码字。一个向量被编码为 $m$ 个编号：

$$
\mathbf{x}=(\mathbf{x}^{(1)},\dots,\mathbf{x}^{(m)})\ \longmapsto\ (k_1,\dots,k_m),\qquad
k_j=\arg\min_{c}\lVert\mathbf{x}^{(j)}-\mathbf{c}^{(j)}_{c}\rVert_2^2 .
$$

原始向量占 $4d$ 字节，编码后占 $m$ 字节（$n_{\text{bits}}=8$），压缩比为

$$
\frac{4d}{m}.
$$

$d=768$、$m=96$ 时压缩比为 32，$10^{7}$ 条向量从 28.61 GiB 降到 0.89 GiB。查询时预先计算查询各段到对应码本全部码字的距离，得到 $m\times 2^{n_{\text{bits}}}$ 的查找表：

$$
T[j][c]=\lVert\mathbf{q}^{(j)}-\mathbf{c}^{(j)}_{c}\rVert_2^2,
$$

则与编码向量的近似平方距离为 $\sum_{j=1}^{m}T[j][k_j]$，只需 $m$ 次查表与加法，不再做浮点乘加。这就是 ADC。

精度损失来自分段独立量化：每段单独选择码字，段间相关性被丢弃。$m$ 越大，每段维度越低、码本越容易拟合，误差越小，但压缩比下降；$m$ 越小，压缩比越高，距离估计偏差越大。$m$ 必须整除 $d$，且每段维度不宜低于 4，否则码本难以覆盖该子空间。

| 配置（$d=768$） | 每段维度 | 压缩比 | 内存（$10^{7}$ 条） | 精度 |
|---|---|---|---|---|
| $m=192$ | 4 | 16 | 1.79 GiB | 较高 |
| $m=96$ | 8 | 32 | 0.89 GiB | 中等 |
| $m=48$ | 16 | 64 | 0.45 GiB | 较低 |

PQ 通常与 IVF 组合为 IVFADC：先用 IVF 选桶，再在桶内用 PQ 码计算近似距离，最后可用原始向量对前若干条精算。只依赖 PQ 码排序会引入系统性偏差，精算阶段能挽回部分召回，代价是需要保存原始向量或回表读取，内存与 IO 随之上升。

### 6 度量类型与归一化一致性

索引的度量必须与写入、查询时的处理一致。三种常见组合如下。

| 目标 | 写入处理 | 索引度量 | 查询处理 |
|---|---|---|---|
| 余弦相似度 | L2 归一化 | 内积或余弦 | L2 归一化 |
| 欧氏距离 | 不归一化 | L2 | 不归一化 |
| 内积 | 不归一化 | 内积 | 不归一化 |

向量归一化后，内积排序与 L2 排序一致（$\lVert\mathbf{a}-\mathbf{b}\rVert^2=2-2\mathbf{a}^{\top}\mathbf{b}$），因此在归一化数据上把余弦检索实现为内积索引是等价的，且内积计算少一次除法。若写入时归一化、查询时未归一化，内积会引入查询模长因子，虽然对同一查询的所有文档是同一常数、不改变排序，但混合了未归一化文档时排序就会改变。若写入未归一化、查询归一化，则文档模长进入排序，长文档占优。

各系统的接口对度量有显式声明。pgvector 用操作符与索引类绑定：`<->` 对应 L2 距离、`<#>` 返回负内积、`<=>` 返回余弦距离，索引必须用匹配的 `vector_l2_ops`、`vector_ip_ops`、`vector_cosine_ops`，否则查询不会使用该索引。Milvus 在集合级别声明 `metric_type`，Chroma 在集合创建时指定 `hnsw:space`。更换度量意味着重建索引，不能只改查询参数。

量化索引还要求训练与查询使用同一度量。IVF 的 k-means 以 L2 分配样本，PQ 的码本也以 L2 训练；若最终按内积排序，归一化后二者一致，未归一化时近似误差会偏向模长大的向量。

### 7 元数据过滤：预过滤与后过滤

过滤条件把查询限制在满足布尔表达式的子集上，选择率 $s\in[0,1]$ 表示命中比例。两种执行顺序的代价不同。

**后过滤**（post-filter）先做 ANN 取 $k'$ 条，再按条件过滤，若不足 $k$ 条则扩大 $k'$ 重试。若过滤与向量分布独立，留下的条数近似服从二项分布，期望为 $k'\cdot s$。要得到 $k$ 条，需 $k'\approx k/s$：$s=0.01$ 时为了 10 条结果要取 1000 条候选，延迟与 $1/s$ 成正比，且极端情况下重试多次仍不足。

**预过滤**（pre-filter）先计算满足条件的 id 集合，再在该集合内检索。若集合很小，直接暴力扫描子集的代价为 $O(sNd)$，可能低于 ANN；若集合较大，可以把过滤条件交给索引做过滤式遍历。问题在于图索引的连通性：HNSW 的边跨越不同元数据分区，过滤掉大量节点后，从入口到目标区域的路径可能被切断，召回率骤降。工程上的折中包括按过滤字段分区（每个租户或时间段一个集合）、在遍历时跳过不满足条件的节点但保留其边、以及用位图加速条件判断。

| 策略 | 做法 | 优点 | 缺点 | 适用 |
|---|---|---|---|---|
| 后过滤 | ANN 取 $k/s$ 再过滤 | 实现简单，索引不变 | 低选择率时延迟放大 | $s>0.1$ |
| 预过滤暴力 | 取 id 子集后扫描 | 召回精确 | 子集大时慢 | $s<0.01$ |
| 过滤式遍历 | 遍历时跳过不合格节点 | 兼顾召回与延迟 | 依赖系统支持 | $0.01<s<0.1$ |
| 分区 | 按租户/时间建独立集合 | 过滤变为路由 | 集合数量与运维成本上升 | 强分区语义 |

选择率不是唯一因素，过滤字段与向量的相关性同样重要。若某类文档的向量本身聚集，过滤后候选区域变窄，ANN 更容易漏召回；此时应优先分区而不是后过滤。

### 8 系统选型对比

| 系统 | 形态 | 索引 | 过滤 | 更新与删除 | 适用规模 |
|---|---|---|---|---|---|
| Chroma | 嵌入式库，也提供服务模式 | HNSW | `where` 元数据过滤 | 支持按 id 删除与更新 | 原型到百万级 |
| FAISS | C++/Python 库 | Flat、IVF、PQ、HNSW、OPQ 等 | 无内置元数据，需自建掩码 | HNSW 不支持原地删除，IVF 可移除 | 百万到十亿级，需自行分片 |
| Milvus | 分布式服务 | HNSW、IVF、PQ、DiskANN、GPU 索引 | 标量过滤与混合查询 | 支持删除与 compaction | 亿级，多租户 |
| pgvector | PostgreSQL 扩展 | IVFFlat、HNSW | SQL `WHERE`，与事务一致 | 支持 `DELETE` 与 `UPDATE` | 百万到千万级，单机为主 |

选型从约束出发，而不是从基准测试排名出发。已有 PostgreSQL 且数据量在千万级以内时，pgvector 复用事务、备份与权限体系，运维成本最低；需要十亿级向量与多副本时，Milvus 的存算分离与分区能力更合适；只做离线实验或需要 GPU 暴力检索时，FAISS 提供最完整的索引组合；原型阶段需要最少配置时，Chroma 的嵌入式模式可以省去服务部署。

需要核对三个细节。第一，维度上限：pgvector 的 HNSW 索引对 `vector` 类型支持到 2000 维，更高维需改用 `halfvec` 或降维。第二，删除语义：FAISS 的 HNSW 不提供原地删除，删除比例上升后必须重建。第三，过滤下推能力：部分系统只能后过滤，低选择率查询会退化。

### 9 容量、删除与重建

容量由四部分构成：原始向量 $4Nd$ 字节、图或倒排结构、量化码与码本、副本与临时构建空间。以 $N=10^{7}$、$d=768$、HNSW $M=32$ 为例：

| 部分 | 计算 | 大小 |
|---|---|---|
| 原始向量 | $4Nd$ | 28.61 GiB |
| HNSW 邻接 | $4N(2M+1)$ | 2.42 GiB |
| PQ 码（$m=96$） | $Nm$ | 0.89 GiB |
| 构建临时空间 | 约为原始向量的 1 到 2 倍 | 30 到 60 GiB |

原始向量与索引同时驻留时，单机需要 32 GiB 以上的常驻内存，构建阶段还需额外空间；若保存副本，按副本数线性增加。容量规划应保留 30% 余量，用于重建、合并与流量峰值。

删除在两类索引中的代价不同。IVF 与 PQ 的删除是定位 id 所在桶后移除，代价 $O(1)$ 到 $O(\text{桶长})$；HNSW 的删除会破坏双向边，通常用墓碑标记，查询时过滤，等到墓碑比例超过阈值（常见 10% 到 20%）再重建。墓碑比例上升会同时降低召回率与有效容量，因为被标记的节点仍占用图结构与遍历预算。

重建由三类事件触发：嵌入模型更换、数据分布显著漂移、删除与更新累积。模型更换必须全量重编码，不能只重建索引，因为新旧向量不在同一空间；迁移应采用双写策略，新索引构建完成并通过离线评估后切换别名，保留旧索引一段时间用于回滚。重建期间的服务能力需要提前规划，常见做法是按分片滚动重建。

### 10 参数选择建议

1. 先固定度量与归一化，再选索引。度量不一致造成的召回损失无法通过调参弥补。
2. HNSW 起步取 $M=16$ 到 $32$、$\mathrm{efConstruction}=200$，在 1000 条查询的样本上把 $\mathrm{efSearch}$ 从 32 扫到 256，记录召回率与 p99 延迟，选择满足召回目标的最小值。
3. 目标召回率高于 0.98 时，优先增大 $M$ 与 $\mathrm{efConstruction}$ 重建，而不是只增大 $\mathrm{efSearch}$；后者只能改善查询侧，无法修复图结构缺陷。
4. IVF 取 $\mathrm{nlist}\approx4\sqrt{N}$ 到 $16\sqrt{N}$，$\mathrm{nprobe}$ 从 1% 起调；训练样本至少 $30\times\mathrm{nlist}$ 条，且必须来自线上分布。
5. 内存不足时引入 PQ，$m$ 取 $d/4$ 左右并保证整除；压缩后务必用原始向量对前 50 到 100 条精算，否则排序偏差会传导到生成阶段。
6. 过滤选择率低于 1% 时改用预过滤或分区；1% 到 10% 时确认系统支持过滤式遍历；高于 10% 时后过滤通常可接受。
7. 每次更换模型、调整参数或数据分布变化后，重跑同一套查询与标注，报告召回率、p50/p99 延迟、内存占用与构建时间，四项同时记录。

## 关键直觉

> [!tip] HNSW 是“分层图 + 束搜索”：上层负责快速接近目标区域，下层负责精确收敛，$\mathrm{efSearch}$ 是用候选数量换取召回率的查询期预算；IVF 用聚类把全量扫描变成“只扫 $\mathrm{nprobe}$ 个桶”，加速比约为 $\mathrm{nlist}/\mathrm{nprobe}$；PQ 用分段码本把向量压缩为 $m$ 字节，并用查表把距离计算变成 $m$ 次加法。
>
> 与严格定义的关系：召回率 $\rho$ 定义了 ANN 的“近似”程度，所有参数只在这条曲线上移动工作点；HNSW 的边选择启发式 $d(e,x)<d(e,r)$ 解释了为什么图能保持可导航性而不是退化为局部团簇；IVF 的候选数 $N\cdot\mathrm{nprobe}/\mathrm{nlist}$ 与 PQ 的压缩比 $4d/m$ 把“召回—延迟—内存”三者写成可计算的量，选型就是在这三个量之间取满足约束的点。

## 例子与代码

### 例 1：NumPy 实现 IVF 并与精确检索对比

以下代码在合成的聚类数据上构建 IVF 索引，扫描 $\mathrm{nprobe}$ 并报告 Recall@10 与单查询延迟。运行环境为 Python 3.12 与 NumPy 2.3，不依赖 faiss。

```python
import time

import numpy as np

rng = np.random.default_rng(20261018)
N, dim, C, NQ, K = 20000, 64, 20, 200, 10
centers = rng.normal(size=(C, dim))
labels = rng.integers(0, C, N)
X = centers[labels] + rng.normal(scale=0.75, size=(N, dim))
Q = centers[rng.integers(0, C, NQ)] + rng.normal(scale=0.75, size=(NQ, dim))
X = X.astype(np.float32)
Q = Q.astype(np.float32)

def kmeans(data, k, iters=12, seed=7):
    r = np.random.default_rng(seed)
    cent = data[r.choice(len(data), k, replace=False)].copy()
    for _ in range(iters):
        d2 = (data ** 2).sum(1)[:, None] - 2 * data @ cent.T + (cent ** 2).sum(1)[None, :]
        assign = d2.argmin(1)
        for j in range(k):
            m = assign == j
            if m.any():
                cent[j] = data[m].mean(0)
    return cent, assign

t0 = time.perf_counter()
cent, assign = kmeans(X, 64)
print(f"k-means 训练 64 个聚类中心耗时 {time.perf_counter() - t0:.2f} s")

# 精确检索：一次矩阵乘法得到全部查询的 top-10
t0 = time.perf_counter()
exact = np.argsort(-(Q @ X.T), axis=1)[:, :K]
exact_ms = (time.perf_counter() - t0) * 1000 / NQ

# 倒排表：每个簇保存成员下标
lists = [np.where(assign == j)[0] for j in range(64)]

def ivf_search(q, nprobe):
    csim = cent @ q
    cells = np.argsort(-csim)[:nprobe]
    cand = np.concatenate([lists[c] for c in cells])
    scores = X[cand] @ q
    return cand[np.argsort(-scores)[:K]]

print(f"\n精确检索：Recall@10=1.0000，平均每查询 {exact_ms:.2f} ms，扫描 {N} 条向量")
print("nprobe  候选数  Recall@10   每查询 ms")
for nprobe in (1, 2, 4, 8, 16, 32, 64):
    t0 = time.perf_counter()
    approx = np.array([ivf_search(Q[i], nprobe) for i in range(NQ)])
    ms = (time.perf_counter() - t0) * 1000 / NQ
    hits = sum(len(set(map(int, approx[i])) & set(map(int, exact[i]))) for i in range(NQ))
    cand_avg = np.mean([sum(len(lists[c]) for c in np.argsort(-(cent @ Q[i]))[:nprobe])
                        for i in range(NQ)])
    print(f"{nprobe:>6}  {cand_avg:>7.0f}  {hits / (NQ * K):>9.4f}  {ms:>9.3f}")
```

```text
k-means 训练 64 个聚类中心耗时 0.17 s

精确检索：Recall@10=1.0000，平均每查询 0.91 ms，扫描 20000 条向量
nprobe  候选数  Recall@10   每查询 ms
     1      476     0.6070      0.042
     2      785     0.7965      0.053
     4     1340     0.9665      0.113
     8     2470     1.0000      0.279
    16     4751     1.0000      0.683
    32     9688     1.0000      1.687
    64    20000     1.0000      3.893
```

上表中的毫秒数是单次运行的记录，随机器负载与实现语言波动；候选数与召回率由数据与参数决定，可以复现。曲线给出三个可复用的结论。第一，$\mathrm{nprobe}$ 从 1 增到 4 时召回从 0.607 升到 0.967，候选数只增加约 2.8 倍，这是 IVF 的主要收益区间。第二，$\mathrm{nprobe}=8$ 时召回达到 1.000 并饱和，原因是合成数据的簇间分离明显，真实语料的近邻会跨越桶边界，召回通常不会饱和。第三，$\mathrm{nprobe}=64$ 时单查询 3.893 ms 反而高于精确检索的 0.91 ms：精确检索把 200 个查询合并为一次矩阵乘法，IVF 的 Python 循环与候选收集开销在小规模下占主导，而真实系统的索引由 C++ 或 GPU 实现，常数不同但趋势一致。因此延迟数字只能在同一实现内比较，不能跨实现引用。

### 例 2：FAISS 的 IndexFlatIP 与 IndexIVFFlat

FAISS 需要单独安装（`pip install faiss-cpu` 或 `faiss-gpu`）。以下脚本在缺少 faiss 时自动退化为 NumPy 精确检索，在安装后执行完整分支。

```python
import numpy as np

try:
    import faiss
except ImportError:
    faiss = None

rng = np.random.default_rng(7)
C, d, per, nq, k = 20, 64, 1000, 200, 10
centers = rng.normal(size=(C, d))
xb = centers[rng.integers(0, C, C * per)] + rng.normal(scale=0.75, size=(C * per, d))
xq = centers[rng.integers(0, C, nq)] + rng.normal(scale=0.75, size=(nq, d))
xb = (xb / np.linalg.norm(xb, axis=1, keepdims=True)).astype("float32")
xq = (xq / np.linalg.norm(xq, axis=1, keepdims=True)).astype("float32")
print("xb", xb.shape, "xq", xq.shape)

def recall_at_k(approx, exact, k):
    return float(np.mean([len(set(map(int, a)) & set(map(int, e))) / k
                          for a, e in zip(approx, exact)]))

exact = np.argsort(-(xq @ xb.T), axis=1)[:, :k]
print(f"精确检索基线 Recall@10 = 1.0000，I 形状 {exact.shape}")

if faiss is None:
    print("未安装 faiss：跳过 FAISS 分支，安装 faiss-cpu 后同一脚本会打印两行召回率")
else:
    flat = faiss.IndexFlatIP(d)
    flat.add(xb)
    D_flat, I_flat = flat.search(xq, k)
    print("IndexFlatIP Recall@10 =", round(recall_at_k(I_flat, exact, k), 4),
          "I 形状", I_flat.shape)

    quantizer = faiss.IndexFlatIP(d)
    ivf = faiss.IndexIVFFlat(quantizer, d, 64, faiss.METRIC_INNER_PRODUCT)
    print("训练前 is_trained =", ivf.is_trained)
    ivf.train(xb)
    ivf.add(xb)
    ivf.nprobe = 8
    D_ivf, I_ivf = ivf.search(xq, k)
    print("训练后 is_trained =", ivf.is_trained, "ntotal =", ivf.ntotal)
    print("IndexIVFFlat(nprobe=8) Recall@10 =", round(recall_at_k(I_ivf, exact, k), 4))
```

```text
xb (20000, 64) xq (200, 64)
精确检索基线 Recall@10 = 1.0000，I 形状 (200, 10)
未安装 faiss：跳过 FAISS 分支，安装 faiss-cpu 后同一脚本会打印两行召回率
```

这段代码演示 FAISS 的三条契约。第一，向量必须是 `float32` 且内存连续，`np.linalg.norm` 的归一化在 float64 上完成后要显式转换。第二，IVF 必须先 `train` 再 `add`，训练前 `is_trained` 为 `False`，直接 `add` 会抛出异常；训练样本不足时 FAISS 给出警告，质心质量下降。第三，`nprobe` 是查询期参数，可在每次查询前修改，`IndexFlatIP` 没有该参数。`search` 返回两个数组：`D` 为得分（内积），`I` 为下标，形状均为 `(nq, k)`；越界位置以 -1 填充。

由于本机未安装 faiss，输出块只包含 NumPy 基线。安装后同一脚本会多打印 `IndexFlatIP` 与 `IndexIVFFlat` 的召回率，二者都应接近 1.0000，因为数据只有 20 个分离良好的簇且已归一化；差异出现在更大规模或更难的数据上。

### 例 3：内存与压缩估算

```python
n, d = 10 ** 7, 768
raw = n * d * 4
print(f"{n:.0e} 条 {d} 维 float32 向量：{raw / 2**30:.2f} GiB")
print(f"PQ m=96：{n * 96 / 2**30:.2f} GiB，压缩比 {raw / (n * 96):.1f}")
for M in (16, 32, 64):
    graph = n * (2 * M + 1) * 4
    print(f"HNSW M={M}：邻接表 {graph / 2**30:.2f} GiB，合计 {(raw + graph) / 2**30:.2f} GiB")
```

```text
1e+07 条 768 维 float32 向量：28.61 GiB
PQ m=96：0.89 GiB，压缩比 32.0
HNSW M=16：邻接表 1.23 GiB，合计 29.84 GiB
HNSW M=32：邻接表 2.42 GiB，合计 31.03 GiB
HNSW M=64：邻接表 4.81 GiB，合计 33.42 GiB
```

估算用于容量规划，不用于精确计费。实际内存还要加上索引对象开销、id 映射、元数据、副本与构建临时空间；HNSW 的邻接表在删除后保留墓碑，实际占用会高于公式值。

## 易错点

> [!warning] 以下六条均可在索引日志、召回实验或内存监控中直接检验。
> 1. 训练与查询的度量不一致：IVF 用 L2 训练、查询按内积排序，或写入未归一化而查询归一化。检验方法是比较同一批查询在精确内积与索引结果上的前 10 条重合率，若显著低于基线，先检查归一化。
> 2. 用不具代表性的样本训练 IVF 或 PQ：训练集若来自旧数据或某个租户，其他区域的查询召回率会系统性偏低。训练样本应随机抽取且覆盖线上分布，样本量至少为 $\mathrm{nlist}$ 的 30 倍。
> 3. 低选择率下使用后过滤：$s=0.01$ 时要取 $1000$ 条候选才能得到 10 条结果，延迟放大百倍且可能不足 $k$。应改为预过滤、分区或过滤式遍历。
> 4. 删除后不重建：墓碑比例上升后，HNSW 的有效节点减少、路径变长，召回率与吞吐同时下降。应在墓碑比例超过 10% 到 20% 时重建，并监控该比例。
> 5. 只调 $\mathrm{efSearch}$ 而不重建：图结构本身缺少连通边时，增大查询预算只能遍历更多局部节点，召回率不会恢复到目标值。应先增大 $M$ 与 $\mathrm{efConstruction}$ 重建。
> 6. 跨实现比较延迟：NumPy、faiss-cpu、GPU 实现的常数差异可达两个数量级，用论文或博客的延迟数字做容量规划会严重偏离。所有延迟必须在目标硬件与目标实现上实测。

## 关联笔记

- 前置 [[Embedding与向量检索]]：本篇的索引以该篇的度量与归一化为前提，内积、余弦与 L2 的等价关系决定了索引度量能否替换。
- 后续 [[RAG原理与流程]]：索引只是检索阶段的一半，召回结果如何进入提示词、如何与生成器配合，在该篇展开。
- 后续 [[检索优化与重排Rerank]]：ANN 返回的候选通常还要经交叉编码器重排，本篇的召回率决定重排的上限。
- 对照 [[模型推理优化]]：两者都在延迟、内存与质量之间取舍，区别在于前者优化检索，后者优化生成。
- 后续 [[RAG评估]]：召回率、延迟与内存的报告方式应与该篇的评估协议一致，否则跨版本比较没有意义。

## 达标检测

- [ ] 写出精确检索的时间与空间复杂度，并估算 $N=10^{7}$、$d=768$ 时向量占用的字节数。
- [ ] 描述 HNSW 的插入过程，说明启发式邻居选择条件 $d(e,x)<d(e,r)$ 的作用；解释去掉该条件后图结构会如何退化。
- [ ] 给定 $N=10^{6}$、$\mathrm{nlist}=4096$、$\mathrm{nprobe}=64$，估算 IVF 的候选数与相对暴力检索的加速比。
- [ ] 计算 $d=768$、$m=96$、$n_{\text{bits}}=8$ 时的 PQ 压缩比与 $10^{7}$ 条向量的码大小，并说明 $m$ 减半的代价。
- [ ] 用本篇代码把 $\mathrm{nprobe}$ 固定为 4，改变数据簇间间隔，记录召回率变化并解释原因。
- [ ] 设计一个过滤选择率为 0.5% 的查询场景，比较后过滤与分区的延迟与召回，给出选择依据。

## 参考来源

- Malkov & Yashunin, "Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs", arXiv:1603.09320, 2018 —— 对应第 3 节的多层图结构、插入与搜索算法、启发式邻居选择与参数分析。
- Jégou, Douze & Schmid, "Product Quantization for Nearest Neighbor Search", IEEE TPAMI 33(1), 2011 —— 对应第 5 节的分段量化、ADC 距离计算与压缩率分析。
- Johnson, Douze & Jégou, "Billion-scale similarity search with GPUs", arXiv:1702.08734, 2017 —— 对应 FAISS 的索引组织方式与 GPU 实现，第 8 节的选型对比以其为背景。
- FAISS 官方文档与 wiki（github.com/facebookresearch/faiss/wiki）—— 对应第 3、4、5 节的索引参数、训练要求与 `IndexFlatIP`、`IndexIVFFlat` 的接口。
- Milvus 官方文档（milvus.io/docs）—— 对应第 8 节的分布式架构、索引类型与标量过滤能力。
- pgvector 官方仓库（github.com/pgvector/pgvector）—— 对应第 6 节的操作符与索引类绑定、第 8 节的维度上限与事务语义。
