向量数据库常见的索引算法

首先做一个总结：

📊 常见向量索引算法与底层库对比表

类别	名称	核心原理	优势 (Pros)	劣势 (Cons)	适用场景
算法	IVF	聚类分区：利用 K-Means 将空间划分为小区，搜索时只扫描邻近区域。	内存占用低，索引速度快。	搜索精度受限于聚类边界。	中大规模数据的平衡选型。
算法	HNSW	分层图网络：构建多层“小世界”导航图，通过层级跳跃快速逼近目标。	性能巅峰，检索延迟极低，召回率极高。	内存消耗巨大，存储成本最高。	RAG 生产环境、高并发实时检索。
算法	PQ	乘积量化：将长向量切段并压缩为短编码，实现大幅度“瘦身”。	极度省空间（可压缩 10-100 倍），检索极快。	精度损失明显，存在语义漂移。	PB 级海量数据的低成本存储。
算法	ANNOY	随机森林/树：通过随机超平面不断二分空间，构建多棵索引树。	支持静态文件内存映射（mmap），适合只读。	不支持增量更新，必须重新构建索引。	静态推荐系统、离线搜索、移动端。
工具库	FAISS	高性能引擎：由 Meta 开发，集成了上述所有算法的底层优化库。	支持 GPU 加速，支持多种算法复合（如 IVF-PQ）。	仅为工具库，非分布式数据库，需二次开发。	向量数据库底层引擎、算法调优。

---

💡 快速选型指南：

1. 追求极致性能与准确率 🚀：首选 HNSW（目前 RAG 系统的主流）。

2. 数据量巨大但内存预算有限 💰：首选 IVF-PQ 组合。

3. 数据几乎不更新且需要低内存读写 🌲：考虑 ANNOY。

4. 需要进行亿级数据的大规模训练与加速 🛠️：直接使用 FAISS。

5. IVF（Inverted File Index）
   常见的数据库都支持 IVF 索引。
   1.1 IVF 索引的检索过程
   IVF 索引的检索过程可以分为以下几个步骤：

6. 计算查询向量与所有质心向量的距离，找到距离最近的 K 个质心向量。

7. 对于每个最近的质心向量，根据倒排列表找到所有属于该聚类的向量。

8. 对这些向量进行距离计算，返回距离最近的 N 个向量。
   1.2 IVF 索引的存储结构
   IVF 索引是一种基于倒排索引的数据结构，用于快速查找相似数据。主要有两部分组成，一个是质心表、一个是倒排列表。
   码表里边存储的是每个聚类的质心向量，同时还会存储这个质心对应的聚类 ID。
   质心表
   存储内容：每个聚类的质心向量，和这个聚类其他向量所在倒排列表的地址。
   存储顺序：根据 Kmeans 聚类的结果输出顺序
   倒排列表
   存储内容：质心向量所在聚类的其他向量的 ID 和向量的具体内容。
   存储顺序：倒排列表内的顺序经常是根据插入顺序排序的。倒排列表之间的顺序通常是按照质心表的顺序

2.HNSW (Hierarchical Navigable Small World)
2.1 HNSW 索引基础 NSW算法
简单的理解一下，NSW算法在建立过程中
首先我们将向量一个一个放入数据库中，第一个向量我们将它作为根节点，后续的向量放入的时候，我们去找它最近的k个向量，然后去链接它们。直到我们放完了所有的向量。
如果我们要查询一个向量，我们先在数据库里边随便找一个向量，然后计算它与查询向量的距离，找到距离最近的k个向量，然后我们再去查询这k个向量的邻居，直到我们找到那个她的领居都比他距离查询向量更远，那他就是最近的向量
2.2 HNSW 索引算法
HNSW索引算法是在NSW算法上加上分层的概念，最上边的层向量最少，最下边的层向量最多，query现在最上边的层去找，找到这一层中和query最接近的向量，然后以他为点，链接下一层，到下一层继续找。
2.3 HNSW 索引存储结构
存储过程：
查过程：

Step0: