38.3.1 图书馆寻书指南：ANN近似最近邻

可视化演示

演示向量空间KNN搜索、HNSW分层图导航路径、以及Brute Force/HNSW/IVF三种方法的召回率-延迟权衡曲线。

问题定义

还是那座一亿册的图书馆。你手中的书，在图书馆管理员眼里对应一张“特征卡片”——上面写着主题分类号、关键词向量。所谓“最近邻”，就是找到特征卡片最接近的那几本书。管理员的朴素做法是摊开所有卡片，一张张比对，选出差距最小的。

但这里有个隐蔽的岔路：是追求“绝对最像”（精确最近邻），还是“够像就行”（近似最近邻）？一亿本书的精确比对意味着巨大的时间开销。ANN 的精髓，是用“允许一定误差”换取“速度指数级提升”——就像你想找几本和《三体》相似的书，管理员直接带你去“科幻”书架，而不是跑遍全部书库。

从工程角度看，ANN 需要回答三个问题：搜得快不快（时间开销）、搜得准不准（召回率）、存得住不爆（内存开销）。衡量“准”的经典指标是 Recall@k——看返回的 k 个结果里，和暴力搜索找出的“真·最近邻”重合了几个。

$\displaystyle \text{Recall@}k = \frac{\left| \text{ANN}_k(q) \cap \text{BruteForce}_k(q) \right|}{k}$

1. 分子——交集计数：分别用 ANN 和暴力搜索各返回 k 个最近邻结果，取两个集合的交集，数一数重合了多少个。

$$\left| \text{ANN}_k(q) \cap \text{BruteForce}_k(q) \right|$$

2. 分母——k 值归一化：除以 k，把结果归一到 0~1 之间。k 越大，偶然重合的概率越低，指标越可信。

$$\frac{1}{k}$$

3. 整体——比率：这个比值就是召回率。1.0 表示 ANN 结果与精确结果完全一致，0.5 表示只找到了一半。

$$\text{Recall@}k$$

暴力搜索

暴力搜索就是那个“一本一本翻”的笨办法。对于查询向量 q，它遍历数据库里的每一个向量 p，逐一计算距离，最后选出距离最小的 k 个。在亿万向量的工业场景下，这个办法的耗时是“每次查询都扫一遍全库”——好比每次进图书馆都要把一亿本书捧到手上一一掂量。

它的复杂度是：

$\displaystyle T(n, d) = O(n \times d)$

其中 n 是数据库中的向量总数，d 是向量维度。当 n=1000 万、d=128 时，一次查询要算 12.8 亿次浮点乘法——再快的 CPU 也扛不住。

1. n——数据量：数据库里一共多少本书（向量）。n 越大，扫描越慢，线性增长。

$$n$$

2. d——维度：每本书的特征描述长度（向量维度）。d 越大，单次距离计算越重。

$$d$$

3. n × d——总操作数：每个向量都要算一遍距离，总计 n 次距离计算，每次计算约 d 次运算。

$$n \times d$$

4. O(·)——增长趋势：大 O 记号刻画“随规模增长的趋势”。暴力搜索是线性增长，数据翻倍时间翻倍。

$$O(n \times d)$$

树索引-KD

既然全馆扫描太慢，聪明的图书管理员想到了“分类索引”。KD-Tree 的思路与之惊人相似：在每一层选一个维度把空间切成两半，像切豆腐一样——先按“类别”横切一刀，再按“作者”竖切一刀，层层细分，最终形成一棵树。

搜索时，从根节点出发，沿着查询点所在的半区快速下钻。如果某个子树区域已经不可能包含更近的点，就果断“剪枝”——整棵子树当作无关书架忽略掉。这样搜索只访问路径附近的书架，而不是全馆。

KD-Tree 在低维（d ≤ 20）空间表现优秀，但维度升高后性能急剧恶化。原因是高维空间里“豆腐块”被切得极碎，每一层的区分度都在下降，剪枝很难生效——最终退化成“几乎全馆都翻了一遍”。

它的近似复杂度为：

$\displaystyle T_{\text{search}} \approx O(\log n) \quad (\text{低维})$

1. log n——下钻层数：每次切一刀，树的高度约为 log₂n，搜索时沿单一路径下钻，访问层数近似这个量级。

$$\log n$$

2. ≈——平均情况：这是平均复杂度，KD-Tree 在高维时不再成立，因此标注“低维”限定。

$$\approx$$

3. T_search——单次查询成本：一次查询的总耗时，近似与 log n 成正比。

$$T_{\text{search}}$$

哈希-LSH

既然树的切法在高维空间失效，换个思路：给相似的东西盖上同一枚章。LSH（局部敏感哈希）的核心思想是：设计一种特殊的哈希函数，让“距离越近的向量，哈希值越容易相等”。就像把书按“主题色”盖章——红壳的书盖红章，蓝壳的盖蓝章，相似的书大概率进同一个“章桶”。

搜索时只需在查询向量所在的那个桶里找近邻，旁边的桶不用管。这个方法的妙处在于：越相似，碰撞概率越高。碰撞概率随距离单调递减：

$\displaystyle P[h(q) = h(p)] \propto e^{-\lambda \cdot \text{dist}(q,p)}$

1. h(q) = h(p)——碰撞事件：两个向量经过哈希函数 h 得到相同桶编号——即“被盖了同一枚章”。

$$h(q) = h(p)$$

2. dist(q,p)——向量距离：两者在原始空间中的距离，距离越大相似度越低。

$$\text{dist}(q,p)$$

3. e^{-λ·dist}——衰减指数：碰撞概率随距离指数级下降，符合“近的常相遇，远的难同桶”的设计目标。

$$e^{-\lambda \cdot \text{dist}(q,p)}$$

4. ∝——正比关系：比例常数由哈希函数族决定，可通过多张哈希表叠加来提高召回。

$$\propto$$

图索引-HNSW

到了这里，管理员终于用上了“社交网络”。HNSW 的灵感来自跳表（Skip List）：高层图稀疏、低层图稠密。顶层像“校长名单”——只有少数几位资深管理员；底层像“全馆员工名册”——所有人都在，彼此认识邻居。

搜索过程是一场贪心接力：从顶层随机节点出发，每次沿边走到“离查询点更近”的邻居；走到没有更近邻居时，降到下一层继续接力；直达最底层，返回当前最优。整个过程不需要全局扫描，每层只访问一小簇节点，仿佛是“先向校长打听该找谁，再向系主任确认，最后找具体馆员指路”。

HNSW 的搜索复杂度约：

$\displaystyle T_{\text{search}} \approx O(\log n)$

但这里的 log n 在高维（如 128 维）下依然成立——这正是它成为工业主流的原因。

1. 构图——多层嵌套：每层都是图，上层是下层的“缩略索引”。所有向量都出现在底层，越往上越稀疏。

$$G = G_0 \supset G_1 \supset \cdots \supset G_{\text{top}}$$

2. 贪心选择——每步最优：在当前节点的邻居中，选择距离查询点最近的未访问节点，重复直至局部最优。

$$v_{t+1} = \arg\min_{u \in \mathcal{N}(v_t)} \text{dist}(u, q)$$

3. 层下降——粗排到精排：当前层无法继续改进时，进入下一层重新执行贪心。层号降低意味着候选集从稀疏变稠密。

$$G_{t} \to G_{t+1}$$

量化-IVFPQ

最后登场的是“把书变薄”的魔法。IVF（倒排文件）先对整个数据库做聚类，把书分进多个“馆藏区”；查询时只走进最近的几个区去翻，而不是全馆跑。但区内书仍然很多，于是 PQ（乘积量化）出场：把每个向量的每一段维度压缩成“摘要卡片”上的短码，比对时只比摘要卡，不必展开全文。

这两招叠加，带来两个直接收益：搜索空间从全库缩到几区，距离计算从浮点运算变成查表操作。存储开销更是大幅下降。

$\displaystyle \text{mem}_{\text{IVFPQ}} = n \times m \times \log_2 k^* \ \text{bits}$

1. n×m——向量数乘子段数：每个向量切成 m 段，每段分别量化，总数是 n 乘以切割段数。

$$n \times m$$

2. log₂k*——每段编码位数：每段用 k* 个码本中心表示，需要 log₂k* 个比特来存索引。k* 取 256 时，即为 8 bit。

$$\log_2 k^*$$

3. mem——总内存开销：相比原始 float32（每维度 32 bit），压缩比可达几十倍——相当于书都换成了“带目录的摘要卡”。

$$\text{mem}_{\text{IVFPQ}}$$

工程实践

工业界的真实世界里，选型从不是“哪个最优”，而是“哪个够用”。Facebook 开源的 Faiss 库是 ANN 领域的“标准工具箱”，内置了上面所有算法。工程中的常见流程是：粗召回 + 精排序。先用 ANN（如 HNSW 或 IVF-PQ）从千万级库中快速捞出几百个候选，再用精确距离逐一精排——既控制了时延，又保证了精度。

| 场景 | 推荐方法 | 原因 |

|------|----------|------|

| 百万级·低维 | KD-Tree | 实现简单，低维高效 |

| 千万级·高维 | HNSW | 高维下仍保持 log 级搜索 |

| 上亿级·内存紧张 | IVF-PQ | 压缩比高，内存友好 |

| 极端大规模 | 混合方案 + 分片 | 分布式 + 多算法叠加 |

关键参数调优，每一项都像调乐器：efConstruction（建图质量）越大，图越精准但建图越慢；M（邻居数）越大，召回越高但内存越多；nprobe（扫描区数）越大，IVF 精度越高但耗时越长。在图书馆的比喻里，它们分别对应“请多少位审稿人校对目录”“每个书架留几条交叉索引”“进馆后多逛几个分馆”。

---

AI 应用场景

Python 演示

import numpy as np class HNSW:    """极简 HNSW 演示：随机图 + 贪心搜索"""    def __init__(self, dim=16, M=4):        self.dim = dim        self.M = M        self.vectors = []        self.edges = []     def add(self, vec):        idx = len(self.vectors)        self.vectors.append(vec)        self.edges.append([])        if idx == 0:            return        # 计算所有已有点的距离，取最近 M 个做邻居        dists = []        for i, v in enumerate(self.vectors[:-1]):            d = np.linalg.norm(vec - v)            dists.append((d, i))        dists.sort(key=lambda x: x[0])        for d, i in dists[:self.M]:            self.edges[idx].append(i)            self.edges[i].append(idx)     def search(self, query, k=3):        """贪心搜索：从随机起点出发，沿边走向更近邻"""        cur = np.random.randint(len(self.vectors))        visited = set([cur])        improved = True        while improved:            improved = False            for nb in self.edges[cur]:                if nb in visited:                    continue                visited.add(nb)                if np.linalg.norm(self.vectors[nb] - query) < np.linalg.norm(self.vectors[cur] - query):                    cur = nb                    improved = True        # 收集当前节点及其邻居作为候选        cands = set(self.edges[cur]) | {cur}        cands = sorted(cands, key=lambda i: np.linalg.norm(self.vectors[i] - query))        return [self.vectors[i] for i in cands[:k]] # 生成测试数据rng = np.random.default_rng(42)db = HNSW(dim=8, M=5)for _ in range(100):    db.add(rng.normal(size=8))q = rng.normal(size=8)results = db.search(q, k=3)print("查询向量:", q)print("返回结果数量:", len(results))

1. self.vectors.append(vec)存储原始向量，相当于“图书馆里的一本书的特征描述”。
2. dists.sort(key=lambda x: x[0])按距离排序，选出最近的 M 个点建边，即“结识最近的书友”。
3. self.edges[idx].append(i)双向加边，让两个节点互相成为邻居，形成无向图。
4. while improved:贪心主循环：只要还能跳到更近的邻居就继续走，一旦走到局部最优就停。
5. visited = set([cur])防重复访问的“路标”集合，避免在图里绕圈。
6. cands = set(self.edges[cur]) | {cur}最终候选集合：当前最优节点 + 其全部邻居，从中取 Top-k。

常见误区

面试题