一、技术背景

过去几个月的时间，我们正处于人工智能的革命中，其中最耀眼的莫过于 GPT-3.5/4 的横空出世，而 GPT-3.5/4 带给我们无限震撼的同时，其天然的缺陷和诸多的限制也让开发者头痛不已。例如输入端上下文（tokens）大小的限制，大模型知识来源限制(仅依赖预训练语料)，大模型检索范围过大而导致响应较慢，以及大模型处理长序列时容易遗忘前文内容等。

在大模型的限制下，开发者们不得不寻找其他的解决方案，而向量数据库就是其中之一。向量数据库的核心思想是将文本转换成向量，然后将向量存储在数据库中。当用户输入问题时，将问题转换成向量，然后在数据库中搜索最相似的向量和上下文，最后将文本返回给用户。

当我们有一份文档需要大模型处理时，例如这份文档是客服培训资料或者操作手册，我们可以先将这份文档的所有内容转化成向量（这个过程称之为 Vector Embedding）；当用户提出相关问题时，将用户的搜索内容转化成向量，然后在数据库中搜索最相似的向量，匹配最相似的几个上下文；最后将上下文返回给大模型。这样不仅可以大大减少大模型的计算量，提高响应速度，更重要的是能降低成本，并绕过大模型的 tokens 限制。

贝格迈思在研发以智能数据库AiSQL为核心的新一代自适应数据智能平台BigInsights中，优化实现了数据的向量化储存及向量引擎检索。同时，不断改进数据库系统，提升性能、稳定性和用户体验。

向量数据库的作用当然不止步于文字语义搜索，在传统的 AI 和机器学习场景中，还包含人脸识别、图像搜索、语音识别等功能。但不可否认的是，这一轮向量数据库的火爆，正是因为它使 AI 进行理解和维护长期记忆，以执行复杂任务时有非常大的帮助。

二、向量数据库的核心技术

1. Vector Embeddings

对于传统数据库，搜索功能都是基于不同的索引方式（BTree、倒排索引等）加上精确匹配和排序算法（BM25、TF-IDF）等实现的，本质还是基于文本的精确匹配。这种索引和搜索算法对于关键字的搜索功能非常合适，但对于语义搜索功能就非常弱。那么为什么我们需要词嵌入呢？在词嵌入还没有流行之前，NLP已经是深度学习和机器学习等领域中最重要的问题之一。但大家知道，无论是深度学习还是机器学习模型，它们本身是不理解字母或字符的，只认识数字。所以，无论是中文汉字还是英文字母，我们都需要将它们转化为数字才能输入到模型中进行处理，这个过程称为“向量化”。

例如，如果你搜索“小狗”，那么你只能得到带有“小狗”关键字相关的结果，而无法得到“柯基”、“金毛”等结果。因为“小狗”和“金毛”是不同的词，传统数据库无法识别它们的语义关系。所以传统的应用需要人为地将“小狗”和“金毛”等词之间打上特征标签进行关联，这样才能实现语义搜索。而如何生成和挑选特征这个过程，也被称为 Feature Engineering (特征工程)，它是将原始数据转化成更好的表达问题本质特征的过程。

但是如果你需要处理非结构化数据，就会发现它的特征数量开始快速膨胀。如果我们处理的是图像、音频、视频等数据，这个过程就变得非常困难。例如图像，可以标注颜色、形状、纹理、边缘、对象、场景等特征，但这些特征太多且难以进行人为标注；所以我们需要一种自动化的方式来提取这些特征，而这可以通过 Vector Embedding 实现。

Vector Embedding 是由 AI 模型（例如大型语言模型 LLM）生成的，它会根据不同算法生成高维度的向量数据，代表着数据的不同特征，这些特征代表了数据的不同维度。例如，对于文本，这些特征可能包括词汇、语法、语义、情感、情绪、主题、上下文等；对于音频，这些特征可能包括音调、节奏、音高、音色、音量、语音、音乐等。

2.相似性搜索 (Similarity Search)

可以通过比较向量之间的距离来判断它们的相似度，那么如何将它应用到真实的场景中呢？如果想要在一个海量的数据中找到和某个向量最相似的向量，我们需要对数据库中的每个向量进行一次比较计算，但这样的计算量是非常巨大的，所以我们需要一种高效的算法来解决这个问题。

高效的搜索算法有很多，其主要思想是通过两种方式提高搜索效率：

(1) 减少向量大小——通过降维或减少表示向量值的长度；

(2) 缩小搜索范围——可以通过聚类或将向量组织成基于树形、图形结构来实现，并限制搜索范围仅在最接近的簇中进行，或者通过最相似的分支进行过滤。

我们首先来介绍一下大部分算法共有的核心概念，也就是聚类。

2.1 K-Means 和 Faiss

我们可以在保存向量数据后，先对向量数据先进行聚类。例如下图在二维坐标系中，划定了 4 个聚类中心，然后将每个向量分配到最近的聚类中心。经过聚类算法不断调整聚类中心位置，这样就可以将向量数据分成 4 个簇。每次搜索时，只需要先判断搜索向量属于哪个簇，然后再在这一个簇中进行搜索，这样就从 4 个簇的搜索范围减少到了 1 个簇，大大减少了搜索的范围。

常见的聚类算法有 K-Means，它可以将数据分成 k 个类别，其中 k 是预先指定的。以下是 k-means 算法的基本步骤：

(1) 选择 k 个初始聚类中心；

(2) 将每个数据点分配到最近的聚类中心；

(3) 计算每个聚类的新中心；

(4) 重复步骤 2 和 3，直到聚类中心不再改变或达到最大迭代次数。

但是这种搜索方式也有一些缺点，例如在搜索时，如果搜索的内容正好处于两个分类区域的中间，就很有可能遗漏掉最相似的向量。

现实情况中，向量的分布也不会像上图区分那么明显，往往区域的边界是相邻的，就像下图 Faiss算法一样。

我们可以将向量想象为包含在 Voronoi 单元格中，当引入一个新的查询向量时，首先测量其与质心 (centroids) 之间的距离，然后将搜索范围限制在该质心所在的单元格内。

那么为了解决搜索时可能存在的遗漏问题，可以将搜索范围动态调整，例如当 nprobe = 1 时，只搜索最近的一个聚类中心；当 nprobe = 2 时，搜索最近的两个聚类中心，我们可以根据实际业务的需求调整 nprobe 的值。

实际上，除了暴力搜索能完美的搜索出最相邻，所有的搜索算法只能在速度和质量还有内存上做一个权衡，这些算法也被称为近似最相邻（Approximate Nearest Neighbor）。

2.2 Product Quantization (PQ)

在大规模数据集中，聚类算法最大的问题在于内存占用太大。这主要体现在两个方面：

(1) 需要保存每个向量的坐标，而每个坐标都是一个浮点数，占用的内存非常大；

(2) 需要维护聚类中心和每个向量的聚类中心索引，也会占用大量的内存。

对于第一个问题，可以通过量化 (Quantization) 的方式解决，也就是常见的有损压缩。例如在内存中可以将聚类中心里的每一个向量都用聚类中心的向量来表示，并维护一个所有向量到聚类中心的码本，这样就能大大减少内存的占用。

但这仍然不能解决所有问题，在K-Means 和 Faiss的例子中，二维坐标系中划分了聚类中心。同理，高维坐标系中，也可以划定多个聚类中心点，不断调整和迭代，直到找到多个稳定和收敛的中心点。但是在高维坐标系中，还会遇到维度灾难问题。具体来说，随着维度的增加，数据点之间的距离会呈指数级增长。这也就意味着，在高维坐标系中，需要更多的聚类中心点将数据点分成更小的簇，才能提高分类的质量。否则，向量和自己的聚类中心距离很远，会极大降低搜索的速度和质量。

但如果想要维持分类和搜索质量，就需要维护数量庞大的聚类中心。随之而来会带来另一个问题，那就是聚类中心点的数量会随着维度的增加而指数级增长，这样会导致我们存储码本的数量极速增加，从而极大增加内存的消耗。

例如一个 128 维的向量，需要维护 2^64 个聚类中心才能维持不错的量化结果，但这样的码本存储大小已经超过维护原始向量的内存大小了。解决这个问题的方法是将向量分解为多个子向量，然后对每个子向量独立进行量化。比如将 128 维的向量分为 8 个 16 维的向量，然后在 8 个 16 维的子向量上分别进行聚类。因为 16 维的子向量大概只需要 256 个聚类中心就能得到还不错的量化结果，所以就可以将码本的大小从 2^64 降低到 8 * 256 = 2048 个聚类中心，从而降低内存开销。

在将向量进行编码后，也将得到 8 个编码值，将它们拼起来就是该向量的最终编码值。使用时，只需要将这 8 个编码值，分别在 8 个子码本中搜索出对应的 16 维向量，就能将它们使用笛卡尔积的方式组合成一个 128 维的向量，从而得到最终的搜索结果。这也就是乘积量化（Product Quantization）的原理。

使用 PQ 算法，可以显著减少内存开销，同时加快搜索速度，它唯一的问题是搜索质量会有所下降。但就像我们刚才所讲，所有算法都是在内存、速度和质量上做一个权衡。

2.3 Hierarchical Navigable Small Worlds (HNSW)

除聚类外，也可以通过构建树或者构建图的方式来实现近似最近邻搜索。这种方法的基本思想是每次将向量加到数据库中时，就先找到与它最相邻的向量，然后将它们连接起来，这样就构成了一个图。当需要搜索时，就可以从图中的某个节点开始，不断进行最相邻搜索和最短路径计算，直到找到最相似的向量。

这种算法能保证搜索质量，但是如果所有的节点都以最短的路径相连，如图中最下面的一层，那么在搜索时，同样需要遍历所有节点。

解决这个问题的思路与常见的跳表算法相似，如下图搜索跳表，从最高层开始，沿着具有最长“跳过”的边向右移动。如果发现当前节点的值大于要搜索的值时，我们知道已经超过了目标，因此我们会在下一级中向前一个节点。

HNSW 继承了相同的分层格式，最高层具有更长的边缘（用于快速搜索），而较低层具有较短的边缘（用于准确搜索）。具体来说，可以将图分为多层，每一层都是一个小世界，图中的节点都是相互连接的，且每一层的节点都会连接到上一层的节点。当需要搜索时，就可以从第一层开始，因为第一层的节点之间距离很长，可以减少搜索时间，再逐层向下搜索；又因为最下层相似节点之间相互关联，所以可以保证搜索的质量，能够找到最相似的向量。

HNSW 算法是一种经典的空间换时间算法，它的搜索质量和搜索速度都比较高，但它的内存开销也比较大。因为不仅需要将所有的向量都存储在内存中，还需要维护一个图的结构，也同样需要存储。所以这类算法需要根据实际的场景来选择。

2.4 Locality Sensitive Hashing (LSH)

局部敏感哈希（Locality Sensitive Hashing）也是一种使用近似最近邻搜索的索引技术。它的特点是快速，同时仍提供一个近似、非穷举的结果。LSH 使用一组哈希函数将相似向量映射到“桶”中，从而使相似向量具有相同的哈希值。这样，就可以通过比较哈希值来判断向量之间的相似度。

通常，我们设计的哈希算法都是力求减少哈希碰撞的次数，因为哈希函数的搜索时间复杂度是 O(1)。但是，如果存在哈希碰撞，即两个不同的关键字被映射到同一个桶中，那么就需要使用链表等数据结构来解决冲突。在这种情况下，搜索的时间复杂度通常是 O(n)，其中n是链表的长度。所以为了提高哈希函数的搜索效率，通常会将哈希函数的碰撞概率尽可能的小。

但是在向量搜索中，我们的目的是为了找到相似的向量，所以可以专门设计一种哈希函数，使得哈希碰撞的概率尽可能高，并且位置越近或者越相似的向量越容易碰撞，这样相似的向量就会被映射到同一个桶中。等搜索特定向量时，为了找到给定查询向量的最近邻，使用相同的哈希函数将类似向量“分桶”到哈希表中。查询向量被散列到特定表中，然后与该表中的其他向量进行比较以找到最接近的匹配项。这种方法比搜索整个数据集要快得多，因为每个哈希表桶中的向量远少于整个空间中的向量数。

那么这个哈希函数该如何设计呢？为了大家更好理解，我们先从二维坐标系解释。如下所图示，在二维坐标系中可以通过随机生成一条直线，将二维坐标系划分为两个区域，这样就可以通过判断向量是否在直线的同一边来判断它们是否相似。例如下图通过随机生成 4 条直线，这样就可以通过 4 个二进制数来表示一个向量的位置，例如 A 和 B 表示向量在同一个区域。

这个原理很简单，如果两个向量的距离很近，那么它们在直线同一边的概率就会很高，例如直线穿过 AC 的概率就远大于直线穿过 AB 的概率。所以 AB 在同一侧的概率就远大于 AC 在同一侧的概率。

当搜索一个向量时，将这个向量再次进行哈希函数计算，得到相同桶中的向量，然后再通过暴力搜索的方式，找到最接近的向量。如下图如果再搜索一个向量经过了哈希函数，得到了 0110 的值，就会直接找到和它同一个桶中相似的向量 D，从而大大减少了搜索的时间。

3. 相似性测量 (Similarity Measurement)

上面我们讨论了向量数据库的不同搜索算法，但是还没有讨论如何衡量相似性。在相似性搜索中，需要计算两个向量之间的距离，然后根据距离来判断它们的相似度。而如何计算向量在高维空间的距离呢？有三种常见的向量相似度算法：欧几里德距离、余弦相似度和点积相似度。

3.1 欧几里得距离（Euclidean Distance）

欧几里得距离是指两个向量之间的距离，它的计算公式为：

其中，A 和 B 分别表示两个向量，n 表示向量的维度。

欧几里得距离算法的优点是可以反映向量的绝对距离，适用于需要考虑向量长度的相似性计算。

3.2 余弦相似度（Cosine Similarity）

余弦相似度是指两个向量之间的夹角余弦值，它的计算公式为：

其中，A 和 B 分别表示两个向量，⋅表示向量的点积，

∣A∣ 和 ∣B∣ 分别表示两个向量的模长。

余弦相似度对向量的长度不敏感，只关注向量的方向，因此适用于高维向量的相似性计算。

3.3 点积相似度 (Dot product Similarity)

向量的点积相似度是指两个向量之间的点积值，它的计算公式为：

其中，A 和 B 分别表示两个向量，n 表示向量的维度。

点积相似度算法的优点在于它简单易懂，计算速度快，并且兼顾了向量的长度和方向。

三、向量数据库发展趋势

• 应用领域拓展：目前主要应用于图像搜索、音乐推荐、文本分类等领域，未来可能运用于语音识别、自然语言处理、智能推荐等。
• 性能提升：随着技术不断提升，向量数据库的性能将会进一步提升，会有更快的查询速度、更高的并发处理能力等。
• 安全性提高：未来向量数据库会加强数据加密，提高访问控制，以提高数据库安全性。
• 云化趋势：随着云计算技术的发展，向量数据库也将会趋向云化，将向量数据库部署在云端，提供云服务。
• 应用场景：

检索：传统的关键词搜索，搜索结果局限于输入的关键词，而向量数据库是基于文本生成 embedding向量再进行检索，检索结果范围更广。

语义分析：包括文字、图像、行为等多方面的语义分析，以图搜图等模糊数据匹配。

人工智能NLP场景：包括搜索引擎和问答机器人。用向量数据库对问题进行相似性查找，可以得到相关结果。

四、小结

这篇文章简要介绍了向量数据库的不同搜索算法及相似性衡量。贝格迈思在研发以智能数据库AiSQL为核心的新一代自适应数据智能平台BigInsights中，通过多种算法的优化实践，充分实现数据的向量化储存及向量引擎检索。作为数据智能技术创新引领者，凭借业内领先的各项技术，持续开发多种创新型应用产品，打造数据应用生态。

欢迎大家的持续关注与交流，我们期待与大家不断进行技术交流与经验分享，为大家呈现更多精彩纷呈的硬核技术内容。同时，也期待各位技术精英的加入，共创共享创新成果，共同实现“人人惠及数据智能”的良好愿景！

参考文献：

1.Mikolov T, Chen K, Corrado G, et al. Efficient estimation of word representations in vector space[J]. arXiv preprint arXiv:1301.3781, 2013.

2.Jegou H, Douze M, Schmid C. Product quantization for nearest neighbor search[J]. IEEE transactions on pattern analysis and machine intelligence, 2010, 33(1): 117-128.

3.Y. A. Malkov and D. A. Yashunin, "Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs," in IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 42, no. 4, pp. 824-836, 1 April 2020, doi: 10.1109/TPAMI.2018.2889473.