4、精确检索与暴力搜索：全量遍历算法、时间复杂度分析、适用场景与局限性
说到向量检索，很多人第一反应就是“快”。但有个问题绕不开——你到底要不要100%精确的结果？
如果你要的是“一个都不能少”，那不好意思，你得回到最原始的方法：暴力搜索。也叫全量遍历，或者英文里常说的 Brute-Force Search。
我刚开始接触向量检索时，也觉得这玩意儿太笨了。但后来在某个金融风控项目里，客户要求召回率必须100%，少一个向量都不行。嗯，那时候我才意识到，暴力搜索虽然“笨”，但它是所有近似方法的基准线，也是你理解其他算法的起点。
什么是全量遍历？
说白了，就是拿着你的查询向量，跟数据库里每一个向量挨个算距离。
假设你有100万个向量，每个向量是128维。查询时，系统会计算100万次余弦相似度或欧氏距离，然后挑出距离最近的K个。
没有任何捷径，没有任何索引结构。就是硬算。
核心特征：
- 结果100%精确，没有近似误差
- 实现极其简单，几乎不需要预处理
- 查询时间与数据量成正比增长
时间复杂度分析
我们来拆一下这个复杂度。你想想看，一次暴力搜索到底要花多少时间？
假设：
- 数据集有 N 个向量
- 每个向量的维度是 d
- 距离计算（比如欧氏距离）需要 O(d) 次浮点运算
那么一次查询的时间复杂度就是：
O(N × d)什么意思？就是数据量翻倍，查询时间也翻倍。维度翻倍，查询时间也翻倍。
我给大家列个表，直观感受一下：
| 数据量 N | 维度 d | 单次查询耗时（估算） | 每秒可处理查询数（QPS） |
|---|---|---|---|
| 1万 | 128 | ~1ms | ~1000 |
| 10万 | 128 | ~10ms | ~100 |
| 100万 | 128 | ~100ms | ~10 |
| 1000万 | 128 | ~1s | ~1 |
| 1亿 | 128 | ~10s | ~0.1 |
看到没？数据量到千万级别，单次查询就要1秒。到亿级，10秒起步。这在很多在线场景里根本没法用。
我的经验： 我曾经在一个推荐系统项目里，初期用暴力搜索做离线评估。数据量只有50万，跑一次全量召回大概50ms，勉强能接受。但上线后用户量暴涨，数据很快到了500万，查询时间直接飙到500ms+。用户反馈“刷不动了”，我们才紧急切了近似检索。
适用场景
暴力搜索虽然慢，但并不是一无是处。我总结了几类它仍然适用的场景：
- 小数据集（N < 1万）
数据量小的时候，暴力搜索反而最简单直接。不需要建索引，不需要调参，代码写出来就能跑。 - 离线批量处理
比如离线聚类、数据清洗、批量标注。这些场景对延迟不敏感，但要求结果精确。 - 作为基准测试
评估近似检索算法的召回率时，暴力搜索的结果就是“标准答案”。没有它，你没法知道近似算法到底丢了多少精度。 - 低QPS场景
如果每秒只有几次查询，用户也能接受几百毫秒的等待，那暴力搜索完全够用。
局限性
局限性其实很明显，我直接列出来：
- 无法扩展到大数据集——N 到百万级，延迟就不可接受了
- 高维度下计算开销大——d 到几百甚至上千，每次距离计算都很重
- 没有增量更新优势——每次新增向量，查询时仍然要全量遍历
- 内存占用高——所有向量必须常驻内存，否则磁盘IO更慢
我曾经踩过的坑： 有一次我图省事，直接用暴力搜索处理了200万条128维的向量。结果单次查询要200ms，QPS只有5。上线后用户一多，服务直接被打挂。后来我才意识到，暴力搜索的瓶颈不只是CPU，还有内存带宽——每次查询都要把整个向量矩阵扫一遍，对缓存非常不友好。
暴力搜索的流程图
下面这张图展示了暴力搜索的完整流程。你可以看到，整个过程没有任何剪枝或跳过，就是一条路走到黑。
代码示例：暴力搜索的简单实现
下面是一个用 Python + NumPy 实现的暴力搜索。代码很简单，但你可以用它来验证其他近似算法的召回率。
import numpy as np
def brute_force_search(query, vectors, k=10, metric='cosine'):
"""
暴力搜索：全量遍历，返回最相似的 k 个向量索引和距离
参数:
query: 查询向量，shape (d,)
vectors: 所有向量，shape (N, d)
k: 返回 top-k 结果
metric: 距离度量，'cosine' 或 'euclidean'
返回:
indices: 最相似向量的索引，shape (k,)
distances: 对应的距离，shape (k,)
"""
N = vectors.shape[0]
if metric == 'cosine':
# 余弦相似度 -> 距离 = 1 - 相似度
norms = np.linalg.norm(vectors, axis=1)
query_norm = np.linalg.norm(query)
similarities = np.dot(vectors, query) / (norms * query_norm + 1e-10)
distances = 1.0 - similarities
elif metric == 'euclidean':
# 欧氏距离
diff = vectors - query
distances = np.sqrt(np.sum(diff ** 2, axis=1))
else:
raise ValueError(f"Unknown metric: {metric}")
# 按距离升序排序，取前 k 个
sorted_indices = np.argsort(distances)
indices = sorted_indices[:k]
distances = distances[indices]
return indices, distances
# 示例用法
if __name__ == "__main__":
# 生成 10000 个 128 维向量
N, d = 10000, 128
vectors = np.random.randn(N, d).astype(np.float32)
query = np.random.randn(d).astype(np.float32)
# 暴力搜索 top-10
indices, distances = brute_force_search(query, vectors, k=10)
print("Top-10 索引:", indices)
print("对应距离:", distances)
我个人的习惯： 在开发近似检索算法时，我会先用暴力搜索跑一遍小数据集，把结果存下来作为“黄金标准”。然后每次调参或改算法，都用这个标准来验证召回率。这样能快速发现 bug 或参数问题，避免在错误的方向上越走越远。
什么时候该放弃暴力搜索？
我给大家一个简单的判断标准：
- 如果 N > 10万 且 延迟要求 < 100ms，暴力搜索基本没戏
- 如果 N > 100万 且 延迟要求 < 1s，暴力搜索也扛不住
- 如果 N > 1000万，不管什么延迟要求，暴力搜索都不现实
这时候，你就得考虑近似检索了。比如 HNSW、IVF、PQ 这些算法。它们会在精度和延迟之间做权衡，但能让你在毫秒级完成亿级数据的检索。
不过，那是后面章节的内容了。这一章你只要记住：暴力搜索是所有近似算法的基准线，理解它的局限，你才能更好地理解为什么需要那些“花里胡哨”的索引结构。