# ch18 向量检索系统 — 代码示例 本目录对应教材第 18 章，按正文六节组织：ANN 成本直觉、树结构（KD / 球树 / 随机投影树）、局部敏感哈希（MinHash / SimHash / Banding）、乘积量化（PQ / IVFADC）、HNSW、工具选型与索引生命周期。共 **12 个可运行脚本**加 1 个公共模块。 - 只依赖 **NumPy**，不需要 faiss / sklearn——这些算法本身就是几十行能讲清的东西，用库反而看不到细节； - 合成数据由 `common.py` 统一生成（簇状高斯混合，固定 `np.random.default_rng(2026)`），所有脚本可复现； - 全部脚本均以「暴力精确检索」为 Ground Truth 计算 Recall@10，而不是拿另一份近似结果做基准。 --- ## 目录结构 ``` code/ ├── common.py 公共：簇状向量生成、批量平方距离、暴力 Top-K、Recall、计时 ├── ch01_ann_basics/ §18.1 ANN 概述 │ └── ann_cost.py 算力/存储账、扫描比例 vs 召回、复杂度对照 ├── ch02_tree_based/ §18.2 基于树结构的 ANN │ ├── kd_tree.py §18.2.1 建树、超矩形剪枝、维度灾难 │ ├── ball_tree.py §18.2.2 超球合并（含正文公式勘误）、三角不等式下界 │ └── rp_tree.py §18.2.3 随机方向划分、Annoy 式多树 + Best-First ├── ch03_lsh/ §18.3 局部敏感哈希 │ ├── minhash.py §18.3.1 排列哈希 / 线性哈希、方差 J(1−J)/L │ ├── simhash.py §18.3.2 随机超平面、谷歌 64 位指纹、k+1 块倒排 │ └── lsh_banding.py §18.3.3 碰撞概率 1−(1−tʳ)ᵇ、S 型曲线、候选集实测 ├── ch04_pq/ §18.4 乘积量化 │ ├── product_quantization.py §18.4.1–§18.4.2 子空间分解、码本、SDC vs ADC │ └── ivfadc.py §18.4.3 倒排 + 残差 PQ、n_probe / n_list 扫描 ├── ch05_hnsw/ §18.5 HNSW │ └── hnsw.py 层数采样、构图、efSearch / M / efC、选边启发式 └── ch06_tools_and_architecture/ §18.6–§18.7 工具与系统 ├── tool_matrix.py §18.6 加权打分选型（分数全为 [MOCK]） └── index_lifecycle.py §18.7 索引缺失、双缓冲切换与切换前校验 ``` 正文 §18.4.4「Faiss 中的 PQ 实现」与 §18.5.4「Faiss 中的 HNSW 实现」是工程接口说明（`train/add/search` 三阶段），没有对应算法可复现，相关说明分别写在 `product_quantization.py` 的 ④ 与 `hnsw.py` 的结尾注释里，不单独成脚本。 --- ## 快速运行 ```bash # 仅需 Python 3.12 + NumPy python3 ch01_ann_basics/ann_cost.py python3 ch02_tree_based/kd_tree.py # 约 3 秒 python3 ch02_tree_based/ball_tree.py # 约 1 秒 python3 ch02_tree_based/rp_tree.py # 约 18 秒 python3 ch03_lsh/minhash.py # 约 4 秒 python3 ch03_lsh/simhash.py # 约 19 秒 python3 ch03_lsh/lsh_banding.py # 约 21 秒 python3 ch04_pq/product_quantization.py # 约 24 秒 python3 ch04_pq/ivfadc.py # 约 80 秒 python3 ch05_hnsw/hnsw.py # 约 2 分 20 秒（构图最重） python3 ch06_tools_and_architecture/tool_matrix.py # 瞬时 python3 ch06_tools_and_architecture/index_lifecycle.py # 约 53 秒 ``` 全部 12 个脚本 exit 0，总耗时约 5 分钟。 --- ## 公共数据口径 `make_vectors(n=2000, dim=16, n_clusters=20)` 生成「20 个簇心 + 簇内高斯噪声」的向量库；查询向量由库内随机点加小扰动得到（`jitter=0.15`），保证每个查询在库里确实有语义近邻。`knn_exact` 用 `‖q‖²+‖x‖²−2qᵀx` 展开批量算距离，避免构造 `[Q,N,D]` 张量。 需要特别说明：**不同脚本用的库规模与维度不同**，因为它们各自要复现的现象对数据形状敏感。树结构与 LSH 用 2000 条小库（要跑得动、看得清），PQ 用 6000×128（压缩率才有意义），IVFADC 用 20000×64，HNSW 用 6000×64 的近均匀分布。下文每个数字都标了对应规模，不要跨脚本横向比较绝对值。 --- ## 各脚本要点与实测 ### §18.1 ANN 成本直觉（`ann_cost.py`） 10⁹ 条 128 维向量，单次查询 `N×d = 1.3×10¹¹` FLOPs；按平方距离展开约 `3.8×10¹¹`，10 GFLOP/s 单核下要 **12.8 秒**，32 核也要 400 ms。本机 NumPy 暴力检索 20,000×128 实测 200 个查询耗时 **33.3 ms**（≈6,001 QPS、单查询 167 µs），外推到 10⁹ 条是 8.3 秒/查询——与毫秒级 SLA 差三个数量级以上。存储账：10⁹ 条 float32 正好 512 GB，PQ m=8、K=256 压到 8 GB。扫描比例实验：随机扫 1% 的库，Recall@100 只有 **0.011**，线性掉——ANN 的全部价值在于用结构找出「该扫的那 1%」。 ### §18.2 树结构 **KD 树**（2000 条 8 维簇状、叶子桶 8）：Recall@10 = 1.0000，平均访问 174 个点（8.7%）。维度灾难在均匀数据上非常陡：D=2/4/8/16/32 的访问占比为 2.2%/6.6%/27.8%/**94.9%**/100%。同样的库换成 16 簇数据，D=32 时只访问 14.1%——起作用的是**内在维度**，不是名义维度。正文说的「D<20 才适用」在这组数字上很准确。 **球树**：按正文七点重建，内部球心 `(43.46, 51.92) r=61.31`，4 个叶球、3 个内部球。正文的 (7,3) 例子：超矩形下界 `d_kd = 3.00`，超球下界 `d_ball = 4.610 − 2.5 = 2.11`——**KD 这一侧反而更紧**，球树的优势在「每节点只需一次球心距离、支持任意三角不等式度量」，不在下界大小。2000 条 8 维簇状数据上球树访问 **488 点（24.4%）**、KD 只访问 174 点（8.7%）：叶球半径被离群点撑大、父球一合并重叠更多。维度扫描同样退化，D=16 时 99.9%、D=32 起 100%——**上表比 KD 还差**，「球树更好」的说法在这组数据上不成立。 **随机投影树**：δ 系数 0/0.5/1/3/6/12 对应叶节点 256/366/361/361/361/361、退化划分 0.0%→1.1%——**不扰动反而最平衡**（中位数划分天然 50/50），δ 的理论作用是保证坏分裂概率小，不是提升平衡性。精确 RP-Tree 在均匀立方体上访问占比反而高于 KD（D=8 时 64.5% vs 29.6%）。在「沿随机方向张成的低维流形」上才有优势，但换成坐标轴子空间（64/4）又反转为 92.2% vs 14.7%。Annoy 式多树：M=1/2/4/8 → Recall 0.675/0.838/0.943/0.994，候选数 35/55/79/101；`search_k` 从 16 扫到 2000 时召回 0.513→1.000，耗时 92 µs→1369 µs。 ### §18.3 局部敏感哈希 **MinHash**：L=1024 时 6 组集合对的实测标准差 0.0115–0.0136，理论 `√(J(1−J)/L)` 0.0122–0.0136，比值 0.94–1.03——**碰撞概率 = Jaccard 是无偏的**，误差只来自抽样。工业上用线性哈希：universe 10⁶、L=128 时，随机排列要 **512 MB** 索引内存、153 µs/次签名；线性哈希 **2 KB**、33 µs/次。 **SimHash**：θ/π 从 0 到 1 扫 7 档，实测 P(同侧) 1.0000/0.8330/0.6743/0.5101/0.3391/0.1726/0.0000，与 `1−θ/π` 逐行吻合；谷歌版与显式随机超平面的逐位一致率 **1.0000**、最大绝对差 0——正文的等价性推导是恒等式。k+1 块倒排：20 万条 64 位指纹，暴力扫描 9.2–10.6 ms，查表 + 重排 0.03–0.13 ms（**约 80–300 倍**）。反例表验证鸽笼原理：只有 `m ≥ k+1` 时召回为 1.000，`m ≤ k` 全为 0。 **LSH Banding**：`P(t)=1−(1−tʳ)ᵇ` 用 2000 对 × n=256 位的实测值逐行落在公式的 ±0.01 内。2000 个集合、40 簇（同簇 J≈0.47）、Top-10：(r,b)=(2,256)/(4,128)/(8,64)/(16,32) 的 Recall 为 0.698/0.698/**0.262**/**0.000**，候选数 61/50/8/0——`r=8` 时理论碰撞率只剩 0.14，Banding 成了瓶颈。固定 r=2、L 从 64 加到 1024，候选数几乎不变（50→62），召回 0.450→0.760，**瓶颈转移到签名排序的分辨率**。对照：随机抽同样数量候选 Recall 只有 0.026–0.386，同桶候选能到 0.70。 ### §18.4 乘积量化 **PQ**（6000×128，m=8，K=256）：原始 512 B → 编码 8 B（**64×**），子码本 0.13 MB，训练 2.2 s，重建相对能量误差 3.8%。m=4/8/16/32：压缩 128×/64×/32×/16×，相对误差 4.1%/3.8%/3.2%/2.1%，ADC Recall 0.248/0.272/0.337/0.432。**SDC vs ADC**：距离误差比 ADC/SDC 为 0.48/0.42/0.74，Recall 0.226 vs **0.272**，耗时 0.87 vs 0.62 ms。ADC 全库扫描 48,000 次查表、0.23 ms，同一规模下 NumPy 暴力 L2 只要 0.14 ms——**O(mN) < O(DN) 的复杂度结论正确，但常数因子由实现决定**，Python 循环体现不出 SIMD 的优势。 **IVFADC**（20000×64，n_list=256，m=16）：倒排表 min 0 / 中位 69 / max 280（分布不均），训练 12.8 s。`n_probe` 扫描：1/2/4/8/16/32/64/128/256 → 候选占比 0.57%/1.02%/1.67%/3.02%/6.18%/…/100%，Recall 0.504/0.648/0.720/0.723/0.723/…/**0.723**——**召回到 0.72 就封顶，剩下的缺口是 PQ 量化误差，不是候选覆盖**。残差编码 vs 直接编码：MSE 8.06 → **1.13**，Recall 0.297 → 0.720（+140%）。`n_list`=16/64/256/512 时 Recall 0.355/0.531/**0.720**/0.686——存在性价比最优点，不是越大越好。 ### §18.5 HNSW（`hnsw.py`） 层数分布实测与 `e^(−l/m_L)` 逐行吻合（M=32、l=1 时 0.0310 vs 0.0312）。6000×64、M=8、efC=40：构图 10.8 s、**7,415,974 次距离计算**（平均 1,236 次/点，约为暴力两两的 **41%**），层节点 6000/787/104/18/3，平均度数 9.6。`efSearch` 10/20/40/80/160 → Recall 0.423/0.544/0.681/0.822/0.904，距离计算 226/340/550/895/1449，单查询 0.31–2.42 ms。M 与 efC（efSearch=80）：M=8/efC=100 0.866、M=16/efC=40 **0.923**、M=16/efC=100 0.973、M=32/efC=100 0.993；构图耗时 10.9→26.1 s。选边启发式 vs「取最近 M 个」：Recall 0.423/0.681/0.822 vs 0.364/0.625/0.729，**相对提升 9%–16%**，代价是构图慢 34%（10.9 s vs 8.1 s）——图连通性是结构差异，调 `efSearch` 补不回来。 ### §18.6 工具选型（`tool_matrix.py`） **所有分数都是 [MOCK] 主观分，不是基准测试。** 三份画像的 Top-3：小规模实验 Pinecone 4.27 / Qdrant 4.07 / Faiss 3.60；十亿级 Milvus 4.36 / Qdrant 3.79 / Pinecone 3.79；RAG Qdrant 4.25 / Pinecone 3.94 / Elasticsearch 3.75。第一名各不相同——「哪个向量库最好」本身不是个好问题。敏感性：去掉「运维复杂度」一维后，十亿级画像的 Top-3 从 Milvus/Qdrant/Pinecone 变成 Milvus/Elasticsearch/Faiss。 ### §18.7 索引生命周期（`index_lifecycle.py`） 小候选池（100 条）缺 7 条，返回 93 条，**业务当天就能发现**；20,000 条缺 386 条（1.9%）时 Top-10 召回只从 1.000 掉到 **0.979**——第 11 名顺位补上，指标几乎不动。双缓冲最常见的失效点：构建期间新增 500 条、回放只覆盖 70%，新索引缺 150 条，而它们在旧索引里是有的，**切换前的两份索引各自都「合法」**。四种校验在切换前都能发现缺口（条数差集 536 条、ID 集合差集、抽样自检索覆盖率 0.970、小候选池 93/100）；修复后 20,500/20,500、缺 0 条、自检索 1.0000。 --- ## 实现约定与踩过的坑 - **Recall 的基准始终是暴力精确检索**，不是另一个近似索引。否则「A 比 B 召回高」可能只是两者都错在不同地方。 - **`np.argpartition` 取 Top-K 后要再 `argsort`**，否则返回的顺序无序，Recall 计算不受影响但打印出的距离会乱序。 - **球树合并父球时必须断言覆盖性**：`‖c_L−c‖+r_L ≤ r + ε` 且 `‖c_R−c‖+r_R ≤ r + ε`。这两条不等式就是最小包围球的定义；漏掉断言时，公式写错不会报错，只会静默漏召回。 - **HNSW 的 `efSearch` 要先 `max(efSearch, k)`**，否则结果队列装不下 Top-k，召回会出现不应有的波动。 - **HNSW 的图质量对插入顺序敏感**：脚本按数据顺序插入，工业实现通常打乱。要比较两个参数配置时，必须用相同的 `np.random.default_rng` 序列。 - **`sq_dists` 逐查询展开而不是广播成 `[Q,N,D]`**：128 维、6000 库、200 查询就是 600 MB；展开后 `np.maximum(out, 0)` 兜住浮点负零。 - **tool_matrix 的分数不能当结论**：它在文件头就标了 `[MOCK]`，目的是演示「先写约束、再加权」的方法，替换成真实压测数据才有决策价值。 --- ## 关于正文的几处勘误 1. **球树父球球心公式符号写反了。** 正文式 `c_parent = c_L + (d + r_L − r_R)/(2d)·(c_R − c_L)` 应为 `(d − r_L + r_R)/(2d)`。按正文写法，当 `r_L < r_R` 时父球包不住右子球（右球外沿超出 `(r_R−r_L)/2`），剪枝会误剪真实近邻。正确球心在两球最远表面点的中点，半径 `(d+r_L+r_R)/2`。`ball_tree.py` 的 `merge_ball` 保留了覆盖性断言，改回正文式会直接 assert 失败。 2. **Banding 拐点近似 `t₀ ≈ (1/b)^(1/r)` 高估了拐点位置。** 它把 `t₀ʳ = 1−2^(−1/b)` 换成了 `1/b`，忽略了 `ln2`。b=16、r=4 时精确值 **0.4538**、近似值 0.5000（**+10.2%**），b=256、r=4 时 +9.6%——正文说「b 取十几到几十时偏差很小」，实测偏差稳定在 **5%–10%**，做参数初筛够用，做召回率承诺不够。 3. **PQ 的「32640 个距离值」是上三角计数。** 正文写 `½×256×255 = 32640`，那是利用对称性只存上三角；若存含对角线的全矩阵是 `K² = 65536`。两种写法都极小，但含义不同，引用时要说清楚。 4. **「球树在高维比 KD 树好」不成立。** 实测在均匀数据 D=4/8/16 上球树访问占比 15.6%/54.8%/99.9%，KD 是 7.0%/29.6%/93.9%——球树反而更差。球树的价值是「每个节点下界只需一次球心距离、支持任意三角不等式度量」，不是抗维度灾难。