3.1 精确搜索与近似搜索

3.1 精确搜索与近似搜索

要从"逐点比较"走向"跳跃导航"，得先看清前者到底贵在哪里。本节是第三章的开篇：承接第二章的度量知识，把暴力检索的复杂度账算清楚，用计时实验让复杂度墙可见，然后给出近似检索的核心契约——召回率。后面两节的所有算法，都是对这一节最后一行输出里的那堵墙的回应。

暴力检索的账

精确近邻搜索的流程朴素到不需要解释：查询向量和库里每个向量算一次距离，取最小的 K 个。它的成本也好算——n 个向量、每个 d 维，就是 n 次距离计算、每次 d 次乘加，复杂度记作 n 乘 d 的量级，且每次查询都要重付全款，索引的缺席意味着结果精确，也意味着成本没有下限。

乘法之外还有一层常被低估的成本：内存带宽。现代 CPU 算距离极快，真正喂不饱的是数据搬运——每个查询要把 n×d×4 字节的向量数据从内存搬进缓存。单精度浮点下一百万条 768 维向量约 2.9 GB，每次全量扫描意味着约 3 GB 的搬运；每秒一百次查询就是每秒近三百 GB 的带宽需求，已经不是一台通用服务器能从容供给的量级。这就是为什么向量检索的优化史，一半是计算史，另一半是内存史。

用实验看见这堵墙

空谈复杂度不如亲手计时。下面的实验固定维度，把规模从十万加到四十万，量一次全量扫描的真实延迟：

import numpy as np, time

rng = np.random.default_rng(7)

def flat_search(db, qs, k=10):
    # 全量算距离：矩阵乘法交给底层优化，这已经是暴力检索的极限速度
    dists = qs @ db.T                      # 归一化向量，内积即相似度
    idx = np.argpartition(-dists, k, axis=1)[:, :k]
    return idx

for n in [100_000, 200_000, 400_000]:
    db = rng.normal(size=(n, 128)).astype(np.float32)
    db /= np.linalg.norm(db, axis=1, keepdims=True)
    qs = db[:64].copy()                    # 用库里向量当查询，纯测扫描速度
    t0 = time.perf_counter()
    flat_search(db, qs)
    dt = (time.perf_counter() - t0) / len(qs)
    print(f"规模 {n:>8}  单条查询 {dt*1000:6.1f} ms")
​

在普通服务器上你会看到延迟随规模线性爬升：十万余条尚在毫秒级，四十万条已经翻了两番还多。把这个斜率外推到一千万条，单次扫描就要上百毫秒——还没算并发争抢。维度方向同样残酷：维度翻倍，搬运量与计算量同步翻倍。这组数字解释了两个工程事实：其一，十万余条以内很多业务确实不需要任何近似索引，平面结构又准又简单；其二，规模一旦过线，唯一出路是让每次查询只碰数据的一小部分——这正是"索引"两个字的全部含义。

近似的契约：召回率

近似检索的定义由此浮现：只检查库里的一部分候选，用可控的漏检换数量级的加速。既然会漏检，就需要一把尺子度量"错了多少"。召回率的定义在 1.1 出现过，这里给出严格口径：对同一批查询，分别跑精确算法与近似算法取 TopK，召回率等于两边结果的交集大小除以 K。实践中常用的是取多组查询求平均，并把 K 定为业务真实的返回条数——TopK 取值不同召回率不可比。

与召回率绑在一起交易的是延迟和内存，三者构成整个领域的基本盘。值得警惕的是它们不可兼得：想多召回就多探测，延迟随之上涨；想省内存就多压缩，召回随之受损。第三章剩下的全部内容、第五章的调优体系，本质上都是在这三个变量之间找业务可接受的解。

精确与近似的分界怎么划

分界不是绝对的，但"先量基线再决定"永远成立：先跑一遍全量扫描的真实延迟，再决定要不要为它引入索引复杂度。反过来的教训更常见——小规模业务上了重型索引，换来了运维负担却没换来延迟收益。近似的另一个隐性收益常被忽略：平面基线同时就是召回率评估的参照答案，保留一条精确检索的通道（哪怕是旁路小库），第五章的调优会省很多力气。

维度灾难的直觉版解释

实验之外，给维度灾难一个不依赖公式的直觉。想象在一维数轴上找"离你最近的点"：只要检查左右两个方向的近邻，很容易剪枝。维度升到二维，方向变成平面上的全方位；三维再变成立体。维度上百时，空间里的"方向"多到爆炸，任何一个候选点都可能与查询点在某一维上接近、在另一维上疏远——结果是所有点到查询点的距离都长得差不多，"最近"和"次近"的差距被稀释，靠距离差异剪枝的手段集体失效。这就是为什么树形索引在高维退化成全扫：不是树建错了，是"距离差异"这个信号本身在高维里衰弱了。

这个直觉还解释了一个实战现象：同样是百万级数据，128 维的检索比 32 维的慢得多，差距远超数据体积的比例——因为 32 维时索引剪枝依然锋利，128 维时每剪一刀只能淘汰少量候选。所以降维（无论是选低维模型还是做降维投影）本质上是在恢复剪枝信号的强度，这是它与"压缩省内存"完全不同的另一重价值。

问题：硬件越来越快，暴力检索会不会重新可用？

局部会，整体不会。硬件进步（更快指令集、更大内存带宽、GPU 批量算力）确实把精确扫描的可用规模线往上推了——十多年前百万级就要上索引，如今两三百万级全扫在单机上也能做到十毫秒级。但规模线之外，业务数据量的增长曲线同样在陡峭化，且并发放大需求；更关键的是延迟预算在收紧而不是放宽——用户体验对检索环节的容忍度普遍在数十毫秒，规模线追不上预算线。务实的结论是：把"精确扫描可用"的边界当作用硬件换简单性的机会窗口，能用简单方案时别急着复杂化，但别指望它一劳永逸。

本节要点回顾

• 暴力检索复杂度是规模乘维度，且内存带宽往往先于计算成为瓶颈。
• 十万余条以内平面结构完全够用，规模过线就必须引入索引。
• 近似检索用受控漏检换数量级加速，召回率是度量的尺子。
• 召回率、延迟、内存三者不可兼得，是全领域的基本盘。
• 上索引前先量精确基线，它既是决策依据也是日后的评估参照。

墙已经看清。下一节进入算法版图：三种技术路线怎么各自把"全量扫描"变成"只碰一小块"。