向量数据库内部机制：IVF、树结构、HNSW与乘积量化

RAG、向量数据库、检索与分块之类的术语被频繁提及，但实际听起来比它们本身更复杂。本文将从向量数据库讲起：它们存储什么，以及其中的搜索机制究竟是如何运作的。

向量的来源

在海量文本集上训练得到的嵌入模型，能够将句子的含义转化为一组数字。有些嵌入模型是托管在服务端的，比如OpenAI的文本嵌入模型和Google的Gemini嵌入模型；还有一些则在本地运行，例如规模为8B、4B和0.6B的Qwen3嵌入系列，或是参数量约为677M的Jina v5 text-small模型。将文本输入这些模型后，就能得到可以存储并日后调用的向量。

词汇表

每个向量数据库中都会出现一些常见的术语：

• 集合。一个命名空间，用于存储具有相同固定维度及相同距离度量的点。
• 点。一个向量，连同其标识符以及元数据载荷。
• 距离度量。衡量接近程度的方法，通常是余弦相似度、点积或欧几里得距离。
• 插入或更新。用于添加数据、插入新点并更新现有点的操作。
• 搜索。其他所有功能存在的目的，即用于执行查询的操作。

直观理解：精确匹配与近似匹配

在10,000个或更多向量中查找与查询相关的向量的简单方法，是计算每个存储向量的余弦相似度，然后保留相似度最高的k个向量。这样得到的就是最接近的邻居集合。然而，当向量数量达到数百万时，这种暴力扫描方式会因内存和时间限制而不再实用。因此，系统转而采用近似最近邻（ANN）搜索，通过牺牲一定的精度来换取显著的速度提升。

这种权衡可以通过两种主要方式实现。索引技术可以减少所需的比较次数，而量化技术则能降低每次比较的成本。二者共同构成了ANN搜索的工具箱。

索引技术，第一种方案：IVF聚类

倒排文件索引（IVF）将向量划分为多个簇，每个簇都有一个质心。查询首先仅与这些质心进行比较。找到最近的簇后，查询才会与该簇中的向量进行比较，最终返回最优的k个结果。

其缺点值得了解：

• 位于单元格边界附近的相似项会被忽略。如果真实匹配项位于未被检查的单元格中，就永远无法被发现。虽然检查更多单元格有助于找到匹配项，但会降低搜索速度并违背该方法的初衷。
• 数据变化会导致质量下降。由于簇在构建时是固定的，新数据会不断进入旧的单元格中，从而导致搜索质量逐渐降低。因此需要定期重新构建索引。

不均匀的聚类会导致速度难以预测。有些节点会变得非常大，而另一些则保持很小，因此落在大型节点上的查询速度会很慢，而落在小型节点上的查询则很快。

需要预先准备训练数据。在拥有足够的数据形成有意义的聚类之前无法构建索引，这对于从零开始的应用来说很不方便。

有两个参数难以调整。聚类数量以及每次查询要搜索的节点数量都会影响查询结果，错误的数值会导致搜索速度变慢或结果不准确。

高维度会使聚类变得模糊。当向量长度过长时，聚类会变得模糊不清，从而导致单位工作量的查询精度低于HNSW。

简而言之：IVF方法简单且节省内存，但在边界附近精度会下降，且不耐频繁更新，正因如此，在与产品量化技术结合使用时，它在处理数十亿级数据时表现优异；而HNSW则更适用于需要实时高精度搜索的场景。

第二种索引方式：基于树的分区

基于树的索引借鉴了二分搜索的思路。它不会将查询与每个向量进行比较，而是不断将空间对半划分，仅检查包含查询的那半部分空间。

要构建索引，需将整个空间用一条分割线一分为二，然后再将每一半继续分割，如此反复，直到每个小区域仅包含少量向量。每个区域即为叶节点。在二维空间中，第一次分割可能沿x轴进行，下一次沿y轴进行，依此类推。所有这些分割共同构成一棵二叉树，其中的每个节点都是一个“是”或“否”的问题，例如x是否小于5，而叶节点则位于树的底部。

当有查询到来时，从根节点开始，一次回答一个问题：位于该分割线的左侧还是右侧？每个答案都会排除剩余空间的一半。经过大约log n次问题询问——对于一百万个向量来说大约需要20次——最终会到达某个小叶节点，然后将查询与该节点内的少量向量进行比对。

不过有个问题。真正的最近邻可能就在分界线另一侧，距离很近但属于另一个子树，单棵树永远无法发现它。因此像 Spotify 的 Annoy 这样的库会构建多棵树，每棵树都有不同的随机分割方式。每棵树都会提出候选节点，这些候选节点会被合并，最终选出最优的。有一棵树忽略的节点，通常会有另一棵树发现。

缺点如下：

• 边界问题比 IVF 更严重。在 IVF 中，错过边界只需再检查一个单元格；而在树结构中，靠近顶部的错误选择会导致搜索进入完全不同的区域。
• 解决方案会消耗内存和速度。使用 50 棵树的森林意味着每次查询都需要存储 50 次索引并执行 50 次搜索，从而以资源代价换取更高的准确性。

长向量能使其失效。树结构在二维、三维、地图及游戏场景中表现良好。现代嵌入向量的维度高达数百甚至数千，此时单条分割线几乎无法有效区分数据，因为两侧的点往往距离相近。这正是该方法在嵌入搜索领域逐渐被淘汰的主要原因。

索引是静态的。树结构是根据现有数据一次性构建的，无法轻松接纳新的向量。例如Annoy在添加数据时需要彻底重建，这极不适用于需要频繁更新数据的场景。

它通常不如其他方法。在精度相当的情况下，HNSW的运行速度更快；在内存占用相同的情况下，结合乘积量化的IVF方法能处理更多数据。树结构目前主要仍用于传统系统以及那些需要小型、可映射到内存的索引文件的场景中。

简而言之，树结构简单且构建快速，但高维嵌入会破坏其分割结构，且无法进行更新，因此目前它们主要用于解释性目的，而非实际应用选择。

索引方法三：HNSW

分层可导航小世界算法，即HNSW，是大多数向量数据库所采用的技术。它将向量组织成具有多层的图结构。最上层仅包含少量向量及长距离连接，类似于城市间的高速公路；而较低层则逐渐包含更多向量及较短距离的连接，直至最底层包含所有向量。

搜索从顶层开始，会贪婪地朝向与查询最接近的节点移动。当没有更近的节点时，它会下降一层，从该位置重新开始搜索，此时使用的链接粒度更细。在最底层，它会探索更广阔的邻域范围，最终返回最佳匹配结果。长距离跳跃能快速覆盖较大范围，而短距离跳跃则有助于优化结果，正因如此，即便面对海量数据集，比较次数也能保持在较低水平。

有几个参数可以控制速度与精度之间的平衡：

• M决定了每个向量保留的链接数量。更多的链接可以提高精度和召回率，但会占用更多内存。
• efConstruction则控制构建图时候选搜索的范围大小。数值越大，生成的图质量越高，但构建速度越慢。

efSearch决定了查询时候选列表的宽度。提高该值会同时提升准确率与延迟。

了解查询是如何逐层处理的，以及这些设置如何影响处理路径，就能明白调整它们会如何改变搜索行为。

量化：降低每次比较的成本

索引技术可以减少比较的次数；而量化则能降低每次比较的成本。一个由32位浮点数构成的1536维向量需要1536乘以4，即6144字节的空间。对于十亿个向量而言，这将占用数TB的存储空间，远远超过RAM的容量。

乘积量化

产品量化会将每个大型向量拆分成大小相等的较小片段。一个16维的向量可能会被拆分为四个4维的片段。对于每个片段位置，都会基于存储的数据训练一个包含256个条目的码本，每个条目代表一个典型的子向量。随后每个片段都会被替换为其最接近的码本条目对应的数字，而这只需要1个字节。

因此，原本需要数千字节的向量会变成一串由小整数构成的短字符串。在搜索时，查询也会以相同方式被拆分，只需计算一次与码本条目的距离，之后在查找每个存储向量时即可重复使用该距离值。虽然这种计算方式较为近似，但能显著提升速度并节省内存。

如何选择

简单的对比就能概括各种方法的优劣：

• IVF方法简单且易于记忆，若处理非常大的静态数据集，可将其与产品量化技术结合使用。
• 树结构易于理解且构建成本较低，但仅适用于低维度且不变的数据。
• HNSW能够实现高精度和快速的实时搜索，但需要更多的内存。
• 产品量化可压缩向量并加快距离计算速度，同时会有可控的精度损失，可与其他索引技术结合使用。

了解这些权衡关系有助于你判断何时适合使用近似搜索、哪种算法适合特定工作负载，以及何时仍应采用暴力搜索方法，比如在数据量较小且对精确度要求不高的情况下。