向量索引——从暴力搜索到 HNSW 与 IVF

摘要

向量索引是向量数据库的核心竞争力，其本质是解决高维空间中的 ANN（Approximate Nearest Neighbor，近似最近邻） 问题——以少量精度损失换取数量级的查询速度提升。本文从暴力搜索的性能极限出发，系统推导为什么精确 KNN 在大规模场景下不可行，然后逐一深度解析三类主流 ANN 算法：IVF（倒排文件索引） 的量化聚类思想、HNSW（分层可导航小世界图） 的图导航机制、以及 DiskANN 的磁盘友好型图索引设计。理解这三类算法的原理与工程取舍，是在 Milvus 中为不同业务场景选择合适索引的前提。文末提供系统化的索引选型决策框架。

第 1 章问题定义——高维空间的近邻搜索

1.1 KNN 问题的形式化定义

给定：

数据集 $X = {x_{1}, x_{2}, \dots, x_{N}}$ ，每个 $x_{i} \in R^{D}$
查询向量 $q \in R^{D}$
距离函数 $d (q, x)$ （欧式距离、余弦距离或内积）

目标：找到 $K$ 个最近邻 ${x_{i_{1}}, \dots, x_{i_{K}}} \subseteq X$ ，使得 $d (q, x_{i_{j}}) \leq d (q, x_{l})$ 对所有 $l \in / {i_{1}, \dots, i_{K}}$ 成立。

精确 KNN（Exact KNN） 的朴素实现：遍历所有 N 个向量，计算与查询向量的距离，排序后返回前 K 个。时间复杂度 O(N × D)，对于 N=100 万、D=768：

计算次数：7.68 亿次浮点乘法
单核计算能力约 10^9 FLOPS
理论耗时 ≈ 0.77 秒（单核，不考虑内存带宽）
实际耗时 100ms~500ms（受内存带宽限制）

对于需要 P99 < 50ms 的在线服务，精确 KNN 完全不可用。

1.2 距离度量的选择

向量检索中常用的三种距离度量，含义和适用场景各不相同：

距离度量	公式	特点	适用场景
欧式距离（L2）	$d = \sum (q_{i} - x_{i})^{2}$	感知绝对位置差异	图像特征、坐标点
余弦相似度（Cosine）	$cos θ = \frac{q \cdot x}{∥ q ∥∥ x ∥}$	感知方向（角度）差异，忽略模长	文本语义（NLP Embedding）
内积（Inner Product）	$IP = q \cdot x = \sum q_{i} x_{i}$	同时感知方向和模长	推荐系统（用户-商品得分）

核心概念

为什么 NLP 场景偏爱余弦相似度？ 文本 Embedding 模型（如 BERT、Sentence-BERT）的输出向量，其模长（向量的 L2 范数）通常与文本的信息量相关，而不是语义相似度的直接体现。两段含义相似的文本，一段短一段长，其向量模长可能差异很大，但方向（角度）接近。余弦相似度通过归一化消除模长影响，只关注方向，因此更准确地捕捉语义相似度。在实践中，通常先对向量做 L2 归一化（使模长=1），然后用内积代替余弦相似度计算（数学等价，但内积计算更快）。

1.3 高维空间的”维度诅咒”

高维空间中存在一个令人反直觉的现象：维度越高，所有点之间的距离差异越小。

数学上，在 D 维超球面上均匀采样的两点，其距离的期望值为 $2$ （归一化后），且随着 D 增大，距离的方差趋向于 0——也就是说，任意两个高维向量的距离趋向于相等。这被称为维度诅咒（Curse of Dimensionality）。

维度诅咒对 ANN 算法的含义：在高维空间中，“近邻”和”远邻”之间的距离差异很小，使得精确区分它们变得困难。基于树的空间分割方法（如 KD-Tree）在低维（D < 20）时效果很好，但在高维（D > 100）时退化为接近线性扫描。这也是为什么 HNSW 这类基于图的方法能在高维场景下优于树形方法——图导航通过逐步逼近的贪心策略，不依赖全局的空间分割。

第 2 章 IVF——基于量化的分区检索

2.1 IVF 的核心思想

IVF（Inverted File Index，倒排文件索引） 的名字来自信息检索领域的”倒排索引”，但在向量搜索中，其实质是一种基于聚类的空间分区方法。

IVF 的核心思想极其直观：

离线建索引：用 K-Means 算法将数据集中的 N 个向量聚类为 nlist 个簇（cluster），每个簇有一个质心（centroid）向量
建立倒排表：对于每个质心，维护一个”倒排列表”，记录属于该簇的所有向量的 ID（和可选的向量数据）
在线查询：给定查询向量 q，先找到与 q 最近的 nprobe 个质心，然后只在这 nprobe 个簇的倒排列表中搜索

IVF 结构示意（nlist=4 个簇）：

质心 C1 (100, 200)  →  倒排列表 [v1, v5, v9, v12, ...]
质心 C2 (300, 100)  →  倒排列表 [v2, v6, v10, ...]
质心 C3 (500, 400)  →  倒排列表 [v3, v7, v11, ...]
质心 C4 (200, 500)  →  倒排列表 [v4, v8, ...]

查询向量 q=(310, 120)：
  最近质心 = C2（距离最小）
  nprobe=1：只在 C2 的倒排列表中搜索
  nprobe=2：在 C2、C1 的倒排列表中搜索

为什么 IVF 能加速？ 假设 N=100 万，nlist=1000，则每个簇平均有 1000 个向量。设置 nprobe=10，每次查询只需搜索 10 × 1000 = 1 万个向量，比全量搜索的 100 万快了 100 倍，同时仍能覆盖查询向量附近的大多数近邻（因为近邻通常在最近的几个簇中）。

2.2 IVF_FLAT——最简单的 IVF 实现

IVF_FLAT 是最基础的 IVF 实现：倒排列表中存储原始向量数据（FLAT 表示”平铺”，不做任何压缩）。

nlist 参数的选择：

nlist 太小：每个簇包含太多向量，单次搜索代价过高，与全量搜索差距不大
nlist 太大：每个簇只有很少向量，质心精度高，但建立索引需要更多 K-Means 迭代时间，且 nprobe 需要相应增大才能保证 Recall

经验规则：nlist ≈ 4 × sqrt(N)。例如，N=100 万，nlist ≈ 4000。

nprobe 参数的选择：

nprobe=1：速度最快，但 Recall 最低（近邻可能在相邻簇中）
nprobe=nlist：退化为全量搜索，速度最慢，Recall=100%

nprobe 是查询时的参数（不影响索引结构），可以实时调整。通常设置 nprobe=nlist/10 作为起点，根据实际 Recall 调整。

IVF_FLAT 的内存占用：与原始向量数据相同（N × D × 4 字节）。100 万个 768 维 float32 向量 ≈ 3GB。内存占用是 IVF_FLAT 在超大规模场景下的主要限制。

2.3 IVF_SQ8——标量量化压缩

IVF_SQ8（Scalar Quantization 8-bit） 在 IVF_FLAT 的基础上，将每个浮点数（32位，float32）量化为 8 位整数（uint8），空间压缩为原来的 1/4。

量化原理：对每个向量维度，找到数据集中该维度的最小值和最大值，然后将 [min, max] 区间均匀分为 256 份（8 位整数的范围），每个向量的该维度值被映射到最近的区间标识（0~255）。

精度损失：量化引入误差（每个维度最多 (max-min)/256 的误差），导致距离计算不精确，最终 Recall 略有下降（通常约 1%~5%）。

选择 IVF_SQ8 的条件：内存紧张，且能接受轻微 Recall 损失（如工程上只需 95%+ 的 Recall）。

2.4 IVF_PQ——乘积量化的极致压缩

IVF_PQ（Product Quantization） 是 ANN 领域最重要的量化技术，由 Jégou 等人在 2011 年提出，其压缩率远超 SQ8。

乘积量化的基本思想：将 D 维向量分割为 M 个子向量（每段 D/M 维），对每段子向量独立进行 K-Means 聚类（每段 256 个质心），每段子向量用最近质心的 ID（8 位，0~255）代替。

PQ 编码示意（D=128, M=8, 每段 D/M=16 维）：

原始向量（128维 float32，512字节）：
[0.1, 0.3, ..., 0.7, | 0.2, 0.8, ..., 0.4, | ... | 0.9, 0.1, ..., 0.6]
  第1段(16维)           第2段(16维)               第8段(16维)

PQ 编码（8字节！）：
[23, 145, 67, 201, 8, 178, 95, 42]
 ↑段1的质心ID ↑段2的质心ID ... ↑段8的质心ID

压缩率：512 字节 → 8 字节 = 64x 压缩！

ADC（Asymmetric Distance Computation，非对称距离计算）：查询时，不需要解码 PQ 编码回原始向量。而是对查询向量也分为 M 段，预先计算查询的每段子向量与该段所有 256 个质心的距离（查找表，M × 256 个距离值），然后对每个数据点，其与查询的近似距离 = M 段距离的累加和（O(M) 的查找操作，远快于 O(D) 的全量计算）。

IVF_PQ 的 Recall 代价：PQ 量化引入了较大的近似误差，Recall 通常比 IVF_FLAT 低 5%~15%，需要通过增大 nprobe 来补偿。实践中，IVF_PQ 在内存节省 50x 的同时，通过适当增大 nprobe 可以将 Recall 维持在 90%~95% 以上。

索引类型	内存占用	查询速度	Recall	适用场景
IVF_FLAT	高（原始大小）	中	高（≈100%）	内存充裕，追求精度
IVF_SQ8	中（1/4 原始）	中-高	中-高（95%+）	内存有限，精度要求较高
IVF_PQ	极低（可达 1/64）	高（ADC 加速）	中（90%+）	超大规模，内存极其有限

第 3 章 HNSW——图导航的极致

3.1 从 NSW 到 HNSW——小世界图的演进

HNSW（Hierarchical Navigable Small World） 由 Yury Malkov 和 Dmitry Yashunin 于 2016 年提出（论文：Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs），是目前在高 Recall 高 QPS 场景下性能最优的 ANN 算法之一。

要理解 HNSW，需要先理解其前身 NSW（Navigable Small World）。

小世界网络（Small World Network） 的概念来自社会学：在 Facebook 的朋友关系网络中，任意两个用户之间的”平均最短路径”约为 4~5 度（“六度分隔”理论）。小世界网络的特点是：网络中同时存在大量的”局部密集连接”（朋友的朋友互为朋友）和少量的”远程桥接连接”（跨越地域的弱关系），使得网络既有局部聚类性，又有全局快速导航性。

NSW 将这一思想引入向量搜索：将数据集的所有向量构建为一个可导航图（Navigable Graph），每个向量作为图的节点，节点之间的边代表”这两个向量在高维空间中相对较近”。查询时，从某个入口节点出发，贪心地沿着边向更近邻的方向移动，直到找不到更近的邻居为止（局部最优解），近似 KNN 搜索转化为图上的贪心遍历。

NSW 的问题：当数据量较大时，单层图的构建会导致某些节点连接了很多长距离边（为了保证全局可达性），使得查询路径中的”起步阶段”需要跨越很多长路径，效率较低。

HNSW 的改进：引入多层结构，解决了 NSW 的粗粒度定位问题：

最底层（Layer 0）：所有节点都在此层，每个节点有 M 条边连接其最近邻（稠密连接，精确定位）
上层（Layer 1, 2, …）：只有随机选择的节点子集存在，层级越高节点越少，每个节点有 Mmax 条边（稀疏连接，快速定位大范围）
每个节点出现在层级 L 的概率为 $e^{- L \cdot m_{L}}$ （ $m_{L}$ 是层间概率参数，通常 $m_{L} = 1/ ln (M)$ ）

3.2 HNSW 的图结构与查询过程

HNSW 分层结构示意（4层，共8个节点）：

Layer 3（最高层，极稀疏）：  [v7]
                               |
Layer 2（稀疏）：      [v2] ---[v5]--- [v7]
                         \     |
Layer 1（较密）：  [v1]-[v2]-[v4]-[v5]-[v7]-[v8]
                   |         \        /
Layer 0（最密，所有节点）：
         [v1]-[v2]-[v3]-[v4]-[v5]-[v6]-[v7]-[v8]
              各节点都与其最近的M个邻居有边连接

查询过程（ef_search=100，top_k=10）：

起点：从最高层的入口节点（Entry Point，通常是随机的或最近插入的高层节点）开始
逐层下降（从高层到 Layer 1）：在每层执行贪心搜索——从当前节点出发，检查其所有邻居，选择与查询向量最近的邻居作为下一步，重复直到当前节点比其所有邻居都更近（局部最优）。然后以该局部最优节点为入口，下降到下一层重新开始贪心搜索。
Layer 0 精细搜索：到达 Layer 0 后，不再使用单点贪心，而是维护一个大小为 ef_search 的候选集（优先级队列，按与查询的距离排序），迭代地扩展候选集（检查候选集中每个节点的邻居，若更近则加入候选集），直到候选集不再更新。从候选集中取前 K 个即为最终结果。

为什么分层能加速？ 高层的稀疏图提供了”全局导航”能力——用很少的步数就能从远处快速跳跃到查询向量所在区域的附近；低层的稠密图提供了”局部精确搜索”能力——在已经定位到正确区域后，精确找到最近的 K 个邻居。这与跳跃表（SkipList，参见 02 MemTable 与 SkipList）的多层索引思想异曲同工。

3.3 HNSW 的构建过程

HNSW 的索引构建是逐点插入的过程，每插入一个新节点 $v$ ：

随机决定节点的最高层级： $l = ⌊ - ln (random()) \cdot m_{L} ⌋$ ，每层出现概率指数递减
从最高层向下，找插入位置：在高于节点最高层级的层（ $l + 1$ 到最高层），每层做单点贪心搜索定位大致区域
在节点所在的每层（ $0$ 到 $l$ ）做精细搜索：用 ef_construction 大小的候选集搜索 M 个最近邻，作为新节点的边
对边进行剪枝（Heuristic Pruning）：当一个节点的邻居数量超过 M 时，不简单保留最近的 M 个，而是使用启发式算法——保留那些能”多样化覆盖”不同方向的邻居，避免所有边都指向同一区域。这提高了图的连通性和导航效率。

HNSW 关键参数：

M（构建时参数）：
  每个节点在 Layer 0 的最大边数（Layer 0 实际最大为 2M，其他层为 M）
  默认值：16。越大 Recall 越高，但构建时间和内存占用成比例增加

ef_construction（构建时参数）：
  构建索引时每次插入使用的候选集大小（决定图的质量）
  默认值：200。越大图质量越好，Recall 越高，但构建越慢
  建议：ef_construction >= 2M（经验规则）

ef_search（查询时参数）：
  查询时的候选集大小，可以实时调整，不影响索引结构
  必须满足：ef_search >= K（top_k 的数量）
  越大 Recall 越高，查询越慢

3.4 HNSW 的内存占用分析

HNSW 的内存占用由两部分组成：

原始向量数据：N × D × 4 字节（float32）
图结构（邻接表）：N × M × 2 × 4 字节（每个节点在 Layer 0 最多 2M 条边，每条边存储目标节点 ID，4 字节）

对于 N=100 万、D=768、M=16：

原始向量：100万 × 768 × 4 = 3 GB
图结构：100万 × 16 × 2 × 4 = 128 MB
总计约 3.1 GB（图结构相对原始向量较小，主要成本在向量存储）

与 IVF_PQ 相比，HNSW 的内存占用远高（IVF_PQ 可将向量压缩到几十 MB），但 Recall 和 QPS 性能更优。

生产避坑

HNSW 的内存占用在加载时是一次性的，必须将整个索引（包括所有向量数据）加载到 Query Node 的内存中才能查询。对于数十亿向量的场景（如 100 亿 × 768 维 = 300 GB），单机内存无法承载，必须考虑 DiskANN 或 IVF_PQ 等磁盘/压缩方案。Milvus 支持 HNSW 索引的分片（通过多个 Segment 分布到多个 Query Node），但每个 Segment 仍需完整加载到单个 Query Node 的内存中。

第 4 章 DiskANN——磁盘友好的图索引

4.1 为什么需要 DiskANN

HNSW 是内存型索引，必须将整个索引加载到内存中。当向量规模达到十亿级时，内存成本变得难以承受（数百 GB 甚至 TB 级别的内存需求）。

DiskANN 由 Microsoft Research 于 2019 年提出（论文：DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node），其核心目标是：在单台服务器的 SSD 上，对十亿规模的向量数据集实现低延迟 ANN 搜索，而不需要将完整索引加载到内存。

4.2 DiskANN 的设计思想

DiskANN 的核心是 Vamana 图——一种专门为磁盘访问模式优化的图索引。与 HNSW 不同，Vamana 图是单层图（不分层），但通过精心设计的边剪枝策略保证了图的导航性。

磁盘友好性的关键设计：

PQ 压缩版本放内存，原始向量放 SSD：将每个向量的 PQ 压缩版本（几十字节）全部加载到内存，原始向量（768 × 4 字节）存储在 SSD 上。查询时，先在内存中用 PQ 版本做粗粒度搜索（确定候选集），再从 SSD 上读取候选集中向量的原始数据做精确距离计算，最终返回 Top-K。
节点布局优化（Beam Search 友好）：DiskANN 在 SSD 上存储图时，将每个节点的邻接表和向量数据打包在一起，存储在连续的磁盘扇区中（通常 4KB 对齐）。查询时，读取一个节点只需一次 SSD 随机读取，避免了多次小 IO。
Beam Search（束搜索）：查询时不使用贪心的单点扩展（每步只走一个节点），而是同时维护 beam_width 个候选节点，每步批量发出 beam_width 次 SSD 读请求（并行 IO）。SSD 的随机 IO 并发能力（NVMe SSD 通常支持 100K+ IOPS）充分利用了多个 IO 请求的并行性。

DiskANN 的内存-SSD 分层结构：

内存（约几 GB）：
  - PQ 压缩向量（每向量 32~64 字节）：快速粗粒度过滤
  - 图的邻接表（每节点的邻居 ID 列表）

SSD（TB 级）：
  - 原始向量数据（每向量 3072 字节@768维）：精确距离计算
  - 与邻接表打包存储（相邻 IO）

4.3 DiskANN vs HNSW 的对比

维度	HNSW	DiskANN
索引存储位置	全内存	SSD（原始向量）+ 少量内存（PQ）
内存占用	高（N × D × 4 字节）	低（N × PQ_bytes + 邻接表）
适用规模	千万级（内存可承载）	十亿级（内存承载不了）
查询延迟	低（~1ms）	中（~~5ms~~20ms，受 SSD IO 延迟影响）
构建时间	较快（小时级）	较慢（十亿级可能需要数天）
Recall	高（95%~99%）	高（95%~99%，经 PQ 再精算后）

DiskANN 是用延迟换容量的选择：接受比 HNSW 高 5~~20 倍的查询延迟，换取能够处理 10~~100 倍数据量的能力。

第 5 章 GPU 加速索引

5.1 GPU 向量检索的优势

向量检索的核心操作（批量浮点乘法和加法）天然适合 GPU 并行计算。一块 A100 GPU 拥有 6912 个 CUDA 核心，理论峰值算力约 312 TFLOPS（FP16），是 CPU 的 100~1000 倍。

GPU 向量检索适合的场景：批量查询（Batch Query）——同时处理大批量查询向量（如每次 1000 个查询向量），充分利用 GPU 的并行计算能力。对于单条查询的低延迟场景，GPU 的优势相对有限（受 PCIe 数据传输延迟影响）。

5.2 Milvus 支持的 GPU 索引

Milvus 通过 FAISS（Facebook AI Similarity Search）库支持 GPU 加速：

GPU_IVF_FLAT：IVF 的 GPU 版本。搜索速度比 CPU 版本快 10~100 倍，适合高 QPS 的批量查询场景。索引数据存储在 GPU 显存中（如 A100 有 80GB 显存），限制了可索引的向量数量。

GPU_IVF_PQ：IVF_PQ 的 GPU 版本。利用 GPU 的 SIMD 能力加速 PQ 距离计算。在 GPU 显存中通过 PQ 压缩存储更多向量，查询速度比 CPU 版本快约 50~200 倍。

第 6 章索引选型决策框架

6.1 核心权衡维度

选择向量索引需要在以下五个维度上做权衡：

Recall（召回率）：返回的 K 个结果中，有多少是真正的 Top-K？计算公式：Recall = |ANN 结果 ∩ 精确 KNN 结果| / K
QPS（每秒查询次数）：系统在满足 Recall 要求的前提下，每秒能处理多少查询请求？
内存/存储占用：索引占用多少内存/SSD？直接决定硬件成本
构建时间：建立索引需要多久？对于频繁更新的场景（如新数据不断导入），构建时间至关重要
延迟（Latency）：单次查询的 P99 延迟，对在线服务至关重要

6.2 Milvus 中各索引的参数与 Recall-QPS 曲线

不同 nprobe / ef_search 参数下，各索引的 Recall-QPS 权衡（SIFT-1M 数据集，768 维，100 万向量，单节点）：

索引类型	Recall@10	QPS（单核）	内存占用	适用场景
FLAT（暴力）	100%	100	3 GB	准确度优先，数据量 < 100 万
IVF_FLAT（nprobe=64）	99%	800	3 GB	高精度，内存足够
IVF_SQ8（nprobe=64）	97%	1200	768 MB	精度/内存均衡
IVF_PQ（nprobe=128）	93%	3000	60 MB	超大规模，内存极限
HNSW（ef=128）	99%	5000	3.1 GB	高精度高 QPS，内存足够
DiskANN（beam=8）	96%	500	300 MB RAM + SSD	十亿级，内存受限

6.3 选型决策树

向量索引选型决策：

数据量 < 100 万？
  是 → 追求完美 Recall？
       是 → FLAT（暴力搜索，无索引）
       否 → 追求高 QPS？
            是 → HNSW（ef_search 可调，QPS 最高）
            否 → IVF_FLAT（内存充裕）/ IVF_SQ8（内存有限）

数据量 100 万 ~ 1 亿？
  内存充裕（> 10GB）？
    是 → HNSW（最佳 Recall-QPS 权衡）
    否 → IVF_PQ（极致内存压缩）

数据量 > 1 亿？
  有大量 GPU 资源？
    是 → GPU_IVF_PQ（GPU 批量加速）
    否 → DiskANN（SSD + 少量内存）

设计哲学

没有”最好”的向量索引，只有最适合业务场景的索引。HNSW 在学术 benchmark 上几乎总是赢家，但在生产环境中，内存成本、构建时间、增量写入支持往往比纯粹的 Recall@QPS 更重要。选择索引时，永远从业务 SLA（服务等级协议）出发：P99 延迟要求多少？可以接受的 Recall 下限是多少？每月的内存成本预算是多少？

第 7 章 Milvus 中的索引构建与管理

7.1 索引构建的触发时机

在 Milvus 中，向量索引是延迟构建的：数据插入后先存储为 Growing Segment（无索引，暴力搜索），当 Segment 被 Sealed 并 Flushed 到对象存储后，Index Coordinator 才调度 Index Node 构建索引。

这种设计的好处是：

索引构建是 CPU 密集型操作，延迟到数据稳定后再构建，避免频繁对变化中的数据重建索引
构建任务可以根据 Index Node 的资源情况调度，不影响写入路径

实时性影响：Growing Segment 的数据没有索引，查询时暴力搜索。若某个 Segment 刚刚 Flushed，在 Index Node 完成索引构建之前，该 Segment 的查询延迟仍然较高。对于数据量大的 Sealed Segment（如 2GB），HNSW 构建可能需要 30~60 分钟，在此期间查询走暴力路径。

7.2 索引参数的 Milvus API

# Milvus Python SDK 示例：创建 HNSW 索引
 
from pymilvus import Collection, FieldSchema, CollectionSchema, DataType
 
# 创建 Collection
fields = [
    FieldSchema(name="id", dtype=DataType.INT64, is_primary=True),
    FieldSchema(name="embedding", dtype=DataType.FLOAT_VECTOR, dim=768),
    FieldSchema(name="category", dtype=DataType.VARCHAR, max_length=64),
]
schema = CollectionSchema(fields=fields, description="文档向量库")
collection = Collection(name="docs", schema=schema)
 
# 创建 HNSW 索引
index_params = {
    "metric_type": "COSINE",   # 距离度量：L2 / COSINE / IP
    "index_type": "HNSW",
    "params": {
        "M": 16,               # 每个节点的最大边数
        "efConstruction": 200, # 构建时的候选集大小
    }
}
collection.create_index(
    field_name="embedding",
    index_params=index_params
)
 
# 查询时的 search_params
search_params = {
    "metric_type": "COSINE",
    "params": {"ef": 128}      # 查询时的候选集大小，ef >= top_k
}
results = collection.search(
    data=[query_embedding],
    anns_field="embedding",
    param=search_params,
    limit=10,                   # top_k=10
    expr="category == 'tech'"   # 标量过滤
)

第 8 章小结

8.1 三类算法的本质差异

IVF：用量化（聚类/压缩）换内存，以空间换时间。本质是通过预先分组缩小搜索空间，适合内存有限但能接受一定 Recall 损失的场景
HNSW：用图的多层导航实现精确定位，Recall 和 QPS 均优秀，但内存开销大，适合内存充裕的中等规模场景
DiskANN：用 SSD 替代内存存储原始向量，通过 PQ 在内存中做粗过滤，适合超大规模（十亿级）且内存受限的场景

8.2 后续章节导引

03 数据模型——Collection、Partition 与 Segment：深入 Milvus 的 Schema 设计和数据导入机制，理解 Segment 状态机与索引的关联
04 查询引擎——混合检索与过滤：理解标量过滤与向量检索的协同策略，以及分布式查询的精度保证

思考题

IVF（Inverted File Index）将向量空间划分为多个 Voronoi 单元——查询时只搜索最近的 nprobe 个单元。nprobe 越大召回率越高但搜索越慢。在 100 万 128 维向量上，nprobe=16（总共 1024 个单元）的召回率和 QPS 大约是多少？nprobe 的最优值如何通过实验确定？

HNSW（Hierarchical Navigable Small World）是一种基于图的索引——构建多层跳表结构的图。查询时从最高层开始贪心搜索，逐层下降到最底层。HNSW 的 M（每个节点的最大邻居数）和 ef_construction（构建时搜索宽度）如何影响索引质量和构建时间？HNSW 的内存占用通常是原始向量的多少倍？

Product Quantization（PQ）将高维向量分为多个子向量，每个子向量用聚类中心的 ID 替代——大幅压缩存储空间。128 维向量用 PQ-8 压缩后只需 8 字节（原始 512 字节）。但 PQ 的距离计算是近似的——在什么精度要求下 PQ 的近似误差是可接受的？IVF_PQ 组合索引如何在内存和精度之间取得平衡？

汀的知识碎片

文章导航

02 向量索引——从暴力搜索到 HNSW 与 IVF

向量索引——从暴力搜索到 HNSW 与 IVF

摘要

第 1 章问题定义——高维空间的近邻搜索

1.1 KNN 问题的形式化定义

1.2 距离度量的选择

1.3 高维空间的”维度诅咒”

第 2 章 IVF——基于量化的分区检索

2.1 IVF 的核心思想

2.2 IVF_FLAT——最简单的 IVF 实现

2.3 IVF_SQ8——标量量化压缩

2.4 IVF_PQ——乘积量化的极致压缩

第 3 章 HNSW——图导航的极致

3.1 从 NSW 到 HNSW——小世界图的演进

3.2 HNSW 的图结构与查询过程

3.3 HNSW 的构建过程

3.4 HNSW 的内存占用分析

第 4 章 DiskANN——磁盘友好的图索引

4.1 为什么需要 DiskANN

4.2 DiskANN 的设计思想

4.3 DiskANN vs HNSW 的对比

第 5 章 GPU 加速索引

5.1 GPU 向量检索的优势

5.2 Milvus 支持的 GPU 索引

第 6 章索引选型决策框架

6.1 核心权衡维度

6.2 Milvus 中各索引的参数与 Recall-QPS 曲线

6.3 选型决策树

第 7 章 Milvus 中的索引构建与管理

7.1 索引构建的触发时机

7.2 索引参数的 Milvus API

第 8 章小结

8.1 三类算法的本质差异

8.2 后续章节导引

On this page

Backlinks

汀的知识碎片

文章导航

02 向量索引——从暴力搜索到 HNSW 与 IVF

向量索引——从暴力搜索到 HNSW 与 IVF

摘要

第 1 章 问题定义——高维空间的近邻搜索

1.1 KNN 问题的形式化定义

1.2 距离度量的选择

1.3 高维空间的”维度诅咒”

第 2 章 IVF——基于量化的分区检索

2.1 IVF 的核心思想

2.2 IVF_FLAT——最简单的 IVF 实现

2.3 IVF_SQ8——标量量化压缩

2.4 IVF_PQ——乘积量化的极致压缩

第 3 章 HNSW——图导航的极致

3.1 从 NSW 到 HNSW——小世界图的演进

3.2 HNSW 的图结构与查询过程

3.3 HNSW 的构建过程

3.4 HNSW 的内存占用分析

第 4 章 DiskANN——磁盘友好的图索引

4.1 为什么需要 DiskANN

4.2 DiskANN 的设计思想

4.3 DiskANN vs HNSW 的对比

第 5 章 GPU 加速索引

5.1 GPU 向量检索的优势

5.2 Milvus 支持的 GPU 索引

第 6 章 索引选型决策框架

6.1 核心权衡维度

6.2 Milvus 中各索引的参数与 Recall-QPS 曲线

6.3 选型决策树

第 7 章 Milvus 中的索引构建与管理

7.1 索引构建的触发时机

7.2 索引参数的 Milvus API

第 8 章 小结

8.1 三类算法的本质差异

8.2 后续章节导引

On this page

Backlinks

第 1 章问题定义——高维空间的近邻搜索

第 6 章索引选型决策框架

第 8 章小结