向量索引在推薦系統、人臉識別、行人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。
