如何在您的 Milvus 实例中选择向量索引：视觉指南

相似性搜索已经成为数据科学和人工智能应用中最受欢迎的现实世界用例之一。推荐系统、信息检索和文档聚类等任务都依赖于相似性搜索作为其核心算法。

一个健全的相似性搜索系统必须能够快速且高效地提供准确结果。然而，随着数据量的增长，满足所有这些要求变得越来越具有挑战性。因此，需要方法和技术来提高相似性搜索任务的可扩展性。

在本文中，我们将探讨几种向量索引策略，这些策略可以用于高效执行相似性搜索，即使在我们需要考虑大量数据和多个约束的情况下。

什么是向量索引？ 相似性搜索是自然语言处理（NLP）的关键现实世界应用之一，特别是在处理文本作为我们的输入数据时尤为重要。由于机器学习模型不能直接处理原始文本，因此需要将这些文本转换为向量嵌入。

包括 BM25、Sentence Transformers、OpenAI、BG3 和 SPLADE 在内的几种模型可以将原始文本转换为嵌入。

一旦我们有了一组向量嵌入，就可以使用各种距离度量（如内积、余弦距离、欧几里得距离、汉明距离、杰卡德距离等）计算一个嵌入与另一个嵌入之间的距离。

相似性搜索的常见工作流程如下：

1. 我们将一组嵌入存储在数据库中（通常是专用的向量数据库）。
2. 给定用户查询，我们将该查询转换为嵌入。
3. 通过计算距离，在查询嵌入和数据库中的每个嵌入之间执行相似性搜索。
4. 数据库中距离最小的嵌入与用户查询最相关。

80.1.png

在存储过程中，会在向量数据库中的每个嵌入之上构建一个称为索引的特殊数据结构，以促进高效搜索和检索相似嵌入。

可以应用几种索引策略以适应我们的特定用例。通常，有四类索引策略：基于树的、基于图的、基于哈希的和基于量化的索引。

每种方法都有其优缺点，以下表格是我们方便的索引备忘单，可帮助您做出选择。

80表.png

请注意：表中未包括 FAISS、基于哈希的索引（局部敏感哈希）和基于树的索引（ANNOY）。

在接下来的部分，我们将讨论 Milvus 支持的基于这四类索引的索引算法。

Milvus 支持的流行索引类型 Milvus 支持几种索引算法，您可以根据特定用例进行选择。让我们从最基本的 FLAT 索引开始。

FLAT 索引 FLAT 索引是一种直接且基本的相似性搜索算法，它使用 k-最近邻 (kNN) 算法。

80.2.png

考虑一个包含 100 个嵌入的数据库和一个查询嵌入 Q。要找到与 Q 最相似的嵌入，kNN 会使用指定的距离度量计算 Q 与数据库中每个嵌入之间的距离。然后，它识别出距离最小的嵌入作为与 Q 最相似的嵌入。

虽然 kNN 通过穷尽搜索确保了结果的高准确性，但其可扩展性是一个问题。使用这种算法进行向量搜索的时间复杂度随着数据库中向量嵌入的数量线性增加。

当数据库中包含数百万或数十亿嵌入时，使用这种方法执行向量搜索可能会耗费时间。此外，这种方法缺乏向量压缩技术，可能会导致尝试存储数百万嵌入时的问题，这些嵌入可能无法全部装入 RAM。

倒排文件 FLAT (IVF-FLAT) 索引 倒排文件 FLAT (IVF-FLAT) 索引旨在通过实现近似最近邻 (ANNs) 算法而不是原生 kNN，提高基本 FLAT 索引的搜索性能。IVF_FLAT 通过将数据库中的嵌入划分为几个不相交的分区来工作。每个分区有一个中心点称为质心，数据库中的每个向量嵌入都根据最近的质心与特定分区关联。

80.3.png

当提供查询嵌入 Q 时，IVF-FLAT 只需要计算 Q 与每个质心之间的距离，而不需要计算数据库中所有嵌入的距离。然后选择距离最小的质心，并使用与该分区关联的嵌入作为最终搜索的候选。

这种索引方法加快了搜索过程，但它有一个潜在的缺点：作为查询嵌入 Q 最近的候选可能不是确切最近的一个。如果 Q 最近的嵌入位于与基于最近质心选择的分区不同的分区中，就会发生这种情况（见下图）。

80.4.png

为了解决这个问题，IVF-FLAT 提供了两个我们可以调整的超参数：

1. nlist：使用 k-means 算法指定要创建的分区数量。
2. nprobe：指定在搜索候选时要考虑的分区数量。

如果我们将 nprobe 设置为 3 而不是 1，我们将得到以下结果：

80.5.png

通过增加 nprobe 值，您可以在搜索中包含更多分区，这可以帮助确保不会错过查询嵌入 Q 最近的嵌入，即使它位于不同的分区。然而，这是以增加搜索时间为代价的，因为需要评估更多的候选。

倒排文件索引与量化 (IVF-SQ8 和 IVF-PQ) 前面提到的 IVF-FLAT 索引算法加速了向量搜索过程。然而，当内存资源有限时，使用 FLAT 策略可能不是最佳选择，因为它不压缩嵌入的值。

为了解决内存限制问题，可以与 IVF 结合使用额外的步骤，这涉及将每个向量维度中的值映射到低精度整数值。这种映射策略通常称为量化，有两种主要的量化方法：标量量化和乘积量化。

倒排文件索引和标量量化 (IVF-SQ8) 标量量化涉及将表示每个向量维度的浮点数映射到整数。

在标量量化中，第一步是确定并存储数据库中向量每个维度的最大值和最小值，以计算步长。这个步长对于将每个维度中的浮点数缩放到其整数表示至关重要。例如，将 32 位浮点数转换为 8 位整数通常涉及将范围分成 256 个桶。步长可以按以下方式计算：

80.6.png

量化的第 n 个向量维度的版本是通过从其最小值中减去第 n 个维度的值，然后将结果除以步长来获得。

倒排文件索引和乘积量化 (IVF-PQ) 乘积量化通过考虑每个维度的分布来解决标量量化的限制。

乘积量化将向量嵌入划分为子向量，在每个子向量内进行聚类以创建质心，并使用最近质心的 ID 对每个子向量进行编码。这种方法在子向量内创建不相交的分区，类似于 IVF-FLAT。

乘积量化将向量嵌入划分为子向量，对每个子向量进行聚类以创建质心，并使用最近质心的 ID 对每个子向量进行编码。这种方法在子向量内创建不相交的分区，类似于 IVF-FLAT。

80.7.png

质心的 ID，称为 PQ 码，表示为 8 位整数，从而实现向量嵌入的内存高效编码。

与标量量化相比，乘积量化提供了更强大内存压缩，使其成为处理相似性搜索应用中巨大内存限制的非常有用的方法。

分层可导航小世界 (HNSW) HNSW 是一种基于图的索引算法，结合了两个关键概念：跳过列表和可导航小世界 (NSW) 图。

跳过列表是由多个链表层组成的概率数据结构。最低层包含所有元素的原始链表。当我们移动到更高层时，链表逐渐跳过更多元素，导致每高层的元素更少。

在搜索过程中，我们从最高层开始，逐渐下降到较低层，直到找到所需的元素。因此，跳过列表可以显著加快搜索过程。

假设我们有一个 3 层的跳过列表和原始链表中的 8 个元素。如果我们想要找到元素 7，搜索过程将如下所示：

80.8.png

在另一方面，NSW 图是通过随机打乱数据点并逐个插入它们构建的，每个点连接到预定义数量的边（M）。这创建了一个图结构，表现出“小世界”现象，其中任意两个点通过相对较短的路径连接。

例如，假设我们有 5 个数据点，然后我们设置M=2。以下是构建 HSW 图的逐步过程：

80.9.png

“分层”一词在 HNSW 中指的是结合跳过列表和 NSW 图概念。HNSW 由多层图组成，其中较低层包含完整的数据点集，而较高层只包含少量的点。

HNSW 首先通过为每个数据点（在我们称为图算法中的“节点”）分配一个从 0 到 l 的随机整数开始，其中 l 是该数据点可以在多层图中出现的最大层。如果一个数据点有 l=2，并且图中的总层数是 5，那么该数据点应该只出现在第二层，并且不应该是第三层及以上。

在搜索过程中，HNSW 首先选择一个入口点，这应该是在最高层中出现的数据点。然后它搜索与查询点最近的邻居，并递归地在较低层继续搜索，直到找到最近的点。

HNSW 有两个关键的超参数，我们可以调整以提高搜索准确性：

1. efConstruction：在每层考虑的邻居数量，以找到最近的邻居。较高的值会导致更彻底的搜索和更好的准确性，但计算时间会增加。
2. efSearch：在每层考虑的最近邻居数量，作为入口点。

通过利用跳过列表和 NSW 图的概念，HNSW 可以通过跳过许多没有希望的数据点，显著加快相似性搜索过程。

使用哪种索引类型？ 现在我们知道了 Milvus 支持的不同索引类型。了解 Milvus 支持的各种索引类型至关重要，但决定使用哪种索引类型取决于您的特定用例和相似性搜索的目标。

诸如结果准确性的重要性、查询速度、内存限制和数据大小等因素在选择适当的索引类型时起着重要作用。为了帮助您决定用例的索引类型，请参阅以下流程图：

80.10.png

对于确保 100% 准确性的精确搜索，FLAT 索引是理想的选择。然而，如果速度是优先考虑的，并且确切的准确性不是那么关键，可以选择其他索引算法。

如果内存资源是一个问题，考虑使用像 IVF-SQ8 或 IVF-PQ 这样的量化索引算法。否则，像 IVF-FLAT 或 HNSW 这样的选项可能是合适的。对于较小的数据集（小于 2GB），IVF-FLAT 可能足够，而较大的数据集（超过 2GB）可以从 HNSW 中受益，以提高搜索速度，同时仍然保持高召回率。

在数据集非常大的情况下，结合 IVF 和量化方法仍然是防止内存过载的首选方法。

结论 为存储向量嵌入选择正确的索引类型对于实现期望的搜索结果至关重要。每种索引类型都有自己的优势和考虑因素，使得选择取决于您用例的具体要求。

要进一步了解本文讨论的索引方法，请查看我们提供的额外资源。

• 关于向量索引基础的所有知识
• 标量量化和乘积量化
• 分层可导航小世界 (HNSW)