IVFFlat 与 HNSW 算法介绍与对比
一 核心概念与适用场景
- IVFFlat（Inverted File with Flat）
- 基于K‑means 聚类将向量空间划分为多个簇（列表/桶），为每个簇维护倒排列表；查询时先找最近的若干簇，再在簇内做暴力精确距离计算（Flat 表示不压缩）。适合对召回精度较高、内存较充足、数据相对静态的场景。其优点是索引结构简单、可解释，缺点是需要训练、对数据分布变化敏感、频繁更新后可能需要重建索引。典型应用包括高精图像对比、需要可控召回的业务。
- HNSW（Hierarchical Navigable Small World）
- 基于多层小世界图的近似最近邻搜索：顶层稀疏用于快速导航，底层稠密用于精检；查询从顶层入口点逐层下降，在底层通过贪婪/受限搜索找 Top‑K。优点是高召回、低延迟、对高维向量和大规模数据更稳健；缺点是构建更慢、内存占用更高（需存储图连接）。常用于RAG、语义搜索、推荐系统等对召回与时延都敏感的场景。
二 算法原理
- IVFFlat
- 训练阶段：对全量或采样数据做K‑means，得到nlist 个质心；构建倒排列表将向量按最近质心分组。
- 查询阶段：计算查询与所有质心的距离，选择最近的nprobe 个簇，在这些簇的倒排列表内做精确距离计算并归并取 Top‑K。
- 关键理解：通过“粗筛（质心）+ 精检（桶内暴力）”减少计算；若查询靠近簇边界，需增大nprobe提升召回。
- HNSW
- 构图阶段：为每个向量随机确定最大层 l，自顶向下逐层插入；每层以ef_construction为宽度做近邻搜索，与M个最近且多样化的邻居建立双向连接，形成小世界图。
- 查询阶段：从顶层入口点开始，逐层下降，在底层以ef_search为宽度做受限搜索，维护候选动态列表，最终返回Top‑K。
- 关键理解：多层结构提供“高速公路”式导航，底层精细搜索保证高召回；M与ef_construction控制图质量与构建成本，ef_search控制查询质量与延迟。
三 关键参数与调优要点
- IVFFlat 常用参数
- lists（nlist）：聚类中心数。经验值：数据量< 100万时取rows/1000，> 100万时取sqrt(rows)；lists 越大，簇越小，查询更快但训练更慢、召回可能下降。
- probes（nprobe）：查询时探测的簇数。经验值：从lists 的 1%–10%起步，或取sqrt(lists)；probes 越大，召回越高、延迟越大。
- HNSW 常用参数
- M：每层节点的最大连接数。增大 M 提升连通性与召回，但增加内存与构建/查询延迟；常见取值16–64。
- ef_construction：构建时的候选队列宽度。增大可显著提升图质量与召回，但构建更慢；常见取值100–500。
- ef_search：查询时的候选队列宽度。增大可提升召回与稳定性，但查询更慢；通常设为≥ K，常见取值50–200。
四 多维对比
维度 | IVFFlat | HNSW |
|---|---|---|
索引结构 | 聚类分桶 + 倒排列表 + 桶内暴力 | 多层小世界图 |
是否需训练 | 是（K‑means） | 否 |
建索引速度 | 较快（依赖聚类） | 较慢（逐点构图） |
查询复杂度 | 近似 O(sqrt(N))，随 nprobe 增大趋近线性 | 近似 O(log N)，随 ef_search 增大趋近线性 |
召回与延迟 | 召回由 nprobe 控制；中等召回、中等延迟 | 召回由 ef_search/M 控制；高召回、低延迟 |
内存占用 | 较低（存原始向量 + 质心） | 较高（存原始向量 + 图连接） |
更新与维护 | 数据分布变化后需重建或重训 | 动态插入更友好，长期无需重建 |
典型场景 | 资源受限、批量/静态数据、可控召回 | 高召回/低延迟、高维/大规模、在线检索 |
参数敏感度 | 中等（lists/probes 直观可调） | 较高（M/efC/efS 需权衡） |
距离度量 | L2、内积、余弦（余弦常配合归一化） | L2、内积、余弦（依实现配置） |
SQL/配置示例 | CREATE INDEX … USING ivfflat (vec vector_l2_ops) WITH (lists=100); — 查询可设 SET ivfflat.probes=10; | CREATE INDEX … USING hnsw (vec vector_l2_ops) WITH (m=16, ef_construction=64); — 查询可设 SET hnsw.ef_search=100; |
五 实践建议与常见误区
- 何时优先 IVFFlat
- 内存预算有限、批量导入后建索引、对中等召回（如 90–95%）可接受、或需要可解释的参数（lists/probes）以快速达成目标性能。
- 何时优先 HNSW
- 高召回（>98%）与低时延（如 <10–20ms）同时要求、数据规模大/高维、在线写入与更新频繁、或希望减少维护成本（无需频繁重建）。
- 参数起步与迭代
- IVFFlat：先定lists ≈ rows/1000（<1M）或 sqrt(rows)(>1M)，再按目标延迟逐步增大probes（如 1%→10%→…）。
- HNSW：先定M=16/32、efC=100–200、efS≈K（或略大），在保证时延的前提下逐步上调efS/M提升召回。
- 距离度量与归一化
- 使用内积/余弦时，务必对向量归一化；此时内积序与余弦/欧氏序相反，排序方向需注意。
- 维护与重建
- IVFFlat在数据分布漂移或大量更新后召回下降，需定期重建；HNSW虽支持在线插入，但长期大规模更新也可能因图结构老化而需重建或重训。
- 多索引与混合检索
- 可为不同精度/时延目标共存多个索引（如 HNSW 高召回、IVFFlat 低成本），按查询场景选择；也可结合全文检索做混合检索以进一步提升效果。
