一句话定义
Annoy 用随机投影递归二分把向量空间切成一棵树（默认建多棵树），查询时沿每棵树走到叶子再合并候选：为"静态、只读、多进程内存共享"的推荐场景而生，是理解树形 ANN 路线的最小范本。
为什么重要
Annoy 是 ANN 工程化的早期代表作（Erik Bernhardsson 为 Spotify 音乐推荐所写），其两个贡献超越了算法本身：把"随机化 + 多棵树投票"的稳健思想带入工程，以及 ann-benchmarks 评测框架确立了行业比较标准。读懂 Annoy 的取舍，能理解为什么嵌入时代图索引最终胜出——这是选型判断力的历史坐标。
前置知识
kp-006（Flat 基线）；二叉树概念。
核心概念
- 随机超平面切分：每节点随机选一个超平面把当前点集一分为二，递归直到叶子足够小；查询沿"点在超平面哪一侧"下行。
- n_trees：树的数量。树多 → 候选覆盖面广、召回高，内存与构建时间线性上升。
- search_k：查询时实际探查的叶子规模（默认约 n_trees × k），在线旋钮，调大提召回。
- 只读 mmap：索引建完为静态文件，mmap 后多进程共享同一份物理内存——Annoy 的招牌特性。
- 距离支持：欧氏、余弦、汉明、点积（版本相关），不支持任意自定义度量。
原理与机制
建树：每棵树独立随机采样超平面序列，把空间切成细长单元格；同一向量出现在每棵树的一个叶子里。查询：对每棵树从根下行到叶子（约 log₂N 步），收集叶子内向量，跨树合并、按真实距离排序取 top-k；search_k 决定"每棵树多认真"。
结构取舍（与 HNSW 对照）：
| 维度 | Annoy | HNSW |
|---|---|---|
| 结构 | 静态多树 | 动态图 |
| 增量插入 | 不支持，需重建 | 支持（图可扩） |
| 多进程内存共享 | mmap 原生 | 各进程独立或依赖系统实现 |
| 高维召回曲线 | 明显弱于 HNSW/PQ 系 | 强 |
| 典型场景 | 旧式推荐、维度不高、只读 | 通用在线检索 |
树形路线在高维的根本困难：随机超平面切分在高维近似"均分球面"，叶子内近邻命中率随维度升高而下降，必须靠"多棵树 + 大 search_k"硬补——这正是 ann-benchmarks 上 Annoy 曲线整体位于 HNSW 右下方（同等召回需要更多延迟）的原因。
公式或模型
本节不适用：结构对比篇，无新公式；随机投影的理论基础（Johnson–Lindenstrauss 引理）见延伸阅读。
图示
根(随机超平面 h1)
╱ ╲
左子(h2) 右子(h3)
╱ ╲ ╱ ╲
叶A(点集) 叶B 叶C 叶D
查询: 每棵树选一侧下行(可回溯) → 收集叶子点 → 合并排序 top-k实例或案例
Spotify 场景画像：千万曲目、128 维（旧式音频特征）、模型每天全量重训一次、几十个 worker 进程只读查询。Annoy 用 2 倍内存换来"一次构建、多进程零拷贝共享"，完美贴合；同样的库若要求实时增删曲目，Annoy 立即出局——静态共享与动态更新是它和图索引的分界线。
直观类比
Annoy 像一群考官（n_trees 棵树）各自按不同目录分类法把图书馆分层分架；找书时每位考官指一个书架，把几个书架的书都翻出来比对（search_k）。分类法固定后不能临时改（只读），想找得更准只能多翻几架。
常见误区
- "Annoy 适合新项目做嵌入检索"——高维嵌入下它的召回-延迟曲线已被图索引全面超越，新项目选它只剩"多进程 mmap 共享"这一个理由。
- "search_k 默认值总是够用"——默认约 n_trees × k，对高召回目标（97%+）通常不足，需显式调大并重测。
- "树形索引都能增量更新"——Annoy 是纯静态构建，任何写变化都要全量重建，写多场景直接排除。
自测题
- n_trees 与 search_k 分别在哪一端发力？
- Annoy 在今天还有哪些不可替代的场景？
- 为什么高维下树形切分的召回吃亏？
答：n_trees 决定候选覆盖广度（建库侧，动它要重建）；search_k 决定查询探查深度（在线侧，可随时调大换召回）。
答：超大规模只读索引需要多进程 mmap 共享内存、或作为轻量无依赖方案嵌入单机应用。
答：高维空间中随机超平面近乎均分各方向，"近邻对"被切开的概率升高，叶子内近邻密度下降，只能靠更多树与更大 search_k 补偿。
与其他知识点的关系
kp-008 的 HNSW 是它今天的替代者；kp-004 的"维度灾难"解释了树形路线的衰落；kp-005 的流派谱系里它是"树派"代表。
延伸阅读
Bernhardsson, "Annoy: Approximate Nearest Neighbors in C++/Python"（开源项目与作者博客，2013 起）——树形 ANN 的工程实录与 mmap 设计细节。