向量数据库索引HNSW与IVFFlat原理及优化实战-开发者社区-阿里云

向量数据库主要用于支持高效的向量检索场景（以图搜图、以文搜图等），通过本次培训可以掌握向量数据库的核心理论以及两种向量索引技术的特点、场景与算法原理，并通过实战案例掌握向量数据库的应用与性能优化策略。
在现实世界中，绝大多数的数据都是以非结构化数据的形式存在的，如图片，音频，视频，文本等。为了能够处理这些非结构化数据，通常会使用人工智能技术提取这些非结构化数据的特征，并将其转化为特征向量，再对这些特征向量进行分析和检索以实现对非结构化数据的处理。因此，将能存储、分析和检索特征向量的数据库称之为向量数据库。
向量数据库使用向量索引技术来实现对特征向量的快速检索。向量索引通常属于近似最近邻搜索（Approximate Nearest Neighbors Search，ANNS）范畴。其核心思想是不是仅仅返回最精确的结果项，而是只搜索可能是近邻的数据项，以提高检索效率。通过在可接受范围内牺牲一定的精确度，实现了向量数据库与传统数据库的显著区别。
在 PostgreSQL 中，当使用基于索引的查询时，索引扫描的方向通常只能按照升序（ASC）进行。这是因为大多数索引类型（如 B-tree）默认支持升序排序，而降序（DESC）扫描通常需要反向遍历索引树，这在效率上不如升序扫描。
内积越大表示越相似，所以使用负的内积（negative inner product）作为索引查询的依据，更小的（更相似）排在前面。
嵌入（embedding）是指将高维数据映射为低维表示的过程。在机器学习和自然语言处理中，嵌入通常用于将离散的符号或对象表示为连续的向量空间中的点。
在自然语言处理中，词嵌入（word embedding）是一种常见的技术，它将单词映射到实数向量，以便计算机可以更好地理解和处理文本。通过词嵌入，单词之间的语义和语法关系可以在向量空间中得到反映，如Word2Vec。
Word2Vec：https://code.google.com/archive/p/word2vec/
召回率衡量的是模型识别出的真正例（True Positives, TP）占所有实际正例（Actual Positives, AP）的比例。换句话说，召回率反映了模型识别出所有相关项目的能力。
召回率不同，在图像检索中体现方式是返回的图像不一样：
完全按照相似度距离排序的暴力搜索。此方式需要比较每一个向量，因此它的搜索速度较慢，但是召回率可以达到百分之百。
通过使用索引的方式进行搜索，此方式搜索速度较快，但得到的结果是一个近似的结果。
在机器学习领域，语义检索，图像识别，推荐系统等方向常涉及到的一个问题是：给定一个向量X=[x1,x2,x3...xn]，需要从海量的向量库中找到最相似的前K个向量。通常这些向量的维度很高，对于在线服务，用传统的方法查找是非常耗时的，容易使得时延上成为瓶颈，因此业界通用的方式就是将最相似的查找转换成Ann问题。
这样查找返回的前K个向量并不一定是最相似的K个向量，衡量Ann算法好不好的一个依据是召回，每次Ann请求返回的K个结果与使用暴力查找的K个结果去比较，如果完全一致，说明是最好的。因为省了搜索时间却没有影响效果。
目前的Ann算法有基于图的，基于树的，基于哈希等，并且有很多关于Ann算法的实现。
HNSW 索引会创建多层图。它的查询性能比 IVFFlat 更好，但构建时间较慢且占用更多内存。此外，由于没有像 IVFFlat 那样的训练步骤，因此可以在没有任何数据的情况下创建索引。
max_parallel_maintenance_workers = 4
maintenance_work_mem = '7GB'
HNSW算法适合超大规模的向量数据集（千万级别以上），并且对查询延时有严格要求（10ms级别）的场景。
HNSW基于近邻图的算法，通过在近邻图快速迭代查找得到可能的相近点。在大数据量的情况下，使用HNSW算法的性能提升相比其他算法更加明显，但邻居点的存储会占用一部分存储空间，同时召回精度达到一定水平后难以通过简单的参数控制来提升。
同质性:同质性也就是相似的点会聚集到一起，相互连接具有邻接边。
弱连接:弱连接是指从每一个节点上，会有一些随机的边随机连接到网络中的节点上，这些节点是随机均匀的。
在NSW算法中通过构建一个小世界网络，希望通过黑色相似的近邻边来检索最近邻节点， 通过红色长边(高速公路)来实现不同类节点之间的快速检索
NSW的局部节点之间的在距离上具有同质性(也就是近邻节点能够相互连接)。从而使得当我们检索到一个近邻节点时，其大部分近邻节点都是近邻节点。同时也希望保留一些随机边，能够在不同区域之间快速跳转
执行m次贪婪搜索，在每次搜索过程中随机选择一个进入点遍历，最后从m次搜索选出距离查询点最近的k个结果。
通过逐个插入元素方式进行构图，对于每个待插入元素，通过近似kNN算法查找与其最近的f个元素，然后与其相连。
继承NSW基于long link快速检索，short link具有聚类特性的思想。怎么样能够使得查找更为稳定， 或者怎么样能够把long link的查找和short link查找有效区分。在此基础上引入了分层图的思想。
将节点划分成不同层级，贪婪地遍历来自上层的元素，直到达到局部最小值，然后切换到下一层，以上一层中的局部最小值作为新元素重新开始遍历，直到遍历完最低一层。
上图为HNSW算法的建图流程，其中红色节点代表待插节点，绿色表示已插入节点。
（1）输入建立索引所需的参数，设M=2，即每个元素最大连接2个结点；
（2）获取用于建图的所有图片，并依次传入算法中建立索引；
（4）将特征当作节点，并获取节点的层次l（随机分配）；
（5）插入节点，对于第一个插入的节点，不做任何操作
① 在L层找到距离待插节点最近的节点ep，并作为下一层的输入；
② 该层及以下为待插元素的插入层，从ep开始查找距离待插元素最近的ef个节点，从ef节点中选出M个与待插节点连接，并将这M个节点作为下一层的输入；
③从M个节点开始搜索，找到距离与待插节点最近的ef个节点，并选出M个与待插元素连接；
① 在L层找到距离待插节点最近的节点ep，并作为下一层的输入；
② 在l=2层找到距离待插节点最近的节点ep，并作为下一层的输入；
③ 该层及以下为待插元素的插入层，从ep开始查找距离待插元素最近的ef个节点，从ef节点中选出M个与待插节点连接，并将这M个节点作为下一层的输入；
其中红色的节点表示搜索节点q(可以是非图中的节点)，绿色节点表示图中已建立的节点，黄色的节点表示搜索结果。