向量数据库原理之向量索引

向量索引

在前面的文章中讲解了milvus的源码安装——向量数据库milvus源码剖析之开篇，向量数据库通常具备以下特点：

• 向量索引：用来支持高效的搜索，快速定位与查询向量相关的数据集。
• 相似度搜索：支持余弦、欧式距离等的搜索。
• 分布式架构，存算分离等。

本节将会着重讲向量索引。众所周知，向量数据库的主要目的是提供一种快速有效的方法来存储和高效查询数据，使向量数据类型成为一等公民。两个向量之间的相似性可以通过距离度量来衡量，例如余弦距离或点积。

通常来说，向量索引方法可以按照数据结构与压缩级别来划分。

1.数据结构

索引按照数据结构划分如下：

1.1 基于分区的索引

典型的如倒排文件索引，Inverted file index (IVF) 通常是将向量空间划分为若干个子空间/子分区，每个子空间一个质心，将查询向量与这些执行比较，找到最近质心，然后仅在该质心内进行搜索。

缺点：最接近的质心可能会存在多个子空间(解决办法：通常可以求最近n个质心，然后在这n个质心对应的子空间里面进行搜索)。

1.2 基于树的索引

基于树的索引结构允许通过二叉搜索树在高维空间中快速搜索。树的构造方式使得相似的数据点更有可能出现在同一个子树中，从而可以更快地发现近似的最近邻居。

缺点：它们仅对低维数据表现良好，而对于高维数据则不太准确，容易退化为线性扫描。

1.3 基于hash的索引

基于哈希的索引（例如Locality Sensitive Hashing）将高维数据转换为低维哈希码，旨在尽可能保持原始相似性.使用哈希函数将数据点映射到多个哈希桶中，使得相似的数据点被映射到同一个桶中的概率高，而不相似的数据点被映射到同一个桶中的概率低。

基于哈希的索引的主要优点是它们在扩展到大量数据时速度非常快，但缺点是它们不太准确。

1.4 基于图的索引

基于图的索引其核心思想是：向量空间中的数据点形成一个图，其中节点表示数据值，连接节点的边表示数据点之间的相似性。图的构造方式使得相似的数据点更有可能通过边连接，而 ANN 搜索算法旨在以高效的方式遍历图。

基于图的索引的主要优势在于，它们能够在高维数据中找到近似的最近邻，同时还能节省内存，从而提高性能，例如：HNSW。

当然，除了以上还有基于图树混合的索引之类的。

2.压缩级别

第一种压缩级别是：flat或 brute force index。指以未修改的形式存储向量的索引。当一个query请求到来时，使用暴力的方法与数据库中所有向量进行距离计算，返回最近距离。适合于在小规模，百万级数据集上寻求完全准确和精确的搜索结果的场景。

第二种压缩级别是：quantization。很显然当我们想要提高搜索效率的一个办法便是压缩，这种通常称为量化。而量化索引则是quantization结合上面的索引结构，从而减少内存提高查询效率，例如：IVF-PQ。量化通常有两种类型：标量量化（Scalar Quantization (SQ)）和乘积量化（Product Quantization (PQ)）。

标量量化（SQ）通过将向量中的浮点数转换为整数来实现，这种方法通过对每个维度的最小值和最大值进行对称划分，将向量分割成多个区间。

乘积量化（PQ）是PQ的核心思想是将向量的所有维度划分为多个子空间，每个子空间一部分维度，将高维向量空间分解成小维度子空间的笛卡尔积，通过对每个子空间进行量化来形成各自的簇。向量由短码表示，这样可以通过这些码（称为再现值）有效地估算向量之间的距离。其中的压缩体现在：对每个子向量进行独立量化。每个子向量使用一个预先计算好的码本(质心集)，将子向量映射为一个短码。这个码本是通过对训练数据进行聚类（如K-means）得到的，每个子空间都有自己独立的codebook。

本节就先总结这么多内容吧，后续将会从实践出发去深入编写代码。