VecDB第十篇：除了HNSW，向量索引还有什么？——IVFFlat与PQ量化原理

VecDB第十篇：除了HNSW，向量索引还有什么？——IVFFlat与PQ量化原理

前言

前面第九篇文章，咱们聊了HNSW向量索引，用"六度人脉"的故事类比了分层图结构的原理——图结构跳转，快是快，但有一个致命问题：内存占用太高。

HNSW的内存占用通常是原始数据的1.5-2倍。8个向量看不出差距，但如果有1亿条768维的向量呢？那就是将近300GB的内存，普通服务器根本扛不住。

所以这一篇，咱们来看看向量索引的两大分支：

• IVFFlat：用"分桶"来减少搜索范围
• PQ量化：用"压缩"来减少内存占用

看完这两篇文章，你就知道什么时候该用HNSW，什么时候该用IVFFlat/PQ，再也不会纠结了。

术语说明：本文用"命中率"代替常见的"召回率"。

学术上叫 Recall，翻译成"召回率"，但这个词非常反直觉：

• 制造业：召回= 产品有缺陷，召回来 → 召回率高 = 烂货多（贬义）
• 搜索领域：Recall= recall information，把信息"回想/检索"出来 → 召回率高 = 找得全（褒义）

同一个词，两个行业意思完全相反，新手看了容易懵。根源是英文 Recall 本身有两个意思：一个是"召回缺陷产品"，一个是"回想起/检索出信息"。

所以本文统一叫命中率——10个该找的，命中了9个，命中率90%，直白好懂。你在其他资料看到"召回率"，就当它是"命中率"就行。

一、先说说暴力检索的问题

在讲IVFFlat之前，咱们先回顾一下暴力检索（Flat）是怎么工作的。

用咱们的小数据集举个例子：

文档0: [1, 2, 1, 0] 文档1: [0, 0, 1, 2] 文档2: [1, 0, 0, 2] 文档3: [0, 0, 2, 1] 文档4: [1, 1, 1, 1] 文档5: [0, 0, 0, 2] 文档6: [0, 1, 1, 0] 文档7: [1, 1, 0, 1]

现在查询"月球任务"，查询向量是[0, 1, 1, 0]。

暴力检索的做法很简单：一个一个算距离，挑最近的那个。

查询向量: [0, 1, 1, 0] → 文档0: √[(0-1)² + (1-2)² + (1-1)² + (0-0)²] = √4 = 1.41 → 文档1: √[(0-0)² + (1-0)² + (1-1)² + (0-2)²] = √5 = 2.24 → 文档2: √[(0-1)² + (1-0)² + (1-0)² + (0-2)²] = √7 = 2.65 → 文档3: √[(0-0)² + (1-0)² + (1-2)² + (0-1)²] = √6 = 2.45 → 文档4: √[(0-1)² + (1-1)² + (1-1)² + (0-1)²] = √2 = 1.41 → 文档5: √[(0-0)² + (1-0)² + (1-0)² + (0-2)²] = √6 = 2.45 → 文档6: √[(0-0)² + (1-1)² + (1-1)² + (0-0)²] = √1 = 1.00 ← 最近！ → 文档7: √[(0-1)² + (1-1)² + (1-0)² + (0-1)²] = √3 = 1.73 结论：文档6最近（距离1.00）

问题在哪？

8个文档还算轻松，但如果是100万个文档呢？那就要算100万次距离；如果是1亿个文档呢？那就要算1亿次。

暴力检索的复杂度：O(N) —— N是文档数量

时间复杂度随着数据量线性增长，数据越大越慢。

那有没有办法加速？

核心思路就一个：先粗筛，再精排。不用一个一个查，先把范围缩小，再在小的范围里精确查找。

二、IVFFlat：先分桶，再查找

2.1 名字解读

IVFFlat=IVF+Flat

整体含义：先把文档分成若干"桶"，查询时先找到相关的桶，再在桶里精确查找。

2.2 核心思想——图书馆分区

IVFFlat的核心思想，用图书馆来类比最合适：

想象你去图书馆找一本关于"月球任务"的书： 暴力搜索 = 一排一排书架走过去，一本一本翻 → 累死你！ IVFFlat = 1. 先看门口的分类指示牌 2. 找到"航天航空"区域 3. 在这个区域里找"月球"相关的书架 4. 终于找到了！ → 快多了！

IVFFlat就是这样工作的：

• 把所有文档分成若干"桶"（类比图书馆的分区）
• 每个桶有一个"中心点"（类比区域指示牌）
• 查询时，先算查询向量到各桶中心的距离，找到最近的几个桶
• 再在桶内进行精确搜索

2.3 构建过程——K-Means聚类

IVFFlat的构建，核心就是K-Means聚类。

咱们还是用那8个文档，一步一步演示：

文档0: [1, 2, 1, 0] 文档1: [0, 0, 1, 2] 文档2: [1, 0, 0, 2] 文档3: [0, 0, 2, 1] 文档4: [1, 1, 1, 1] 文档5: [0, 0, 0, 2] 文档6: [0, 1, 1, 0] 文档7: [1, 1, 0, 1]

参数 nlist = 2：表示分成2个桶。

步骤1：初始化中心点

咱们随机选两个文档作为初始中心：

初始中心0: 文档0 → [1, 2, 1, 0] 初始中心1: 文档3 → [0, 0, 2, 1]

步骤2：迭代分配（迭代1）

现在把每个文档分配到离它最近的中心：

文档0 → 中心0: 0.00, 中心1: 2.65 → 分配到桶0（更近） 文档1 → 中心0: 3.00, 中心1: 1.41 → 分配到桶1 文档2 → 中心0: 3.00, 中心1: 2.45 → 分配到桶1 文档3 → 中心0: 2.65, 中心1: 0.00 → 分配到桶1 文档4 → 中心0: 1.41, 中心1: 1.73 → 分配到桶0 文档5 → 中心0: 3.16, 中心1: 2.24 → 分配到桶1 文档6 → 中心0: 1.41, 中心1: 1.73 → 分配到桶0 文档7 → 中心0: 1.73, 中心1: 2.45 → 分配到桶0 当前分配结果： ├── 桶0: [文档0, 文档4, 文档6, 文档7] └── 桶1: [文档1, 文档2, 文档3, 文档5]

再更新中心点（桶内所有文档的平均值）：

新中心0 = 平均(文档0, 文档4, 文档6, 文档7) = 平均([1,2,1,0], [1,1,1,1], [0,1,1,0], [1,1,0,1]) = [0.75, 1.25, 0.75, 0.5] 新中心1 = 平均(文档1, 文档2, 文档3, 文档5) = 平均([0,0,1,2], [1,0,0,2], [0,0,2,1], [0,0,0,2]) = [0.25, 0.0, 0.75, 1.75]

步骤3：迭代分配（迭代2）

用新中心重新分配：

文档0 → 中心0: 0.97, 中心1: 2.77 → 分配到桶0 文档1 → 中心0: 2.11, 中心1: 0.43 → 分配到桶1 文档2 → 中心0: 2.11, 中心1: 1.09 → 分配到桶1 文档3 → 中心0: 1.98, 中心1: 1.48 → 分配到桶1 文档4 → 中心0: 0.66, 中心1: 1.48 → 分配到桶0 文档5 → 中心0: 2.22, 中心1: 0.83 → 分配到桶1 文档6 → 中心0: 0.97, 中心1: 2.05 → 分配到桶0 文档7 → 中心0: 0.97, 中心1: 1.64 → 分配到桶0 当前分配结果： ├── 桶0: [文档0, 文档4, 文档6, 文档7] └── 桶1: [文档1, 文档2, 文档3, 文档5]

这次分配和上次一样，中心点也不变，K-Means收敛了！

最终聚类结果

┌─────────────────────────────────────────────────────┐ │ 桶0 │ │ 中心: [0.75, 1.25, 0.75, 0.5] │ │ 文档: [文档0, 文档4, 文档6, 文档7] │ │ 内容: 登月任务、月球基地、飞行距离、阿尔忒弥斯 │ ├─────────────────────────────────────────────────────┤ │ 桶1 │ │ 中心: [0.25, 0.0, 0.75, 1.75] │ │ 文档: [文档1, 文档2, 文档3, 文档5] │ │ 内容: 火箭飞船、宇航员测试、系统验证、任务计划 │ └─────────────────────────────────────────────────────┘

从结果能看出什么？

桶0主要包含"月球"、“飞行"相关的内容；桶1主要包含"任务”、“系统”、"宇航员"相关的内容。相似的内容被聚到了一起！

2.4 查询过程——一步步手走

现在查询"月球任务"，查询向量是[0, 1, 1, 0]。

第一步：算查询向量到各桶中心的距离

查询向量: [0, 1, 1, 0] → 到桶0中心 [0.75, 1.25, 0.75, 0.5]: √[(0-0.75)² + (1-1.25)² + (1-0.75)² + (0-0.5)²] = √[0.5625 + 0.0625 + 0.0625 + 0.25] = √0.9375 ≈ 0.97 → 到桶1中心 [0.25, 0.0, 0.75, 1.75]: √[(0-0.25)² + (1-0)² + (1-0.75)² + (0-1.75)²] = √[0.0625 + 1 + 0.0625 + 3.0625] = √4.1875 ≈ 2.05

第二步：根据nprobe决定搜几个桶

参数 nprobe = 1：只搜最近的1个桶。

最近的桶：桶0（距离0.97 < 2.05） 搜桶0里的文档：[文档0, 文档4, 文档6, 文档7] 算精确距离： → 文档0: 1.41 → 文档4: 1.41 → 文档6: 1.00 ← 最近！ → 文档7: 1.73 Top-1结果：文档6（距离1.00）

如果 nprobe = 2（搜2个桶）：

搜桶0 + 桶1 的所有文档 算精确距离： → 文档6: 1.00 ← 最近！ → 文档0: 1.41 → 文档4: 1.41 → 文档7: 1.73 → 文档3: 1.73 → 文档1: 2.24 → 文档5: 2.45 → 文档2: 2.65 Top-3结果：文档6、文档0、文档4

对比暴力搜索：

暴力搜索Top-3：文档6(1.00)、文档0(1.41)、文档4(1.41) nprobe=1: 文档6(1.00)、文档0(1.41)、文档4(1.41) nprobe=2: 文档6(1.00)、文档0(1.41)、文档4(1.41) nprobe=1 就能找到正确答案！因为文档6、0、4刚好是最近的三个。

2.5 关键参数

参数选择建议：

nlist 越大： ├── 优点：每个桶更小，搜索更快 └── 缺点：建索引更慢，内存占用更高 nprobe 越大： ├── 优点：命中率更高（找到正确答案的概率更大） └── 缺点：搜索更慢（搜的桶更多）

类比理解：

nlist = 超市分区数 ├── 分10个区 → 每个区东西少，找得快 └── 分100个区 → 每个区东西更少，但要找很久才能决定去哪个区 nprobe = 你愿意逛几个分区 ├── 逛1个分区 → 可能错过最佳选择 └── 逛10个分区 → 更可能找到最好的，但更累

三、PQ量化：把向量压成密码本

3.1 为什么需要量化

刚才的IVFFlat解决了"搜索范围"的问题，但没有解决"内存占用"的问题。

咱们来算一笔账：

8条4维向量： ├── 原始存储：8 × 4 × 4字节 = 128字节 └── IVFFlat存储：8 × 4 × 4字节 + 2 × 4 × 4字节 = 160字节 （向量 + 中心点） 1亿条768维向量： ├── 原始存储：1亿 × 768 × 4字节 ≈ 288GB └── 根本塞不进内存！

问题核心：高维向量的存储空间太大了。

这时候就需要量化（Quantization）——把向量"压缩"存储，用"近似"代替"精确"。

3.2 PQ核心思想——邮编定位

PQ = Product Quantization（乘积量化）

核心思想用一个生活类比来解释：

你想告诉朋友你在哪个餐厅吃饭： ❌ 暴力做法：告诉他完整地址 "XX省XX市XX区XX路XX号XX大厦B1层XX餐厅" → 太长了！ ✓ PQ做法：告诉他邮编+门牌号 "邮编123456，门牌88" → 简洁多了！ 邮编123456对应的是一个区域（类似质心）， 门牌88对应的是这个区域里的具体位置（类似编码）。

PQ就是这样工作的：

1. 把向量切成几段 2. 每段单独做K-Means聚类，得到若干质心 3. 每个向量用"段1质心编号 + 段2质心编号 + ..."来表示 4. 存储时只存这些编号，不存完整向量

3.3 PQ过程演示

还是那8个4维向量，咱们一步步演示PQ量化：

文档0: [1, 2, 1, 0] 文档1: [0, 0, 1, 2] 文档2: [1, 0, 0, 2] 文档3: [0, 0, 2, 1] 文档4: [1, 1, 1, 1] 文档5: [0, 0, 0, 2] 文档6: [0, 1, 1, 0] 文档7: [1, 1, 0, 1]

参数：m = 2（切成2段），ks = 4（每段4个质心）

步骤1：切段

把4维向量切成2段，每段2维：

文档0: [1, 2, 1, 0] → 段1 [1, 2] + 段2 [1, 0] 文档1: [0, 0, 1, 2] → 段1 [0, 0] + 段2 [1, 2] 文档2: [1, 0, 0, 2] → 段1 [1, 0] + 段2 [0, 2] 文档3: [0, 0, 2, 1] → 段1 [0, 0] + 段2 [2, 1] 文档4: [1, 1, 1, 1] → 段1 [1, 1] + 段2 [1, 1] 文档5: [0, 0, 0, 2] → 段1 [0, 0] + 段2 [0, 2] 文档6: [0, 1, 1, 0] → 段1 [0, 1] + 段2 [1, 0] 文档7: [1, 1, 0, 1] → 段1 [1, 1] + 段2 [0, 1]

步骤2：每段做K-Means聚类

第1段聚类（所有向量前2维）：

段1的向量： [1,2], [0,0], [1,0], [0,0], [1,1], [0,0], [0,1], [1,1] K-Means聚类（4个质心）后： ┌─────────────────────────────────────────┐ │ 质心0: [1.0, 1.33] ← 包含文档0,4,7 │ │ 质心1: [0.0, 1.0] ← 包含文档6 │ │ 质心2: [1.0, 0.0] ← 包含文档2 │ │ 质心3: [0.0, 0.0] ← 包含文档1,3,5 │ └─────────────────────────────────────────┘

第2段聚类（所有向量后2维）：

段2的向量： [1,0], [1,2], [0,2], [2,1], [1,1], [0,2], [1,0], [0,1] K-Means聚类（4个质心）后： ┌─────────────────────────────────────────┐ │ 质心0: [1.0, 0.33] ← 包含文档0,4,6 │ │ 质心1: [1.0, 2.0] ← 包含文档1 │ │ 质心2: [0.0, 1.67] ← 包含文档2,5,7 │ │ 质心3: [2.0, 1.0] ← 包含文档3 │ └─────────────────────────────────────────┘

步骤3：编码

每个向量找到它每段最近的质心，用质心编号代替原始向量：

┌─────────┬─────────────┬─────────────┬────────────┬────────────┐ │ 文档 │ 段1向量 │ 段1质心 │ 段2向量 │ 段2质心 │ ├─────────┼─────────────┼─────────────┼─────────────┼────────────┤ │ 文档0 │ [1, 2] │ 质心0 │ [1, 0] │ 质心0 │ │ 文档1 │ [0, 0] │ 质心3 │ [1, 2] │ 质心1 │ │ 文档2 │ [1, 0] │ 质心2 │ [0, 2] │ 质心2 │ │ 文档3 │ [0, 0] │ 质心3 │ [2, 1] │ 质心3 │ │ 文档4 │ [1, 1] │ 质心0 │ [1, 1] │ 质心0 │ │ 文档5 │ [0, 0] │ 质心3 │ [0, 2] │ 质心2 │ │ 文档6 │ [0, 1] │ 质心1 │ [1, 0] │ 质心0 │ │ 文档7 │ [1, 1] │ 质心0 │ [0, 1] │ 质心2 │ └─────────┴─────────────┴─────────────┴─────────────┴────────────┘ 最终编码： 文档0 → [0, 0] 文档1 → [3, 1] 文档2 → [2, 2] 文档3 → [3, 3] 文档4 → [0, 0] 文档5 → [3, 2] 文档6 → [1, 0] 文档7 → [0, 2]

步骤4：存储对比

原始存储： 8个文档 × 4维 × 4字节 = 128字节 PQ压缩后： 8个文档 × 2段 × 1字节 = 16字节 + 质心表：2段 × 4个质心 × 2维 × 4字节 = 64字节 = 总共 80字节 压缩比：128 / 80 ≈ 1.6:1（在这个小例子中不太明显）

但在大数据中优势明显：

1亿条768维向量，PQ参数 m=8, ks=256： ├── 原始：1亿 × 768 × 4字节 = 288GB ├── 压缩：1亿 × 8 × 1字节 = 800MB ├── 质心表：8 × 256 × (768/8) × 4字节 = 512KB └── 压缩后总大小 ≈ 1.3GB 压缩比：288GB / 1.3GB ≈ 220:1！

步骤5：查询过程

查询向量[0, 1, 1, 0]，咱们来演示PQ怎么查询。

第一步：切段

查询向量: [0, 1, 1, 0] → 段1 [0, 1] + 段2 [1, 0]

第二步：预计算距离表

查询段1 [0, 1] 到各质心的距离： ├─ 质心0 [1.0, 1.33]: 1.05 ├─ 质心1 [0.0, 1.0]: 0.00 ← 最近！ ├─ 质心2 [1.0, 0.0]: 1.41 └─ 质心3 [0.0, 0.0]: 1.00 查询段2 [1, 0] 到各质心的距离： ├─ 质心0 [1.0, 0.33]: 0.33 ├─ 质心1 [1.0, 2.0]: 2.00 ├─ 质心2 [0.0, 1.67]: 1.94 └─ 质心3 [2.0, 1.0]: 1.41

第三步：查表估算距离

文档0 → [0, 0] → 1.05 + 0.33 = 1.39 文档1 → [3, 1] → 1.00 + 2.00 = 3.00 文档2 → [2, 2] → 1.41 + 1.94 = 3.36 文档3 → [3, 3] → 1.00 + 1.41 = 2.41 文档4 → [0, 0] → 1.05 + 0.33 = 1.39 文档5 → [3, 2] → 1.00 + 1.94 = 2.94 文档6 → [1, 0] → 0.00 + 0.33 = 0.33 ← 最小！ 文档7 → [0, 2] → 1.05 + 1.94 = 3.00

PQ估算Top-3：文档6(0.33)、文档0(1.39)、文档4(1.39)

对比真实距离：

文档6: 真实距离 = 1.00 文档0: 真实距离 = 1.41 文档4: 真实距离 = 1.41

真实Top-3：文档6、文档0、文档4

PQ排序: [6, 0, 4] 真实排序: [6, 0, 4] Top-3 完全一致！这就是PQ的魅力——用近似计算得到几乎相同的结果。

PQ的核心优势：

传统距离计算： 查询向量和每个文档向量都要算完整的欧氏距离 → 每次计算需要 d 次减法 + d 次乘法 + d-1 次加法 + 1 次开方 → 768维向量就要768×4=3072次运算 PQ查表： 查询向量和每个质心只算一次距离表（m × ks 次） → 查表求和只需要 m 次加法 → 8段 × 256质心 = 2048次运算（预计算） → 查询时每次只需要 8 次加法！

3.4 PQ参数选择

参数对命中率的影响： m 越大（分段越多）： ├── 优点：命中率越高（分段越细，精度越高） └── 缺点：查询越慢（要查更多表） ks 越大（质心越多）： ├── 优点：命中率越高（质心越细，区分度越高） └── 缺点：质心表越大（存储开销增加）

四、IVF_PQ：分桶+压缩，双管齐下

4.1 为什么需要组合

IVFFlat解决了搜索范围问题，但内存占用没减少。
PQ解决了内存占用问题，但搜索精度有损失。

有没有办法兼顾两者？

有！IVF_PQ=IVF分桶+PQ压缩。

IVF_PQ 工作流程： 1. 用IVF把文档分成若干桶（粗筛） 2. 用PQ把桶内的向量压缩存储（省内存） 3. 查询时： a. 先用IVF找到相关的桶 b. 再用PQ快速估算桶内向量和查询的距离 c. 返回Top-K

4.2 类比理解

IVF_PQ = 图书馆分区域 + 邮编定位 1. 先用IVF分区：找到"航天航空"区域 2. 再用PQ定位： - 不用一本一本翻书架 - 用邮编+门牌号快速定位 - 找到最接近的

4.3 实际应用中的IVF_PQ

主流向量数据库（Milvus、Qdrant等）都支持IVF_PQ：

# Milvus 创建IVF_PQ索引 index_params = { "index_type": "IVF_PQ", "metric_type": "L2", "params": { "nlist": 1024, # 1024个桶 "nprobe": 64, # 搜64个桶 "m": 16, # 16段 "nbits": 8 # 每质心8bit } }

典型配置：

五、三种索引横向对比

这是全文的高潮！咱们来对比一下HNSW、IVFFlat、IVF_PQ：

5.1 速度对比

查询速度（相对值，越小越快）： HNSW: ████ (log N = 几十次计算) IVFFlat: ██████████ (√N = 几百次计算) IVF_PQ: ████████ (√N/m，比IVFFlat快几倍) 说明：IVF_PQ虽然也要搜桶，但因为用了PQ，桶内计算极快。

5.2 内存对比

内存占用（原始数据的倍数）： HNSW: ████████████████████ (1.5-2倍) IVFFlat: ██████████████████ (1倍) IVF_PQ: ████ (1/32-1/64倍) 说明：IVF_PQ压缩32-64倍，所以内存占用极低。

5.3 命中率对比

命中率（找到正确答案的比例）： HNSW: ████████████████████ (95-99%) IVFFlat: ████████████████████ (95-99%) IVF_PQ: ██████████████████ (85-95%) 说明：IVF_PQ用近似计算，命中率略有下降，但通常可接受。

5.4 适用场景总结

┌─────────────────────────────────────────────────────────────┐ │ 选型指南 │ ├─────────────────────────────────────────────────────────────┤ │ │ │ 数据量 < 10万 │ │ └── Flat（暴力搜索就够了，没必要加索引） │ │ │ │ 数据量 10万 - 1000万 │ │ └── HNSW（默认选择，快且准） │ │ │ │ 数据量 1000万 - 1亿 │ │ ├── 内存够 → HNSW │ │ └── 内存不够 → IVFFlat │ │ │ │ 数据量 1亿 - 10亿 │ │ └── IVF_PQ（内存不够时的唯一选择） │ │ │ │ 数据量 > 10亿 │ │ └── DiskANN（磁盘存储+内存索引，特殊方案） │ │ │ └─────────────────────────────────────────────────────────────┘

六、实战选型建议

6.1 按场景选型

6.2 参数调优建议

HNSW调参：

{ "M": 16, # 邻居数，越大越准但越慢 "efConstruction": 200, # 建索引时的候选队列大小 "efSearch": 100 # 查询时的候选队列大小，越大越准 }

IVF_PQ调参：

{ "nlist": 1024, # 桶数，越大越细 "nprobe": 64, # 查询搜几个桶，越大召回越高 "m": 16, # 分段数，越大越准 "nbits": 8 # 每质心位数，越大越准 }

6.3 性能预估公式

HNSW 查询时间 ≈ O(log N / M) IVFFlat 查询时间 ≈ O(N/nlist × nprobe) IVF_PQ 查询时间 ≈ O(nprobe × m)

估算示例（1亿条768维向量）： HNSW: N = 1亿, M = 16 → log(1亿)/16 ≈ 26/16 ≈ 2次计算 → 极快，但内存占用 ~150GB IVF_PQ: nlist = 4096, nprobe = 128, m = 16 → 128 × 16 = 2048次计算 → 快，内存占用 ~3GB 结论：数据量大时，IVF_PQ是唯一可行的选择。

七、总结

这一篇咱们聊了两种重要的向量索引：

IVFFlat

核心思想：先分桶，再查找 优点：命中率高（95-99%），原理简单 缺点：内存占用仍然是原始数据的1倍 适用：千万级数据，内存充足

PQ量化

核心思想：把向量压成密码本 优点：压缩比高（32-64倍），内存占用极低 缺点：命中率略有下降（85-95%） 适用：亿级数据，内存紧张

IVF_PQ（组合）

核心思想：IVF分桶 + PQ压缩 优点：兼顾速度和内存 缺点：实现复杂，调参困难 适用：亿级数据，主流选择

一句话选型：

数据小（<100万）→ 别折腾了，暴力搜索最快 数据中（100万-1000万）→ 果断HNSW 数据大（1000万-1亿）→ 看内存够不够 数据超大（>1亿）→ IVF_PQ没得选