探索向量数据库：深入理解向量搜索算法

“AI 的真正魔力不仅在于理解语言，更在于明智地记住它。”

从 Android 工程转向生成式 AI 开发。

现在，探索 LLM、RAG 和嵌入的世界时，我发现自己反复撞上一个幕后大玩家：

向量数据库

相信我，理解它们的工作原理以及我们如何在其中进行搜索，感觉就像在学习天才大脑的记忆技巧。

因此，这篇博客将全面介绍向量数据库，包括两种出色的搜索算法：ANNoy 和 HNSW，以及它们如何从更早的方法（如 Kd-Tree）演变而来，并启发了更现代的方法（如 倒排文件索引）。

让我们开始吧！

为什么不用传统数据库？

像 MySQL 或 MongoDB 这样的传统数据库最适合精确匹配和结构化查询：

• 想要 ID 为 102 的用户资料？完美。
• 需要 2022 年的所有记录？简单。

但假设你问系统：

“给我最接近这段关于量子计算的段落的文档。”

这不是精确匹配。这是语义匹配。

在这种情况下，你不需要_精确_匹配。你需要概念上的_最接近_匹配。

这就是向量嵌入和向量数据库的用武之地。

什么是向量数据库？

想象一下，将文本、图像或音频的含义压缩成一个高维数字列表，称为向量。

“量子计算是未来。” →[0.14, -0.92, ..., 0.58]

向量数据库存储这些高维向量，并允许你：

• 添加新向量
• 搜索相似向量
• 按元数据过滤

同时针对快速相似性搜索进行了优化，而不是精确查找。

相似性很重要

大多数向量数据库使用余弦相似度或欧几里得距离来确定哪些向量与查询向量“接近”。

嵌入压缩：在不丢失含义的情况下缩小规模

当存储和查询数百万（或数十亿）个向量时，存储和内存带宽很快就会成为瓶颈。为了解决这个问题，向量数据库采用压缩技术来减小嵌入的大小，同时尽量保留其语义含义。

标量量化

• 这就像降低图像质量以节省空间。
• 将高精度浮点值（如 32 位浮点数）转换为低精度整数（如 8 位或 16 位）。
• 向量中的每个元素都被缩放和量化，从而减少其内存占用。
• ⚠️ 缺点：由于粒度丢失，可能会降低准确性。

👉 用例：当空间受限且近似结果可接受时，例如移动端推理或边缘设备存储。

乘积量化 (PQ)

• 将 PQ 视为智能向量压缩。
• 将向量拆分为子向量。一个长向量（例如 128 维）被分成更小的部分（例如 4 组 32 维）。
• 每个子向量被替换为来自码本（类似于基于字典的压缩）的索引——一个使用聚类（如 k-means）学习到的预计算质心列表。
• 在保留距离属性的同时大幅减少空间。我们存储最接近质心的索引，而不是存储原始数字。

为什么有效：

• PQ 能够在压缩空间中实现快速近似最近邻 (ANN) 搜索。
• 可以在不完全解压缩的情况下估计压缩向量之间的距离。

📌 Meta 的 FAISS 大量使用 PQ 来扩展到数十亿个嵌入，从而在不突破 RAM 限制的情况下实现十亿级搜索。

现实生活类比：

• 标量量化 = 将高清电影压缩到 480p。
• 乘积量化 = 将电影分解成场景，为每个场景分配一个标签，然后仅用标签重新拼接。

那么，我们如何搜索这些巨大的空间？

暴力搜索？太慢了。

相反，我们使用近似最近邻 (ANN) 算法，如 ANNoy 和 HNSW，它们针对高维空间中的快速近似搜索进行了优化。

让我们来解开它们。

向量数据库中搜索算法的时间线

搜索技术的演变是一个平衡速度、准确性和可扩展性的故事。

K-D 树 (k-dimensional tree)

• 一种二叉树空间划分结构。
• 对于低维数据（低于 30 维）高效。
• 基于轴对齐的超平面划分空间。

可视化 K-D 树搜索过程

上图说明了 K-D 树（k 维树） 如何在 2D（或更高维）空间中组织和搜索。

左侧：树结构

• 左侧表示通过递归分割数据空间构建的层次二叉树。
• 每个节点基于一个坐标轴（X 或 Y）做出决策。例如：
  • 在第 0 层，按 X 分割
  • 在第 1 层，按 Y 分割
  • 在第 2 层，再次按 X 分割，依此类推（交替）。
• 树将空间划分为象限（如左上、右下），缩小查询点的可能位置。

右侧：空间划分

• 右侧显示了递归分割后的空间外观。
• 编号的绿色圆圈是数据点，橙色点是查询点。
• 通过树遍历，只搜索附近节点的子集，大大减少了比较次数。

发生了什么？

想象一下，你想找到与橙色点（查询点）最近的邻居：

1. 树将搜索引导到一个小的空间区域。
2. 然后，如果附近的节点可能包含更近的点，它会稍微回溯到这些节点。
3. 最终，它通过排除大部分空间区域来避免暴力搜索。

权衡总结：

• 适用于低维数据（例如 2D、3D）。
• 由于可能划分的指数增长（“维度灾难”），在高维空间中失败。
• 随着维度的增加，准确性和速度急剧下降。

➡️ 导致了 ANNoy 的诞生

ANNoy (Approximate Nearest Neighbors Oh Yeah)

🎬 想象一下：

你身处一个黑暗的迷宫（Spotify 的歌曲收藏）。你想找到一个房间（歌曲），它听起来最像你脑海中的一首歌。

ANNoy 构建多棵树，每棵树以不同的方式切割空间。

• 就像同时尝试 50 条不同的迷宫路径。
• 在查询时，它快速选择每棵树中最好的门，并聚合结果。

可视化 ANNoy：随机投影树的实际应用

在这张图中，我们可视化了 ANNoy（近似最近邻，哦耶） 如何使用随机超平面划分高维向量空间（这里我们使用 2D）。

• 黄色点代表你存储的向量，可以将其视为转化为向量的歌曲、文档或图像。
• ANNoy 首先随机选择两个向量，并在它们之间画一条线（或超平面）。
• 这将空间分成两部分，假设两侧的点分布大致均匀。
• 它递归地重复这个过程，生成多个分区，直到每个簇的大小可控（低于给定阈值）。
• 绿色区域突出显示了一个这样的簇，即决策树中的一个“叶节点”，它可能包含语义相似的向量。

现在，当查询（黑点）到来时：

• ANNoy 快速遍历这个决策树，以定位查询最可能属于的区域（簇）。
• 在该区域内执行局部搜索，以检索最近邻。

📌 为什么有效： ANNoy 不是扫描所有向量，而是快速修剪搜索空间——从而实现大规模快速、近似检索。

👶 诞生故事：

由 Spotify 开发，用于驱动音乐推荐。

🔻 局限性：

• 构建速度较慢，且在大规模下不如新算法准确。
• 不能很好地动态适应更新或流式数据。

➡️ 催生了基于层次图搜索的需求：HNSW

HNSW (Hierarchical Navigable Small World)

🎬 电影类比：

想象一下《盗梦空间》式的梦境层次：第 2 层是顶层，有宽阔的路径；第 1 层连接更紧密；第 0 层充满细节。

• 你从顶层 → 中间层 → 底层下降搜索。
• 从稀疏的高层图开始（快速搜索）。
• 在较低层细化搜索（更密集的连接）。
• 想象一下谷歌地图从世界 → 国家 → 城市缩放。

可视化 HNSW：像谷歌地图一样在层间导航

这张图很好地说明了 HNSW 算法如何通过将数据组织成多个分层图来执行快速高效的向量搜索。

• 每个蓝点是存储在数据库中的一个向量（文档、图像等）。
• 绿点是我们正在搜索的查询向量。
• 红色箭头显示了算法为定位最近向量所采取的贪婪路径。

工作原理：

1. 顶层（第 2 层）： 搜索从高层、稀疏的图开始，具有长距离连接，非常适合快速跳过不相关的区域。
2. 中间层（第 1 层）： 随着我们下降，图变得更密集，连接变得更局部，帮助我们细化搜索。
3. 底层（第 0 层）： 这是最详细的级别。算法继续在最相似的候选者中搜索，以锁定最近邻。

📌 关键见解：

就像从世界地图缩放到街景一样，HNSW 使用多分辨率图来快速找到答案——搜索时间复杂度仅为 O(log N)。

这种层次结构使 HNSW 既可扩展又准确，并使其成为 FAISS、Weaviate 和 Qdrant 等向量数据库中的宠儿。

核心思想：

• 构建一个多层图。
• 在每一层使用贪婪搜索。
• 时间复杂度 = O(log N)

为什么它强大：

• 即使在十亿级规模下也超快
• 比 ANNoy 更好的准确性和召回率
• 针对读写操作进行了优化

起源故事：

HNSW 是 ANNoy 的进化，后来被许多工具采用：

➡️ 随着数据进一步扩展，即使 HNSW 也需要提升——倒排索引登场。

倒排文件索引 (IVF)

什么是 IVF？

• 不是将查询与每个向量进行比较，而是将向量分组为簇。
• 在搜索期间，你只与最接近的几个簇进行比较。

可以这样理解：

• 将图书馆按主题（簇）划分
• 然后只搜索与查询最相关的书架（簇）

工作原理：

• 执行粗量化，将数据集划分为 k 个簇
• 每个簇（倒排列表）存储最接近该质心的向量
• 在搜索期间，只访问少数几个列表

通常与乘积量化结合使用，以实现极端规模（如 FAISS 中所见）。

可视化倒排文件索引 (IVF) 搜索

这张图展示了倒排文件索引 (IVF) 如何通过将向量空间划分为簇来工作——使大规模搜索高效且可配置。

🔵 蓝色区域：簇

• 整个空间被分割成簇，每个簇使用像 K-Means 这样的聚类算法形成。
• 每个簇（蓝色区域）有一个质心，一个代表该区域的向量（以红色显示）。

🔴 红点：质心

• 这些是每个簇的“地址”或 OID（对象 ID）。
• 在预处理期间，所有文档向量（黄点）被分配给最近的质心，使后续查找更快。

⚫ 查询：

• 当用户输入查询（大黑点）时，首先使用嵌入模型将其转换为向量。
• 然后算法检查哪个簇质心最接近查询。
• 在这种情况下，黑色查询向量最接近某个特定簇，因此只搜索该区域以找到最佳匹配。

可调节的搜索广度

• 你可以配置要搜索的簇数 (K)：
  • K = 1 → 只搜索最近的簇（更快，但准确性较低）
  • K = 8 → 搜索前 8 个簇（较慢，但召回率更高）
• 这就像决定搜索多少个街区来寻找失踪的人：从他们最可能出现的地方开始，然后扩大范围。

为什么使用 IVF？

可扩展——适用于数百万到数十亿个向量

灵活——通过 K 平衡准确性与速度

高效——避免对整个数据集进行暴力扫描

注意事项：

有时，真正最近的向量可能位于不同的簇中，因此 IVF 是近似的，并非完美。但对于大多数实际用例来说，它足够好且速度极快。

📌 IVF 广泛应用于 Meta 的 FAISS 和当今许多大规模向量搜索系统中。

为什么这让我震惊

当我第一次看到向量数据库的工作速度如此之快，能在毫秒内找到语义答案时，我意识到：

“这是机器的记忆。结构如同记忆宫殿。”

想象一下，如果钢铁侠的 JARVIS 能瞬间扫描所有对话、文件或图像，找到你需要的东西——这就是向量数据库让我们能够构建的东西。

💬 让我们一起成长

📚 资源：

• FAISS 文档
• Spotify 关于 ANNoy 的文章
• HNSW 论文

原文链接：https://medium.com/@smquasim016/exploring-vector-databases-a-deep-dive-into-vector-search-algorithms-30ce384aacaf