向量数据库的索引到底是怎么设计的？B-tree 不管用了

网上讲 B-tree、LSM-tree 的文章遍地都是，但讲向量数据库索引原理的深度文章极少。这篇文章把 IVF、HNSW、PQ 和 IVFPQ 四个核心算法拆开讲清楚。

网上写数据库索引原理的文章，十个里有八个在讲 B-tree。

这很正常。B-tree 是数据库的脊梁，从 MySQL 到 PostgreSQL 到 SQLite，底层都靠它在撑。它的核心思路也简单：把数据按大小排好序，建一棵平衡树，查询时沿着树往下走，每次排除一半的分支。有序、有界、可预测。

但如果你把 B-tree 的思路直接搬到向量检索上，立刻就会碰壁。

向量没有大小之分。你能说向量 [0.1, 0.3, 0.8] 比 [0.9, 0.2, 0.1] 更大或更小吗？不能。向量之间只有距离关系，没有全序关系。B-tree 要求的"可比较大小"这个前提，在向量世界里根本不存在。

那向量数据库的索引是怎么设计的？

整个向量索引领域围绕一个核心矛盾展开：精确检索太慢，近似检索才有出路。

对 n 个 d 维向量做暴力搜索，每次查询要算 n 次距离。n 到百万级别，单次查询就是毫秒级；n 到十亿级别，单次查询就是秒级甚至不可接受。所以所有向量索引本质上都在做同一件事：用精度换速度。

这也是为什么这个领域叫 Approximate Nearest Neighbor Search（ANN）——近似最近邻搜索。

目前主流的索引方案可以归为三个流派：聚类派、图派、压缩派。实际产品里，这三个流派经常混着用。

聚类派：IVF（倒排文件）

IVF 是 Inverted File Index 的缩写，思路直接到有点粗暴。

建索引的时候，先对整个向量集做一次 k-means 聚类，聚出 K 个中心点。然后每个向量被分配到离它最近的那个簇。建完以后，你得到的是一个倒排列表：每个簇下面挂了一堆向量 ID。

查询的时候，先把查询向量跟 K 个簇中心算一遍距离，挑出最近的 N 个簇（nprobe 参数控制）。然后只在这 N 个簇内部暴力搜索。

算一笔账：100 万个 768 维向量，聚成 4096 个簇。查询时 nprobe 设为 10，那么搜索范围就从 100 万缩小到了大概 2500 个向量。速度提升 400 倍。

代价是什么？如果查询向量的真实最近邻恰好落在没被选中的簇里，就找不到了。这就是 ANN 的"近似"所在——它是一个不保证召回率的概率性方案。

IVF 的可爱之处在于它是一个极其直观的 tradeoff 旋钮。当你把 nprobe 调大，搜索范围扩大，召回率上升，速度下降。反之亦然。没有黑魔法。

IVF 的局限也很明显：它的性能天花板受限于聚类质量。如果数据分布不均匀，有些簇特别大，有些特别小，搜索效率就会波动。而且 k-means 本身对初始中心点敏感，每次建索引的结果可能不一样。

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

如果说 IVF 是向量索引里的"粗放派"，HNSW 就是"精细派"。

HNSW 的全称是 Hierarchical Navigable Small World，由 Yury Malkov 在 2016 年提出。它至今仍然是召回率和速度综合表现最好的 ANN 算法之一。

HNSW 的核心结构是一组层层堆叠的图。

最底层（Layer 0）包含所有向量节点，每个节点通过边连接到它最相似的 M 个邻居。往上的每一层逐级稀疏，Layer 1 只包含 Layer 0 的一个随机子集，Layer 2 又是 Layer 1 的子集，以此类推。最高层可能只有个位数的节点。

这个结构的设计灵感来自跳表。

HNSW 的搜索过程可以这样理解：先在高速路上狂飙，确认区域后下匝道走小路，最后在小巷里精确定位。

具体来说：搜索从最高层开始，在当前层沿着边做贪婪遍历——每一步都跳到跟查询向量距离最近的邻居节点，直到找不到更近的节点为止。然后下降到下一层，用上一层的终点作为起点继续遍历。重复直到抵达最底层。

每一层都在做"找到比当前节点更近的邻居"这个简单操作，但因为高层只有稀疏的长程边，一次跳跃可以跨越大片空间；低层有密集的短程边，可以精细定位。

HNSW 的参数有三个：M 控制每个节点最多连几条边；efConstruction 控制建索引时的搜索宽度（越大索引质量越高，建索引越慢）；efSearch 控制查询时的搜索宽度（越大召回率越高，查询越慢）。

优点很突出：召回率极高，在适当参数下可以接近 100%，而且搜索速度极快。缺点也很明确：内存开销大。每个节点都要存储它的邻居列表，对于十亿级别的数据量，纯 HNSW 的内存消耗是惊人的。

压缩派：PQ（乘积量化）

IVF 解决的是"少算一点"的问题，HNSW 解决的是"找得更快"的问题，PQ 解决的则是另一个维度的问题：让向量变得更小。

PQ 的核心思路是把一个高维向量拆成 M 段子向量，对每段子向量分别做量化。

一个 768 维的向量，拆成 8 段，每段 96 维。对每段 96 维的子向量，单独做 k-means 聚类（聚类中心数通常是 256，刚好一个字节能表示）。那么每个子向量就可以被表示成它所属簇的 ID（0-255）。8 段各需要一个字节，整个向量就从 768 * 4 = 3072 字节（float32）压缩到了 8 个字节。

压缩比接近 400 倍。

PQ 查询时有个精妙的设计叫 ADC（Asymmetric Distance Computation）。建索引时向量被压缩了，但查询向量保持原始精度。查询时不是把查询向量也压缩了再比，而是先计算查询向量到每个子码本中心的距离，做成 M 张查找表。然后每个被压缩的向量只需要查 M 次表、加 M 次结果，就能得到一个近似距离。

你保留了查询向量的全精度信息，同时用查表代替了实时计算。这是 PQ 能做到大压缩比同时保持不错召回率的核心原因。

缺点也很明显：PQ 压缩是有损的，压缩比越大召回率越低。而且在压缩域上做搜索，如果没有配合其他索引结构，仍然是 O(n) 扫描——只不过每次计算的成本从浮点运算变成了查表。

IVFPQ 和其他混合方案

单独用 IVF 或 PQ 都有各自的短板。IVF 搜索范围小但每个簇内还是暴力扫描；PQ 压缩率高但没有剪枝能力。

于是 IVFPQ 诞生了。

先建 IVF 倒排索引做粗粒度筛选，把向量分配到最近的簇。在每个簇内部，向量以 PQ 编码形式存储。查询时先找到最近的几个簇，然后在簇内用 ADC 方式做距离计算。

IVF 负责砍搜索空间，PQ 负责压缩内存。两者互补，这也是目前工业界最常用的组合方案。

在此基础上还有迭代版本：IVFPQFS（IVFPQ with Fast Scan），利用 SIMD 指令并行做 PQ 距离计算；IVFPQR（IVFPQ with Re-ranking），在 PQ 粗筛后对 Top-K 结果用原始向量重新排序，用额外计算换回精度。

Faiss 官方有一个很有参考价值的推荐排序：Flat 暴力搜 > IVF > IVFPQ > HNSW > IVFPQ with re-ranking。内存够用追求最高召回，选 HNSW。数据量大、内存紧张，选 IVFPQ 系列。

向量索引没有银弹

回到开头的对比。

B-tree 依赖数据有序性来剪枝，能保证每次查询的时间复杂度。向量索引没有这个前提，所以走的是另一条路：构建一种能在近似空间里快速导航的数据结构。

聚类派（IVF）通过 k-means 粗分空间来缩小搜索范围。图派（HNSW）通过多层可导航图来自适应地定位最近邻。压缩派（PQ）通过向量拆分量化来降低内存和计算成本。

没有哪个方案在所有维度上胜出。选 IVF 还是 HNSW，取决于你的数据量、内存预算、延迟要求和召回率底线。选不选 PQ，取决于你的向量维度和内存成本。

向量数据库的索引设计本质上是一个工程选择，拍板靠的是对数据规模和精度需求的精确估算。

没有银弹，但有工具箱。