向量数据库的索引

为什么要有向量库的索引？

提高高维数据的检索效率

• 向量库的索引目的是以一个相对高效的方式来对向量进行相似性的搜索，一般以特殊的数据结构来组织高位向量，从而避免遍历所有向量所带来的相似性搜索时的效率问题。

优化存储利用资源

• 压缩和编码：一部分索引技术（如乘积量化（PQ）或标量量化（SQ））会对向量进行压缩编码，用更少的bit表示原始向量，显著节省存储空间。当然会损失一定的精度。

支持复杂的查询类型

• 除了支持简单的最近邻搜索，还能高效支持更复杂的查询。
• 范围查询：查找所有与查询向量距离在一定范围内的向量
• 过滤搜索：在基于相似性搜索的同时，结合传统的属性过滤（如“找红色且与这张图片相似的汽车”）一些索引结构能更好地支持这种混合查询。
• 批次查询与流式处理：高效的索引支持一次性对多个查询向量进行检索，这对于许多机器学习流水线的批次处理任务至关重要

常见的向量数据库索引

FLAT

• FLAT Index。扁平索引，最基本的索引方式。暴力遍历所有的变量，由于不涉及任何形式的近似处理和数据压缩，FLAT能够保证100%的召回率。
• 适用于：小数据集，需要绝对精确结果的场景。

IVF

• 倒排文件索引（IVF）。通过将向量数据聚类来减少查询时需要比较的向量数据。（先聚类粗筛，再精查）
  • 首先：计算查询向量与每个簇中心的距离，然后仅选择前N个簇。
  • 在选择的簇中，进行精确匹配。
• 适用于：内存资源受限，对精度有一定容忍的场景。

量化索引

• 通过压缩向量数据来减少存储空间和计算量。主要的量化方式SQ（标量量化），PQ（乘积量化），OPQ（优化乘积量化）。

标量量化 SQ

• 最简单的量化方法。将每个浮点数的值直接转换低比特的整数（如8位，或4位整数）。这种方法易于实现，且量化和反量化过程迅速，显著降低了存储需求。然而，它可能导致较大的量化误差，从而影响检索准确性。

乘积量化 PQ

• 核心思想：分而治之
• 高维向量的直接处理（如计算欧氏距离）计算成本高昂。PQ的核心思路是将一个高维向量分割成多个低维子向量，分别对每个子空间进行量化（聚类），用聚类中心的ID组合来代表原始向量
• 流程
  • 训练阶段
    • 分段 (Partitioning)：将维度为 D的向量均匀划分为 m个段，每段子向量的维度为 D* = D/m
    • 聚类 (Clustering)：在每个子空间内，使用 k-means 算法对所有训练数据的该段子向量进行聚类，生成一个包含 k个聚类中心（质心）的码本（codebook）。每个聚类中心有一个唯一ID（如0到k-1）。m个子空间就有 m个码本
  • 量化阶段
    • 对于任何一个需要存储的新向量，首先将其分成 m个子向量。
    • 对于每个子向量，在它对应的子空间码本中寻找最近的聚类中心。
    • 用该聚类中心的 ID 替换原始的子向量数据。
    • 最终，原始高维向量被转化为一个由 m个ID组成的紧凑编码（如 [18, 130, 241, 3, 90, 45, 32, 9]）。这个编码所能表示的样本空间量级为 K^M，是 M 个码本的笛卡尔积，这也是“乘积”量化名称的由来
  • 查询阶段
    • 将查询向量同样分割为 m个子向量。
    • 预先计算查询向量的每个子向量与对应子空间所有聚类中心的距离，得到一个 m × k的距离表
    • 对于数据库中每一个量化后的向量（其本质是一个ID列表 [id1, id2, ..., idm]），其与查询向量的近似距离可通过查表快速计算：距离 ≈ dist_table[1][id1] + dist_table[2][id2] + ... + dist_table[m][idm]。
    • 最后，返回距离最小的几个向量作为近似最近邻
• 优势：
  • 极高的压缩比：一个原始向量（如128维浮点数，占512字节）可被压缩为仅 m个字节（如 m=8，仅占8字节），内存占用可减少高达97%
  • 加速近似搜索：通过查表计算距离，避免了高维向量的直接计算，搜索速度可比暴力搜索提升数倍至数十倍
  • 可扩展性：结合倒排索引（IVF）等结构形成IVFPQ（如Faiss库中的 IndexIVFPQ），先通过倒排筛选出少量候选集，再对候选集进行PQ精细计算，能进一步极大提升搜索效率，适用于十亿级别的大规模数据集
• IVFPQ (倒排文件与乘积量化)：最常用的复合索引结构之一。先使用粗量化器（k-means）将向量空间划分为 nlist个单元（Voronoi细胞），并建立倒排列表，每个列表存储落入该单元的向量及其PQ编码。搜索时，仅计算查询向量与少数（nprobe个）最接近的单元中的向量距离，极大地缩小了搜索范围

优化乘积量化 OPQ

• 通过改进原始PQ（Product Quantization）的量化过程，降低量化误差，从而在保持高压缩比和快速检索的同时，显著提升检索准确率。
• OPQ解决的问题：
  • 维度相关性：高维向量中，不同维度之间可能存在相关性。简单的均匀分割会破坏这种内在结构，导致量化后的向量无法准确代表原始向量，产生较大的量化误差。
  • 方差不平衡：各个子向量的能量（方差）分布可能极不均衡。方差大的子空间携带更多信息，理应获得更精细的量化；而方差小的子空间信息量少，可以更粗糙地量化。但原始PQ为所有子空间分配相同的码本大小（相同的聚类中心数量 k），这会造成信息量大的子空间因量化粗糙而误差大，信息量小的子空间却浪费了量化资源
• OPQ 的核心思想就是在进行乘积量化之前，先对原始向量空间进行一个正交旋转变换，旨在解除原始维度间的相关性，并使各个子空间的能量（方差）分布更平衡，从而降低量化误差。
• 优势：
  • 更高的检索精度：与原始 PQ 相比，在相同的压缩比下，OPQ 能显著降低量化误差，获得更高的召回率和检索准确率
  • 保持压缩效率：继承了 PQ 的高压缩比特性，依然能极大减少内存占用，适合海量数据。
  • 广泛适用性：OPQ 是一种预处理技术，可以与其他索引结构（如 IVF）结合，形成 IVFOPQ 索引，进一步兼顾检索速度和精度。
• 适用场景
  • 内存敏感的高精度检索：当需要在有限的内存容量下存放十亿级甚至更多向量，并同时要求较高的检索准确率时，OPQ 是一个非常优秀的选择。
  • 检索精度要求高的业务：例如在图像检索、视频查重、推荐系统的语义匹配等业务中，OPQ 可以显著提升用户体验。
  • 与倒排系统结合：IVFOPQ 是 Faiss 等向量数据库库中一种非常强大且常用的索引类型。它先通过倒排（IVF）快速缩小搜索范围，再在候选集中使用 OPQ 进行精细排序，完美平衡了速度和精度。

图索引 HNSW

• 核心思想
  • 小世界网络：这种网络结构（类似于社交网络中的“六度分隔理论”）的特点是，大多数节点彼此并不直接相连，但任意两个节点之间都能通过很少的几步路径连接起来。这意味着既存在紧密的局部连接，也存在少量能够实现远距离跳跃的“捷径。
  • 分层导航：HNSW通过构建一个类似金字塔的多层图来模拟这种行为
    • 顶层（Layer L）：节点最少，连接是长距离的，充当“高速公路”，用于快速导航到目标的大致区域
    • 底层（Layer 0）：包含所有数据点，连接是短距离且密集的，用于在局部区域内进行精细搜索，找到最近邻。
    • 节点被随机分配到一个最高层级，且层级越高，节点出现的概率呈指数衰减（例如 P(level) ∝ 1 / base^level）。这意味着越高层越稀疏
• 搜索过程
  • 从最高层的入口点开始
  • 在当前层执行贪婪搜索：从当前节点出发，始终移动到与查询向量最相似的邻居节点，直到无法找到更近的节点（到达局部最优点）
  • 然后下降一层，以当前局部最优点作为新入口点，重复上述贪婪搜索过程
  • 如此逐层下降，直到在第0层完成精细搜索，并返回最终的最近邻结果
• 构建（插入）过程
  • 对于一个新向量，首先随机确定它所能出现的最高层级 l（层级越高概率越低）
  • 从顶层开始，逐层向下查找该向量在每一层的最近邻节点（过程与搜索类似）
  • 在每一层（从第 l层到第0层），将该新向量连接到该层中其最近的 M 个邻居节点
  • 同时，为了保持图的平衡和高效，可能会修剪已有节点的连接数，使其不超过最大限制 M_max
• 优势：
  • 极高的搜索速度：时间复杂度可达 O(log N)，比暴力搜索的 O(N) 快数个数量级，适用于毫秒级响应的实时应用
  • 高召回率：在近似算法中，HNSW通常能提供非常接近精确搜索的结果质量。
  • 灵活性：支持多种相似度度量方式，如欧氏距离（L2）、内积（IP）、余弦相似度（Cosine）
• 局限和考量：
  • 内存消耗较高：整个图结构通常需要存储在内存中以实现最佳性能，对大规模数据集来说内存开销不小。
  • 索引构建时间较长：相比于IVF等索引，HNSW的构建过程更耗时，但这是一次性的离线操作。
  • 参数调优：性能表现依赖于参数配置，需要根据具体数据和场景进行调整以达到最佳平衡
• 典型场景：
  • 推荐系统：快速为用户寻找相似的商品或内容。
  • 图像与视频检索：实现“以图搜图”或相似视频推荐。
  • 语义搜索与RAG：从海量文档中快速检索与查询语义相关的文本片段，作为大语言模型（LLM）的上下文。
  • 音频与语音识别：检索相似的音频片段。

哈希技术

• 核心思想：
  • 让相似的输入项经过哈希后，有更高的概率映射到同一个“桶”里，从而快速缩小搜索范围。

• 流程
• 构建索引
  • 选择函数族：根据具体的距离度量（如欧氏距离、余弦相似度、Jaccard系数）选择或设计合适的LSH函数族
  • 构建哈希表：通常，会使用 L个哈希函数组（每个组由 k个LSH函数构成）来创建 L张哈希表。对于一个数据点 p，在第 i张哈希表中的索引由 gi(p)=(h1(p),h2****(p),…,hk****(**p**))决定，其中 **h**1,**…**,**h**k是从 **H**中随机选取的哈希函数。具有相同 **g**i(**p**)的数据点会被放入同一个哈希桶中
  • 存储：将数据点存入相应的哈希桶，完成索引构建
• 查询
  • 计算查询哈希：给定一个查询点 q，同样计算它在 L张哈希表中对应的哈希键 g1(q),g2****(q),…,gL****(**q**)
  • 检索候选集：取出所有与 q的哈希键相匹配的桶中的数据点，这些点构成了候选集。由于LSH的性质，相似的项很可能在这些桶中。
  • 精细筛选：在候选集中进行精确的相似性计算（如线性扫描），找到真正的最近邻或近似最近邻。由于候选集远小于整个数据集，搜索效率得到极大提升。
• 优点：
  • 次线性查询时间：查询时间可远小于线性扫描，尤其适用于海量高维数据。
  • 可扩展性：算法易于并行化，适合分布式处理。
  • 灵活性：有针对不同距离度量的多种变体。
• 缺点：
  • 近似性：结果是近似的，可能存在假阴性（False Negative）和假阳性（False Positive）。
  • 参数敏感：性能高度依赖于参数（如 k, L, w）的选择，需要根据数据和查询需求进行调整。
  • 索引开销：构建哈希表和存储索引需要额外的内存空间。
• 应用：
  • 近似最近邻搜索：图像检索、视频查重、推荐系统（为用户寻找相似商品或内容）。
  • 大规模数据去重：尤其是在云存储环境中，用于消除重复数据，节省存储空间。
  • 相似文档检测：网页去重、 plagiarism 检测。
  • 聚类和异常检测：快速发现密集区域或异常点。