向量数据库原理之向量索引
向量索引
在之前的综述性文章中对milvus源码搭建进行了详细讲解，并将其内容整理为独立的文章标题为向量数据库milvus源码剖析之开篇。该文章深入探讨了向量数据库的一般特点及其应用价值。
-
向量索引：用来支持高效的搜索，快速定位与查询向量相关的数据集。
-
相似度搜索：支持余弦、欧式距离等的搜索。
-
分布式架构，存算分离等。
在本节中，我们将深入探讨向量索引的相关内容。众所周知，在现代信息技术领域中，向量数据库的建立旨在通过高效的存储与检索机制支持海量数据的管理。提升向量数据类型的的地位与重要性在于其在信息组织与检索中的关键作用。衡量两个向量之间的相似程度通常采用距离度量这一方法，并且其中常见的评估指标包括余弦相似度和点积得分等指标。
通常来说，向量索引方法可以按照数据结构与压缩级别来划分。
1.数据结构
索引按照数据结构划分如下：
1.1 基于分区的索引
典型的倒排文件索引系统通常采用Inverted file indices, such as IVF, typically partition the vector space into multiple subspaces or subpartitions. Each subspace will be assigned a center point. The system then calculates the relative position of the query vector to each region. The closest center point is identified and becomes the focus for detailed search within its corresponding region.
问题：最接近的质心可能会存在于多个子空间（解决办法：一般建议同时考虑最近n个质心，并在每个对应子空间内展开进一步搜索）
1.2 基于树的索引
基于树的索引结构支持利用二叉搜索树在高维空间中进行高效的搜索操作。特定的构造策略决定了相似的数据点更容易聚集在同一子树内，进而能够更加有效地发现近似的最近邻居。
缺点：它们主要适用于低维数据，在处理高维数据时准确性可能会受到限制，并且容易退化为线性扫描的方法。
1.3 基于hash的索引
采用基于哈希的技术（如Locality Sensitive Hashing）将高维空间中的数据集映射至低维特征空间；该过程旨在尽可能保留原始数据间的相似性关系.通过哈希函数将每个数据样本分配至多个_hash_池中；从而提高相同类别的样本被分入同一池的概率；而不同类别的样本通常不会落入同一_hash_池中.
该哈希索引方案具备显著优势在于其能够快速处理海量数据；然而，在准确性方面存在一定的问题。
1.4 基于图的索引
该方法的核心思想是利用向量空间中的数据点构建一个图；其中节点代表数据值；边则反映了各数据点间的相似程度；该构造策略有助于将具有较高相似度的数据节点通过边相连；而 ANN 搜索算法旨在通过高效路径探索整个图的结构。
基于图论的方法具有显著的优势，在于它们在处理高维数据时能够实现高效的近似 nearest neighbor 搜索，并且还能大幅减少内存占用量。此外，在执行效率上也能显著提升算法效率。
当然，除了以上还有基于图树混合的索引之类的。
2.压缩级别
第一种压缩级别是：平面法或暴力法索引。指的是未修改状态下存储向量的索引。当一个查询请求到来时，通过暴力方法计算数据库中所有向量的距离并返回最近距离结果。该方案适用于较小规模的数据集以获取完全准确且精确搜索结果的情景。
第二种压缩级别对应于quantization这一技术。显而易见地，在提高搜索效率方面的一个显著方法即是进行数据压缩操作；这种技术一般被称作量化的手段。基于此原理构建的量化索引是通过将quantization与前面提到的索引架构相结合的方式实现的；该方法能够有效优化内存占用并提升查询性能；例如：IVF-PQ这一经典算法就是其中一例典型应用。该技术一般分为两类：标量量化的理论框架（Scalar Quantization (SQ)）以及乘积量化的实现方案（Product Quantization (PQ)）。
标量量化（SQ）通过将向量中的浮点数转换为整数来实现这一目标；它是一种方法，在每个维度上基于最小值与最大值的均等分段来进行向量分割。
乘积量化（PQ）是PQ的核心思想是将向量的所有维度划分为多个子空间，每个子空间一部分维度，将高维向量空间分解成小维度子空间的笛卡尔积，通过对每个子空间进行量化来形成各自的簇。向量由短码表示，这样可以通过这些码（称为再现值）有效地估算向量之间的距离。其中的压缩体现在：对每个子向量进行独立量化。每个子向量使用一个预先计算好的码本(质心集)，将子向量映射为一个短码。这个码本是通过对训练数据进行聚类（如K-means）得到的，每个子空间都有自己独立的codebook。
本节就先总结这么多内容吧，后续将会从实践出发去深入编写代码。
跟我一起实践写代码，戳这里呀～
往期推荐：
