向量数据库（第 3 部分）：并非所有索引都是一样的

这是我关于向量数据库的系列文章的第三篇。第一部分比较了各种数据库供应商的产品以及它们在高层面上的区别，而第二部分则着重介绍了向量数据库的基础知识和功能。您可能已经阅读过Dmitry Kan在2021年撰写的优秀文章《并非所有向量数据库都是相同的》1，该文章涵盖了市场上各种向量数据库之间的差异。自那时以来，这个领域一直在不断发展，因为每个数据库在其内部都与其他数据库不同，所以我认为深入探讨索引是有意义的，因为索引是向量搜索的基础。假设你已经充分了解什么是向量数据库，那么值得回过头来思考一下，它是如何如此出色地扩展到能够搜索数百万、数十亿甚至数万亿个向量的呢？向量数据库的主要目标是提供一种快速高效的方式来存储和语义查询数据，以使数据类型成为一等公民。两个向量之间的相似度是通过余弦距离或点积等距离度量来衡量的。在使用向量数据库时，重要的是区分搜索算法和近似最近邻（ANN）搜索算法所操作的底层索引。与大多数情况一样，选择向量索引涉及到准确性（精确度/召回率）和速度/吞吐量之间的权衡。经过查阅文献，我发现向量索引方法可以按照数据结构和压缩级别两个层次进行组织。这些分类并不是详尽无遗的，许多来源对于如何正确组织各种索引存在分歧，所以这是我最好的尝试来理解这一切。下面开始吧！

级别1：数据结构

根据用于构建索引的数据结构对索引进行组织有助于理解。最好通过可视化的方式进行探索。根据数据结构对索引进行组织可以提供更直观的理解。

哈希索引

哈希索引（Hash-based index）是一种基于哈希函数的索引方法，例如局部敏感哈希（Locally Sensitive Hashing，LSH）。哈希索引将高维数据转换为低维哈希码，旨在尽可能保持原始数据的相似性。在建立索引时，数据集会被多次哈希，以确保相似的数据点更有可能发生碰撞（这与传统的哈希技术相反，传统哈希技术的目标是尽量减少碰撞）。在查询时，查询点也会使用与建立索引时相同的哈希函数进行哈希，由于相似的数据点被分配到同一个哈希桶中，所以检索非常快速。哈希索引的主要优点是在处理大量数据时非常快速，但缺点是准确性较低。

基于树的索引

基于树的索引结构（Tree-based index）通过二叉搜索树实现在高维空间中的快速搜索。树的构建方式使得相似的数据点更有可能位于同一子树中，从而更快地发现近似最近邻。Annoy（Approximate Nearest Neighbors Oh Yeah）是一种使用二叉搜索树森林的方法，由Spotify开发。基于树的索引的缺点是，它们只对低维数据表现较好，在高维数据中准确性较低，因为它们无法充分捕捉数据的复杂性。

基于图的索引

基于图的索引（Graph-based index）是基于数据点在向量空间中形成图的思想构建的索引。图中的节点表示数据值，连接节点的边表示数据点之间的相似性。图的构建方式使得相似的数据点更有可能通过边连接在一起，而近似最近邻（ANN）搜索算法被设计为以高效的方式遍历图。图的索引主要优势在于能够在高维数据中找到近似最近邻，并且具有较高的内存效率，提高性能。下面是图的索引的两个例子：HNSW和Vamana。 将图的索引与树的索引概念相结合的扩展是NGT3（Neighbourhood Graphs and Trees）。由Yahoo! Japan Corporation开发，它在索引过程中进行了两个构建操作：一个将密集的kNN图转换为双向图，另一个逐步构建可导航的小世界（NSW）图。与纯图的索引不同之处在于它使用了类似树状结构（Vantage-point，或称为“VP”树）的范围搜索，这是在图的构建过程中的一种贪婪搜索的变体。由于这两个构建操作导致节点具有较高的出度，为了避免组合爆炸，搜索起点使用范围搜索使遍历更加高效。这使得NGT成为一种混合的图和树的索引。

倒排文件索引

倒排文件索引（Inverted file index，IVF）将向量空间划分为多个细分的单元，称为Voronoi图，这些图减少了搜索空间，类似于聚类的效果。为了找到最近邻，ANN算法只需定位最近Voronoi图单元的质心，然后仅在该单元内进行搜索。IVF的好处在于它有助于设计快速缩小相似性感兴趣区域的ANN算法，但其原始形式的缺点是在细分向量空间的量化步骤可能对于非常大量的数据而言速度较慢。因此，IVF通常与量化方法（如产品量化，PQ）结合使用以提高性能。

级别2：压缩

索引可以组织的第二个级别是它们的压缩级别：一个“平坦”或暴力索引是以未经修改的形式存储向量的索引。当接收到查询向量时，它会与数据库中的每个向量进行详尽的比较，如下面简化的三维空间示例所示。实质上，使用这样的索引就像进行kNN搜索，返回的结果是与k个最近邻向量完全匹配的结果。可以想象，返回结果所需的时间会随着数据大小的增加而线性增加，这在应用于包含数十万个向量的数据集时是不实际的。

为了提高搜索效率，以牺牲一定的检索准确性为代价，可以采用压缩的解决方案。这个过程被称为量化（quantization），其中索引中的底层向量被分解成由较少字节组成的块（通常通过将浮点数转换为整数）以减少内存消耗和搜索过程中的计算成本。

平坦索引

在使用ANN（非穷举）搜索时，当现有的索引（如IVF或HNSW）直接计算查询向量与数据库向量之间的距离时，它被称为“平坦”索引。这与量化变体有所区别。在这种方式下使用时，它们被称为IVF-Flat、HNSW-Flat等。

量化索引

量化索引（Quantized indexes）是将现有的索引（如IVF、HNSW、Vamana）与量化等压缩方法结合起来，以减少内存占用并加快搜索速度。量化通常有两种类型：标量量化（Scalar Quantization，SQ）和产品量化（Product Quantization，PQ）。SQ将向量中的浮点数转换为整数（在字节大小上要小得多），通过将向量对称地分成考虑每个维度的最小值和最大值的区间。 PQ是一种更复杂的方法，它考虑了每个向量维度上的值分布，同时进行压缩和数据降维。PQ的思想是将较大维度的向量空间分解为较小维度子空间的笛卡尔积，通过将每个子空间量化为自己的聚类来表示向量，使得可以从它们的代码（称为重构值）有效地估计它们之间的距离。与SQ不同，PQ使用了非对称的分箱过程，增加了精度，因为它将每个子空间内向量的分布纳入了近似距离估计的一部分。然而，这也存在一个权衡，即它会显著降低召回率。

流行的索引

在列出的所有索引方法中，大多数专门构建的向量数据库只实现其中的一小部分。这是一个非常快速发展的领域，因此在阅读本文时，很多信息可能已经过时。强烈建议您查阅您感兴趣的数据库的最新文档，了解它们支持哪些索引。在本节中，我将重点介绍一些受多个供应商关注的热门和即将推出的索引。

IVF-PQ

VF-PQ（向量倒排文件索引与产品量化）是在Milvus和LanceDB等数据库中提供的复合索引。索引的IVF部分用于缩小搜索空间，而PQ部分用于加速查询向量与数据库向量之间的距离计算，并通过量化向量来减少内存需求。将两者结合的好处在于，由于PQ组件的存在，速度得到了大幅提升，并且IVF组件有助于提高（通常由于PQ组件而受到损害的）召回率。 PQ组件可以根据下面的图表进行分解。表示数据点的每个向量由固定数量的维度d组成（取决于上游使用的嵌入模型，通常为数百或数千）。由于在大型数据集上存储这么多32位或64位浮点数可能非常昂贵，产品量化通过两个阶段来解决这个问题：第一阶段是粗量化阶段，将向量分成m个子向量，每个子向量的维度为d/m，并为每个子向量分配一个量化值（称为“重构值”），将原始向量映射到该子空间中点的质心。 第二阶段类似于k-means聚类，通过最小化原始向量与量化向量质心之间的距离来学习一组“码本”值。通过将大型高维向量映射为较小的低维子向量，只需存储量化值的码本，从而使内存占用量大大减小。

然后，IVF被应用于PQ向量空间 - 对于空间中的每个点，都有一个相应的区域，称为Voronoi单元，其中包含所有距离源点（种子点）比任何其他点更近的空间中的点。这些种子点用于创建一个倒排索引，将每个质心与空间中的向量列表相关联。

根据查询向量所在的位置，它可能靠近多个Voronoi单元的边界，使得从哪些单元返回最近邻变得模糊不清，导致边缘问题。因此，IVF-PQ索引涉及设置一个额外的参数n_probes，告诉搜索算法向外扩展到参数指定的单元数。 为了有效地构建IVF-PQ索引，需要做出两个选择：PQ步骤的子向量数量和IVF步骤的分区数量。子向量数量越大，每个子空间越小，减少了由于压缩而导致的信息损失。然而，较大的子向量数量也会导致每个PQ步骤中的更多I/O和计算量，因此必须将此数量最小化，以保持计算成本低廉。类似地，IVF步骤中的分区数量必须选择以在召回率和搜索速度之间取得平衡。当分区数量等于数据集中的向量数量时，极限情况下是暴力搜索，这是最准确的（召回率为1），但实质上将其变成了IVF-Flat索引。事实上，LanceDB的IVF-PQ索引文档中确切描述了在创建索引时的这些权衡，因此值得深入了解这些概念，以了解如何在实际场景中应用它们。

HNSW

分层可导航小世界（HNSW）图是构建向量索引中最受欢迎的算法之一 - 在撰写本文时，几乎每个数据库供应商都将其作为首选选项。它也是最直观的算法之一，强烈建议阅读介绍它的原始论文。 在高层次上，HNSW基于小世界图现象构建，该现象表明尽管图中的大多数节点不是彼此的邻居，但给定节点的邻居很可能是彼此的邻居，无论图的大小如何。基本上，图中的任何节点都可以通过相对较少的步骤从其他节点到达。在下面的示例中，实心填充的蓝色和红色节点可以在仅经过3个跳跃的情况下相互到达，尽管它们在图中可能被认为是相距较远的。

您的数据所在的向量空间也可以被视为一个可导航的小世界（NSW）图，其中节点表示数据点，边表示相似性，即描述两个节点在向量空间中的接近程度的数值。NSW通过构建一个无向图来确保全局连通性，即给定任意入口点，可以到达图中的任何节点。首先形成远距离的边（连接远离的节点，需要多次遍历），然后形成短距离的边（连接附近的节点）。长边提高了搜索效率，而短边提高了搜索准确性。可以通过遍历这个图来找到给定查询向量的最近节点。

NSW图的一个问题是它是平坦的 - 某些节点可能会创建密集的“交通枢纽”，降低遍历的效率，并导致方法的搜索复杂度为多对数级别。HNSW通过分层图结构来解决这个问题，并修复了每个节点邻居数量的上限，将搜索复杂度降低到对数级别。基本思想是根据节点之间的距离尺度将最近邻分层在图中。图中的长边保留在顶层（即最稀疏的层），每个较低的层包含的边比上面的层更短。最低层形成完全图，并且搜索是从上到下进行的。如果所有层都“折叠”到彼此中，HNSW图本质上就是一个NSW图。

上面的图示展示了如何在顶层给定任意入口点的情况下，可以快速遍历整个图，逐层降低，直到找到与查询向量最近的邻居。HNSW相对于IVF的最大优势在于它能够在复杂的高维向量空间中以高召回率找到近似最近邻。事实上，在其发布时（大约2019年），它在基准数据集上产生了最先进的结果，特别是在提高召回率的同时速度也很快，这解释了它的巨大流行。然而，它在内存效率方面不如IVF，除非在搜索时与PQ等方法结合使用来压缩向量。出于这些原因，像Qdrant和Weaviate这样的数据库通常实现了涉及量化的复合索引，例如HNSW-PQ10，同时还提供了调整召回率和查询延迟之间权衡的调节参数。

Vamana

Vamana是最近开发的基于图的索引算法之一，由Subramanya等人与微软研究院印度合作，在2019年的NeurIPS会议上首次提出。Vamana的显著特点包括：

• 它从头开始设计，既可以在内存中工作（大多数索引都是为此设计的），也可以在磁盘上工作。微软提出的磁盘实现被称为DiskANN。对于向量数据库供应商来说，磁盘索引似乎是一个巨大的实现挑战，所以这是Vamana与其他算法的区别之一。
• 它允许对无法放入内存的数据集进行索引，通过构建重叠分区的较小索引，可以轻松合并为一个单一索引，其查询性能与为整个数据集构建的单一索引相当。
• 它还可以与PQ等现成的向量压缩方法结合使用，构建一个Vamana-PQ索引，用于支持DiskANN系统 - 数据集的完整精度向量存储在磁盘上，而压缩向量则缓存在内存中，实现了两者的最佳结合。

Vamana通过迭代构建一个有向图，首先从一个随机图开始，其中每个节点表示向量空间中的一个数据点。在开始时，图是高度连接的，即几乎所有节点都相互连接。然后，使用一个目标函数对图进行优化，该函数旨在最大化彼此最接近的节点之间的连接性。这是通过修剪大部分随机的短程边缘，并添加连接相距较远的节点的某些长程边缘（以加快图中的遍历）来实现的。

在查询时，选择全局质心作为入口点。通过长程边快速向右方向进行搜索，这使得算法能够快速跳转到图的端点，并相对快速地缩小到查询向量的最近邻。在下面的示例中，只需要三次跳跃就可以从入口点（全局质心）遍历到图的外边缘，然后到达最近邻。

正如您可能已经注意到的那样，Vamana提供的是一种更多的“内部-外部”搜索方法，而不是HNSW的“外部-内部”搜索方法，其中搜索从顶层的一个随机节点（可能很远）开始，并向内部进行。 目前（截至2023年），没有多少数据库实现了Vamana索引，这可能是由于在磁盘上实现的技术挑战以及对延迟和搜索速度的影响。Milvus11目前是唯一具有可用的磁盘上Vamana索引的供应商，而Weaviate12和LanceDB13目前只有实验性的实现。然而，这是一个快速发展的领域，因此强烈建议您关注关键的向量数据库供应商，以了解最新的发展情况！

流行的矢量数据库中可用的索引

正如本系列的第一部分所示，大多数数据库将HNSW索引作为默认选项实现。

像Milvus、Weaviate、Qdrant和LanceDB这样的数据库提供了简单的调整参数，用于控制其Product Quantization组件中的压缩/量化级别。了解这些索引如何工作的基本原理非常重要，这样您就可以为您的用例选择正确的数据库和索引参数。

结论

专门构建的向量数据库的制造商花费了数千小时来对其索引和存储层进行微调和优化，因此，如果您拥有大型数据集并且需要在向量搜索查询上实现<100毫秒的延迟，那么借助像Weaviate、Qdrant和Milvus这样的成熟、可扩展的开源数据库似乎是一个明智的选择，无论是从开发者的角度还是从业务的角度来看。

• Flat索引是以原始形式存储向量的索引，用于精确的k最近邻搜索。它是最准确的，但也是最慢的。
• IVF-Flat索引使用倒排文件索引来快速缩小搜索空间，比暴力搜索要快得多，但会在召回率方面牺牲一些准确性。
• IVF-PQ使用IVF与Product Quantization结合，对向量进行压缩，减少内存占用并加快搜索速度，同时在召回率方面比纯索引更好。
• HNSW是目前最流行的索引类型，通常与Product Quantization结合使用，以提高搜索速度和内存效率。
• Vamana是一个相对较新的索引，专为磁盘性能设计和优化-它承诺在存储大于内存的向量数据时能够表现出与HNSW相当的性能和速度。然而，目前还没有很多数据库实现Vamana索引，这是由于磁盘性能方面的挑战。

在我看来，LanceDB是未来几个月中最令人兴奋的数据库之一。这是因为它是市场上唯一一个所有向量索引都基于磁盘的向量数据库。这是因为他们在多个方面同时进行创新：

• LanceDB正在构建一种新的高效列式数据格式Lance，旨在成为parquet的现代继任者，并针对向量搜索进行了优化。
• 正是由于这种高效的存储层，LanceDB能够在基于磁盘的索引方面充满信心，与其他供应商不同。
• LanceDB采用了嵌入式（无服务器）的专用架构，从头开始构建。零拷贝数据访问是对基于磁盘的索引的巨大性能提升。
• 数据的自动版本控制，无需额外的基础设施。
• 与AWS S3和Azure Blob Storage等云存储提供商直接集成，非常容易与现有的数据流水线集成。

无论您选择哪个数据库来满足您的用例，我们都可以一致认为，现在是一个非常好的时代，可以尝试和实验这些工具。我知道这篇文章中有很多信息，但下面的参考资料确实帮助我理解了向量数据库的内部工作原理以及它们是如何从零开始构建的。希望您觉得这篇文章有趣，让我们继续学习吧！