向量数据库索引算法三剑客HNSW、LSH、PQ 原理深度解读1. 开篇从“大海捞针”到“精准导航”的密钥2. 一张图看懂三大算法的定位与协作多色流程图3. HNSW图结构的“高速路网”3.1 设计动机让贪心搜索找到“捷径”3.2 核心原理像查地图一样找向量3.3 关键参数与权衡3.4 优缺点与适用场景4. LSH哈希分桶的“智能分类”4.1 设计动机用哈希把“相似的”聚到一起4.2 核心原理随机超平面的“切分游戏”4.3 优缺点与适用场景5. PQ向量压缩的“极致瘦身”5.1 设计动机让万亿向量也能装进内存5.2 核心原理拆碎了分别“编字典”5.3 距离计算如何加速——查表法5.4 PQ的局限性6. 三类算法横向对比与协同使用7. 选型速查场景决定算法8. 总结三句话记住三大算法The Begin点点关注收藏不迷路⬇ ⬇ 底部 ⬇ ⬇1. 开篇从“大海捞针”到“精准导航”的密钥在向量数据库的世界里索引算法决定了一切。没有索引每一条查询都要和库里的每一个向量做距离计算——1亿条数据就是1亿次浮点运算再强的服务器也扛不住几秒一次的响应延迟。正是HNSW、LSH、PQ这三类算法让向量检索从“大海捞针”变成了“精准导航”。但很多开发者对这三个缩写的理解停留在“知道名字不清楚原理”的层面——HNSW为什么快LSH的哈希和传统哈希有什么不同PQ到底是怎么把向量“压缩”到那么小的本文将从设计动机、核心原理、关键参数、适用场景四个维度把这三类算法彻底讲透。全文配有多色流程图核心要点采用三色标注即使没有深厚的数学背景也能看懂它们的“灵魂”。2. 一张图看懂三大算法的定位与协作多色流程图下图展示了HNSW、LSH、PQ在向量检索中的角色分工。其中蓝色代表索引构建主流程金色代表三类算法的核心机制红色代表需要注意的权衡点。三大算法的核心定位HNSW擅长图导航快速定位PQ擅长极致压缩节省内存LSH擅长哈希分桶快速过滤。三者常被组合使用如IVFPQ、HNSWPQ各取所长。3. HNSW图结构的“高速路网”3.1 设计动机让贪心搜索找到“捷径”HNSW的全称是Hierarchical Navigable Small World分层可导航小世界网络。它的设计灵感来自两个经典思想跳表Skip List一种概率数据结构通过多层链表让查找从O(N)降到O(log N)可导航小世界图NSW一种基于图的近似最近邻算法通过节点间的连接实现“六度分隔”式搜索HNSW把这两个思想融合在一起——用多层图结构让搜索从顶层快速“跳”到目标区域再在底层精细定位。3.2 核心原理像查地图一样找向量HNSW构建的图结构可以想象成不同缩放级别的地图底层Level 0包含所有数据点节点密集连接精细用于最终精确定位上层Level 1, 2, …只包含部分数据点逐层稀疏节点之间的连接距离更长用于快速“跳跃”搜索过程分为三步顶层跳转从最高层的入口节点开始贪心搜索该层中与查询向量最接近的节点层层下降将上一层的搜索结果作为下一层的入口重复贪心搜索逐层逼近目标区域底层精搜在最底层进行局部精细搜索返回最相似的K个结果整个过程就像开车找路——先上高速顶层快速到达城市附近再下到普通道路底层精确找到目的地。3.3 关键参数与权衡HNSW有三个核心参数直接影响速度、精度和内存的平衡参数作用调大效果调小效果M每个节点的最大连接数召回率↑精度↑但内存↑构建↓内存↓速度↑但召回率↓efConstruction构建时的候选队列长度索引质量↑但构建时间↑构建速度↑但索引质量↓efSearch搜索时的候选队列长度召回率↑但查询延迟↑查询速度↑但召回率↓【实战经验】Milvus官方建议M在[5, 100]范围内调优efConstruction在[50, 500]范围内efSearch在[K, 10K]范围内K为返回结果数。3.4 优缺点与适用场景优点缺点适用场景查询复杂度O(log N)亿级数据毫秒响应内存占用高全量数据需加载到RAM实时推荐系统、高吞吐在线服务召回率极高接近暴力搜索构建时间较长对精度要求高的语义检索支持动态插入无需重建索引删除操作支持不完善数据频繁更新的场景4. LSH哈希分桶的“智能分类”4.1 设计动机用哈希把“相似的”聚到一起LSH的全称是Locality-Sensitive Hashing局部敏感哈希。传统哈希的目标是“不同的输入尽量映射到不同位置”而LSH恰恰相反——让相似的输入以高概率映射到同一个“桶”Bucket里。它的核心思想可以概括为“相似的在一起不相似的各走各的路”。查询时只需在查询向量命中的桶里搜索跳过其他所有桶大幅减少计算量。4.2 核心原理随机超平面的“切分游戏”LSH最常见的实现方式是基于随机投影Random Projection生成随机超平面在向量空间中生成K个随机超平面随机向量计算哈希码对于每个向量计算它与每个超平面的位置关系在正侧为1负侧为0得到一个K位的二进制哈希码分桶存储相同哈希码的向量落入同一个哈希桶当两个向量在空间中距离较近时它们被这些超平面“切”到同一侧的概率更高因此哈希码相同的概率也更高。为了提高召回率LSH通常会构建L张独立的哈希表每张表使用不同的随机超平面组。查询时在所有L张表中命中同一个桶的候选集合并去重再进行精细距离计算。4.3 优缺点与适用场景优点缺点适用场景查询复杂度接近O(1)极快需多张表L和长哈希码K保证精度内存占用高对延迟极度敏感的场景如实时推荐支持动态插入更新高效精度相对HNSW较低动态数据集实现简单理论成熟参数调优需要经验高维数据的快速初筛5. PQ向量压缩的“极致瘦身”5.1 设计动机让万亿向量也能装进内存PQ的全称是Product Quantization乘积量化。它解决的不是“检索速度”而是**“内存容量”**问题——HNSW再快如果向量太大装不进内存也跑不起来。一个768维的float向量占768×43072字节。1亿条这样的向量需要约300GB内存。PQ的目标就是把这个数字压缩几十甚至几百倍。5.2 核心原理拆碎了分别“编字典”PQ的压缩过程分为三步第一步拆分子向量将一个高维向量切成m个等长的子向量。例如768维切成m8段每段96维。第二步对每段独立聚类对每一段子向量用K-Means聚类生成k个“中心点”即码本/Codebook。通常k256即8位索引。这就像为每一段编一本“字典”256个词条代表这段空间中最典型的模式。第三步用索引替代浮点数对于原始向量的每一段找到该段在码本中最近的中心点只存储这个中心点的索引编号8位。最终原始的768个浮点数被压缩为8个索引号8×864位。压缩效果示例128维向量float32占4096位PQ压缩后m64, nbits8仅占512位压缩8倍。高维场景下压缩比可达256:1。5.3 距离计算如何加速——查表法PQ的妙处不止在压缩还在于距离计算的加速。查询时把查询向量也切成m段对每一段提前计算查询子向量与该段码本中所有256个中心点的距离生成一张“距离查找表”对于库中的任意向量只需查表、累加m个距离值即可得到近似距离——避免了解压缩和浮点乘法的开销5.4 PQ的局限性精度损失量化本质是有损压缩相似的向量可能因量化误差而被判为不相似训练成本需要提前在数据上训练K-Means码本数据量大时训练时间较长通常不单独使用PQ一般和IVF配合即IVF_PQ先用IVF筛选候选簇再在候选簇内用PQ做距离近似6. 三类算法横向对比与协同使用对比维度HNSWLSHPQ核心策略图结构导航哈希分桶过滤向量量化压缩解决什么问题如何快速找到最近邻如何快速跳过无关数据如何节省内存时间复杂度O(log N)O(1)查桶O(N)需配合IVF内存占用高中-高极低召回率极高中-高中需配合精排动态更新支持支持需重训练码本典型组合HNSWLSH 多表IVF PQIVF_PQ【协同使用】在实际生产中三类算法不互斥。例如HNSW PQ用PQ压缩向量后再建HNSW图既节省内存又保持高速IVF PQ最经典的组合IVF负责粗筛、PQ负责压缩被Milvus等数据库广泛采用7. 选型速查场景决定算法场景特征推荐算法理由数据量10万暴力搜索FLAT精度100%不需要近似数据量1亿追求高召回HNSW精度最高但内存消耗大数据量1亿内存受限IVF_PQ压缩比极高可支撑十亿级实时推荐延迟10msHNSW 或 LSH两者都支持极速查询动态写入频繁LSH 或 HNSW两者都支持增量插入8. 总结三句话记住三大算法HNSW建一张多层“高速路网”顶层跳远路、底层走细路用对数时间找到最近邻。LSH用随机超平面把向量“切”成哈希码相似的切到同一桶查询只翻桶、不翻全库。PQ把向量切成段、每段编字典用“字典索引号”替代“浮点数”压缩几十倍内存压力骤降。理解了这三句话你就掌握了向量数据库索引算法的核心精髓。实际应用中三者常组合使用——HNSW管“找路”PQ管“瘦身”LSH管“快速初筛”——共同构建起支撑亿级向量毫秒检索的技术底座。The End点点关注收藏不迷路⬆ ⬆ 顶部 ⬆ ⬆