向量索引在推荐系统、人脸识别、行人reid的过程中，扮演着重要的作用。一般向量索引算法主要分为基于图的算法、基于聚类的算法、基于量化的方法几类，比如IVF_FLAT、HNSW、IVF_PQ等。
1. IVF_FLAT
算法流程说明：
- 高维空间中的点基于隐形的聚类属性，按照kmeans等聚类算法对向量进行聚类处理，使得每个类簇有一个中心点，聚类出 nlist 个单元。
- 检索向量时首先遍历计算所有类簇的中心点，找到与目标向量最近的 nprobe 个类簇中心。
- 遍历计算 nprobe 个类簇中心所在聚类中的所有元素，经过全局排序得到距离最近的 topk 个向量。
2. HNSW
算法流程说明：
- 构造多层图，每层图都是下层图的一个缩略，同时构成下层图的跳表，类似高速公路。
- 从顶层随机选中一个点开始查询。
- 第一次搜索其邻居点，把它们按距离目标的远近顺序存储在定长( ef )的动态列表中，以后每一次查找，依次取出动态列表中的点，搜索其 M 邻居点，再把这些新探索的邻居点插入动态列表，每次插入动态列表需要重新排序，保留前k个。如果列表有变化则继续查找，不断迭代直至达到稳态，然后以动态列表中的第一个点作为下一层的入口点，进入下一层。
- 循环执行第3步，直到进入最底层。
3. IVF_PQ
算法流程说明：
乘积量化阶段（索引构建）
- 在做PQ之前，首先需要指定一个参数M，这个M就是指定向量要被切分成多少段，所以M一定要能整除向量的维度，在上图中M=4，所以向量库的每一个向量就被切分成了4段。
- 然后把所有向量的第一段取出来做Clustering得到256个簇心，再把所有向量的第二段取出来做 Clustering 得到256个簇心，直至对所有向量的第N段做完Clustering, 从而最终得到了256*M个簇心。
- 做完Clustering就开始对所有向量做Assign操作。这里的Assign就是把原来的N维的向量映射到M个数字，以N=128，M=4为例，首先把向量切成四段，然后对于每一段向量，都可以找到对应的最近的簇心 ID，4段向量就对应了4个簇心 ID，一个128维的向量就变成了一个由4个ID组成的向量，这样就可以完成了Assign操作的过程。
搜索阶段
- 对于每一个查询向量，以相同的方法把 N 维分成 M 段 N/M 维向量，然后计算每一段向量与之前预训练好的簇心的距离，得到一个 M * 256的表，就可以开始计算查询向量与库里面的向量的距离.
- 而查询向量的M段子向量与各自的256个簇心距离已经预计算好了，所以在计算两个向量的时候只用查M次表，比如的库里的某个向量被量化成了[124, 56, 132, 222], 那么首先查表得到查询向量第一段子向量与其ID为124的簇心的距离，然后再查表得到查询向量第二段子向量与其ID为56的簇心的距离。最后就可以得到四个距离d1、d2、d3、d4，查询向量跟库里向量的距离d = d1+d2+d3+d4。
