faiss索引调研（四）—— faiss源码分析
https://zhuanlan.zhihu.com/c_159623040
1. faiss最大堆实现
和普通最大堆没什么区别。
pop：堆顶元素出列（放到最后一个位置，最后一个位置后面会置为无效），然后循环把子节点往上提（提上来大的那个子节点（左vs右））。
push：先放到最后一个位置，然后循环往上找到应该插入的位置，每次往上一步就把被对比的堆里面的原元素往下踢一个位。
2. faiss暴力搜索（找当前元素的最相近的k个元素）
循环遍历数组，建立最大堆。
亮点是计算距离的时候使用的是分段计算，把一个d维向量分开每一段计算距离。
3. faiss聚类
- 先随机初始化k个聚类中心；
- 用暴搜（用上面的方法）找出数组中每个向量所属的聚类中心。把聚类中心的向量求和并求均值作为新的聚类中心，对于空元素的聚类中心，找到另一个分裂中心拿来分裂；
- 循环步骤2知道达到迭代次数。
4. faiss倒排
索引 : 先聚类，然后遍历每个向量找到最近的1个聚类中心，把聚类中心的id和向量放到list中作为倒排表（ids和codes）。
搜索 :
- 粗查询：返回最近的nprobe个聚类中心以及对应的距离；
- 查询倒排表：对于当前查询向量的每个聚类中心：拉取聚类中心的倒排list，遍历list中的每个向量，和查询向量一一计算距离，将结果放入返回的最大堆