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 名字解读IVFFlatIVFFlat字母含义解释IVFInverted File倒排文件类比图书馆的分类索引FlatFlat不压缩原样存储整体含义先把文档分成若干桶查询时先找到相关的桶再在桶里精确查找。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) nprobe1: 文档6(1.00)、文档0(1.41)、文档4(1.41) nprobe2: 文档6(1.00)、文档0(1.41)、文档4(1.41) nprobe1 就能找到正确答案因为文档6、0、4刚好是最近的三个。2.5 关键参数参数含义类比nlist桶的数量图书馆分多少个区域nprobe查询时搜几个桶你愿意逛几个区域找书参数选择建议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参数 m8, ks256 ├── 原始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.00PQ估算Top-3文档6(0.33)、文档0(1.39)、文档4(1.39)对比真实距离文档6: 真实距离 1.00 文档0: 真实距离 1.41 文档4: 真实距离 1.41真实Top-3文档6、文档0、文档4PQ排序: [6, 0, 4] 真实排序: [6, 0, 4] Top-3 完全一致这就是PQ的魅力——用近似计算得到几乎相同的结果。PQ的核心优势传统距离计算 查询向量和每个文档向量都要算完整的欧氏距离 → 每次计算需要 d 次减法 d 次乘法 d-1 次加法 1 次开方 → 768维向量就要768×43072次运算 PQ查表 查询向量和每个质心只算一次距离表m × ks 次 → 查表求和只需要 m 次加法 → 8段 × 256质心 2048次运算预计算 → 查询时每次只需要 8 次加法3.4 PQ参数选择参数含义建议值m分成几段4-16768维通常用8或16ks每段几个质心2568bit或102410bitds每段维度d/m768维/m段时每段96维或64维参数对命中率的影响 m 越大分段越多 ├── 优点命中率越高分段越细精度越高 └── 缺点查询越慢要查更多表 ks 越大质心越多 ├── 优点命中率越高质心越细区分度越高 └── 缺点质心表越大存储开销增加四、IVF_PQ分桶压缩双管齐下4.1 为什么需要组合IVFFlat解决了搜索范围问题但内存占用没减少。PQ解决了内存占用问题但搜索精度有损失。有没有办法兼顾两者有IVF_PQIVF分桶PQ压缩。IVF_PQ 工作流程 1. 用IVF把文档分成若干桶粗筛 2. 用PQ把桶内的向量压缩存储省内存 3. 查询时 a. 先用IVF找到相关的桶 b. 再用PQ快速估算桶内向量和查询的距离 c. 返回Top-K4.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 } }典型配置数据量nlistnprobem内存占用100万256328~2GB1000万1024648~15GB1亿409612816~100GB五、三种索引横向对比这是全文的高潮咱们来对比一下HNSW、IVFFlat、IVF_PQ对比维度HNSWIVFFlatIVF_PQ原理分层图结构聚类分桶聚类分桶量化压缩查询速度极快 (log N)中等 (√N)快 (√N/m)命中率95-99%95-99%85-95%内存占用高 (1.5-2倍)高 (1倍)极低 (1/32-1/64)构建速度慢快中等动态更新优秀差差适用数据量百万-十亿十万-千万亿级-百亿典型场景实时查询中等规模超大规模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 按场景选型场景推荐索引原因RAG对话系统HNSW需要实时响应命中率要高推荐系统HNSW高并发低延迟用户等不及离线数据分析IVF_PQ内存优先可以牺牲一点速度合规审计Flat必须100%命中率不能有任何遗漏图片搜索IVF_PQ亿级图库内存扛不住语音检索IVFFlat百万级中等规模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没得选