3、核心算法：近似最近邻搜索（ANN）—— 从暴力到智能的跨越

聊到向量数据库，最核心的引擎就是搜索算法。说白了，你存了一堆向量进去，最终目的就是要把「最相似」的那几个找出来。怎么找？这里面门道很深。我刚开始接触这个领域时，也踩过不少坑，今天就把这些经验掰开揉碎了讲给你听。

3.1 精确搜索 vs 近似搜索：鱼与熊掌

先讲最朴素的方案——精确搜索。也叫暴力搜索（Brute Force）。

它的逻辑很简单：拿你的查询向量，跟库里每一个向量算一遍距离，然后排序，取 Top-K。结果精确，一个都不会漏。我在第一个项目里就是这么干的，当时数据量才 10 万条，响应时间还能接受。

但问题来了。当数据量涨到 1000 万、1 亿时，精确搜索的耗时是线性增长的。你想想看，每次查询都要扫全库，这在生产环境里根本扛不住。我见过一个团队，上线第一天 QPS 一上来，数据库直接被打挂，就是因为用了精确搜索。

于是，近似最近邻搜索（ANN）登场了。它的核心思想很简单：用一点点精度损失，换取几十倍甚至上百倍的速度提升。说白了，我不保证每次返回的都是全局最优，但我保证返回的结果「足够好」，而且快得多。

核心权衡： 精确搜索 = 100% 召回率 + 慢速；ANN = 95%-99% 召回率 + 极速。在绝大多数推荐、检索场景里，那 1%-5% 的精度损失，用户根本感知不到。
维度 精确搜索（KNN） 近似搜索（ANN）
召回率 100% 95% ~ 99.9%
时间复杂度 O(n*d) O(log n) 或 O(1)
适用数据量 百万级以下 千万级到十亿级
典型场景 小样本验证、精确去重 实时推荐、语义搜索
我曾经踩过的坑： 有一次做离线聚类评估，我偷懒用了 ANN 去算邻居，结果聚类边界全乱了。后来才意识到，离线分析、数据校验这种场景，必须用精确搜索。ANN 只适合在线服务，别搞混了。

3.2 常用索引算法：IVF、HNSW、PQ

ANN 不是一种算法，而是一类算法的统称。目前工业界最主流的，就是下面这三种。我按自己的理解，给你拆开讲。

3.2.1 IVF（倒排文件索引）—— 先分区，再搜索

IVF 的思路很直观：把整个向量空间划分成若干个区域（也叫 Voronoi 单元），每个区域有一个中心点。查询时，先找到离查询点最近的几个区域，然后只在这些区域里做精确搜索。

我个人习惯把 IVF 比作「先找小区，再找门牌号」。你想想看，在北京找一个人，如果让你在全城搜，那得搜到什么时候？但如果你先确定他在哪个区，再在那个区里找，效率就高多了。

IVF 有两个关键参数：nlist（划分的区域数）和 nprobe（搜索时探访的区域数）。nprobe 越大，召回率越高，但速度越慢。我在项目中一般从 nprobe=10 开始调，然后根据召回率曲线往上加。

# 以 Faiss 为例，IVF 的典型用法
import faiss

dim = 128
nlist = 100  # 划分 100 个区域
quantizer = faiss.IndexFlatL2(dim)  # 用精确搜索做区域中心
index = faiss.IndexIVFFlat(quantizer, dim, nlist, faiss.METRIC_L2)

# 训练 + 添加向量
index.train(vectors)
index.add(vectors)

# 搜索时设置 nprobe
index.nprobe = 10
D, I = index.search(query, k=10)
小技巧： IVF 的训练过程需要所有数据吗？不一定。你可以采样 1% 的数据来训练聚类中心，效果差别不大。这在数据量特别大时能省不少时间。

3.2.2 HNSW（分层可导航小世界图）—— 图结构中的高速公路

HNSW 是目前公认的「召回率-速度」平衡最好的算法之一。它的底层是多层图结构：上层是稀疏的「高速公路」，下层是密集的「本地道路」。

搜索时，从顶层开始，快速跳到目标区域附近，然后逐层向下细化。这就像你从北京去上海，先坐飞机到虹桥（顶层），再换地铁到具体街道（底层）。

我记得有一次做亿级向量检索的选型，对比了 IVF 和 HNSW。在同等召回率（99%）下，HNSW 的延迟只有 IVF 的 1/3。但代价是什么？内存占用高。HNSW 需要把整个图结构存在内存里，对资源敏感的项目要慎重。

特性 IVF HNSW PQ
搜索速度 中等 极快 快
内存占用 低 高 极低
构建时间 快 慢 中等
召回率 中等 极高 中等
适合场景 大规模、磁盘索引 高并发、低延迟 内存受限、超大规模

3.2.3 PQ（乘积量化）—— 压缩的艺术

PQ 的思路完全不同。它不改变搜索结构，而是改变向量的存储方式。简单说，就是把一个高维向量切成若干段，每段用一个码本（codebook）来量化。最终，一个 128 维的向量，可能只存 8 个字节。

这带来的好处是：内存占用大幅下降。我做过一个实验，用 PQ 把 10 亿条 128 维向量的索引，从 500GB 压缩到了 20GB。代价是什么？精度损失。因为量化本身是有损的。

实际项目中，我经常把 PQ 和 IVF 组合使用，也就是 IVF-PQ。先用 IVF 做粗粒度分区，再用 PQ 做细粒度压缩。这是目前大规模向量检索的黄金组合。

# IVF + PQ 组合索引
m = 16  # 将 128 维切为 16 段，每段 8 维
nbits = 8  # 每段用 8 bit 量化
index = faiss.IndexIVFPQ(quantizer, dim, nlist, m, nbits)

# 训练和搜索流程不变
index.train(vectors)
index.add(vectors)
D, I = index.search(query, k=10)
注意： PQ 的码本训练需要足够的数据。如果训练集太小，码本会过拟合，导致搜索精度大幅下降。我建议训练集至少要有 10 万条以上。

3.3 距离度量：余弦、欧式、点积——选错了全白搭

算法选对了，度量选错了，结果一样糟糕。这三种距离度量，各有各的脾气。

  • 余弦距离（Cosine Similarity）：只看方向，不看长度。适合文本、语义搜索。比如两句话「我喜欢猫」和「我讨厌猫」，长度差不多，但方向相反，余弦距离能很好地捕捉这种语义对立。
  • 欧式距离（L2）：看距离。适合图像、音频特征。因为这些特征的模长本身就有意义。
  • 点积（Dot Product）：既看方向又看长度。适合推荐系统里的协同过滤、矩阵分解场景。

我见过最典型的错误是：有人用 BERT 做文本向量化，然后拿欧式距离去算相似度。结果呢？两个语义完全不同的句子，因为向量模长相近，被判定为相似。这就是度量选错了。

我的经验法则：
  • 如果向量做过 L2 归一化（模长为 1），那么余弦距离 = 点积，选哪个都一样。
  • 如果没做归一化，文本类用余弦，视觉类用欧式，推荐类用点积。
  • 实在拿不准，就在验证集上跑一下，看哪个度量的 Recall@K 最高。

3.4 核心算法知识图谱

下面这张图，是我自己梳理的 ANN 算法选型决策流。你可以把它当作一个快速参考。

ANN 算法选型决策流 ANN 算法选型决策流 查询向量 数据量 < 100 万？ 精确搜索 (KNN) 近似搜索 (ANN) 内存充足？ HNSW IVF + PQ 选型建议 高并发低延迟 → HNSW | 超大规模内存受限 → IVF+PQ | 小数据量 → 精确搜索

3.5 实战选型建议

说了这么多，到底怎么选？我总结了一个简单的决策流程：

  1. 先看数据量：100 万以下，直接用精确搜索，别折腾。
  2. 再看延迟要求：要求 10ms 以内，优先考虑 HNSW。
  3. 再看内存预算：内存紧张，用 IVF+PQ 组合。
  4. 最后看召回率：如果要求 99% 以上，HNSW 是唯一选择。
我的个人习惯： 做原型验证时，先用 IVF 跑通流程，因为它的参数少、调起来快。等业务稳定了，再根据实际 QPS 和延迟要求，决定要不要切到 HNSW。别一上来就上最复杂的方案，容易把自己绕进去。

嗯，核心算法这块就讲到这里。记住一句话：没有最好的算法，只有最合适的算法。选型的关键，是搞清楚你的业务到底要什么。

← 上一章 📖 返回目录 下一章 →