向量索引

向量索引是向量数据库的核心，它将暴力搜索的 $O(n\times d)$ 复杂度降低到近似 $O(\log n\times d)$，代价是损失一定的精度。所有向量索引本质上都是在用空间换时间——通过额外的预处理（构建索引）来加速查询。不同的索引算法在精度、速度、内存占用和构建成本之间做不同的权衡，理解这些权衡是选择合适索引的基础。

暴力搜索（FLAT）

暴力搜索逐个计算查询向量与库中所有向量的距离，返回 TopK。FLAT 是精确搜索，精度 100%，但速度最慢。它的唯一优势是不需要构建索引，适合小规模数据（< 50 万向量）或作为其他索引精度评估的基准。在 Milvus 中，不创建索引时默认使用 FLAT。

IVF（倒排文件）

IVF（Inverted File）的核心思想是"先粗筛再精排"。构建阶段，使用 K-Means 聚类将所有向量分成 nlist 个簇，每个簇有一个质心向量。查询时，先计算查询向量与所有质心的距离，找出最近的 nprobe 个簇，然后只在这些簇内做暴力搜索。这样搜索空间从全库缩小到 nprobe/nlist 的比例。

IVF 的精度和速度完全由 nlist 和 nprobe 两个参数控制。nlist 越大，每个簇越小，精度越高，但构建时间越长、内存开销越大（需要存储 nlist 个质心）。nprobe 越大，搜索的簇越多，精度越高，但搜索越慢。工程上 nlist 通常取 $\sqrt{n}$（n 为向量总数），nprobe 取 8-32。nprobe 是查询时参数，可以在运行时调整，不需要重建索引。

IVF 的构建需要对全量数据做 K-Means 聚类，时间复杂度 $O(n\times nlist\times iter\times d)$，构建较慢但只需要一次。IVF 支持增量插入：新向量分配到最近的簇中，当簇过大时触发局部重聚类。

Milvus 提供了 IVF_FLAT 和 IVF_SQ8 两个变体。IVF_FLAT 直接存储原始向量，精度无损。IVF_SQ8 对向量做标量量化（Scalar Quantization），将 float32 量化为 uint8，内存占用减少到 1/4，代价是精度略有损失。

HNSW（分层可导航小世界图）

HNSW（Hierarchical Navigable Small World）是当前性能最好的向量索引之一，基于图的贪心搜索策略。它构建多层图结构：最上层（L 层）最稀疏，节点最少，越往下越稠密，最底层（L0 层）包含所有节点，连接最密集。每个节点在不同层以概率出现在更高的层，概率公式为 $P(level)=(1/m{)}^{level}$。

搜索从最上层开始，贪心查找最近邻节点，找到最近邻后进入下一层，以该节点为入口继续搜索，逐层向下直到 L0 层。L0 层的搜索精度决定了最终结果的精度。这种分层策略类似于跳表的思路——上层稀疏图用于长距离跳跃，下层稠密图用于局部精细搜索。

HNSW 有三个关键参数。M 是每个节点的最大连接数（默认 16），越大图越稠密，精度越高但内存越大，搜索时间增加 $O(M)$。efConstruction 是构建时的候选队列大小（默认 200），越大构建的图质量越高、精度越好，但构建时间和内存消耗成倍增加。ef 是搜索时的候选队列大小（默认 topK），越大精度越高但搜索越慢，ef 必须大于等于 topK 才有意义。

HNSW 的内存占用较大（每个向量需要存储 M 个邻居的 ID），但搜索延迟极低且精度高，适合中等规模、对延迟敏感的场景。HNSW 构建是增量的，支持实时插入，但删除操作是通过标记实现的，删除的节点仍占用内存，需要定期压缩清理。

ANNOY（近似最近邻 Oh Yeah）

ANNOY（Approximate Nearest Neighbors Oh Yeah）使用随机超平面将高维空间递归分割，构建多棵随机投影树（类似随机森林的思想）。每棵树是一个二叉空间划分，搜索时在所有树中并行查找最近邻，合并去重后返回 TopK。

ANNOY 的优点是索引文件支持内存映射（mmap），内存占用可控——操作系统按需加载索引页到内存，不活跃的页可以换出到磁盘。缺点是构建后的索引是静态的，不支持高效的增量插入和删除，每次数据变更都需要重建索引。ANNOY 适合数据集相对稳定、内存有限但对精度要求不是极高的场景。

DiskANN（磁盘加速索引）

DiskANN 是微软提出的面向超大规模数据（十亿到百亿向量）的磁盘索引方案。它在内存中维护一个 Vamana 图的骨架（每个节点只存少量邻居的 ID 和指针），完整向量数据存储在磁盘上。搜索时，通过内存中的图结构导航，只将必要的向量从磁盘读入内存进行距离计算。

DiskANN 的关键优化是最小化磁盘 I/O 次数。它使用 PQ（Product Quantization）在内存中构建粗糙的距离估计，避免对每个候选节点都读取完整向量。Vamana 图的构建采用贪心剪枝策略，优先保留对导航最有价值的边（即能跳转到远处节点的边），而非简单的最近邻边。

DiskANN 适合数据规模超出内存容量的场景。在内存能装下全量索引时，HNSW 的延迟更低；当内存不足时，DiskANN 是为数不多能保持可接受延迟的方案。

量化技术

量化（Quantization）是压缩向量以减少内存占用的通用技术，可与上述索引组合使用。

标量量化（SQ, Scalar Quantization）将每个维度独立量化：找出每个维度的最小值 min 和最大值 max，将 float32 线性映射到 uint8（256 级）或 uint4（16 级）。SQ 简单高效，压缩比 4:1（uint8）或 8:1（uint4），精度损失较小。

乘积量化（PQ, Product Quantization）将 d 维向量切分成 m 个子空间，每个子空间 d/m 维。对每个子空间独立做 K-Means 聚类，得到一个码本（centroid table）。向量被编码为 m 个码本索引（每个 uint8），压缩比 d/4:1（假设 m = d/4，每个子空间 256 个 centroid）。查询时，先对查询向量做同样的切分，在码本中查找最近 centroid，通过预计算的距离表快速估计与所有库向量的距离。PQ 的压缩比远高于 SQ，但精度损失也更大，且搜索时需要额外的距离表计算开销。

工程实践中，如果内存足够用 FLAT 或 HNSW 不量化；如果内存紧张但需要高精度，用 IVF_PQ 或 HNSW + SQ；如果内存非常紧张且对精度不极度敏感，用 IVF_PQ。

索引选择

索引选择取决于三个核心约束：数据规模、可用内存和延迟要求。

数据量 < 50 万且内存充足，直接 FLAT 即可，无需索引构建开销。

50 万到 5000 万向量、内存充足，HNSW 是首选，精度和延迟的综合表现最好。

5000 万到数亿向量、内存有限，IVF_SQ8 或 IVF_PQ 更合适，通过量化压缩内存。超大规模（> 5 亿）且超出内存容量，DiskANN 是可行方案。

如果数据频繁变更需要实时更新，HNSW 的增量插入能力优于 IVF 的重建策略。