索引原理：在三角里选一个点

整章只有一个核心主张：所有 ANN 索引都是 recall × 延迟 × 内存 这个三角里的一个点。每一种索引——IVF、HNSW、PQ、DiskANN——都是为了往某个角靠拢，而代价是远离另一个角。读完后，面对一个陌生索引或一组陌生参数，能力不是背它的定义，而是定位它在三角里的位置、说出它牺牲了什么。先把这张图刻进脑子。

00为什么精确 KNN 不 scale

暴力最近邻在小数据上是对的答案，在亿级上是不可能的答案——而高维度让所有"聪明"的树形索引退化回暴力。

精确 K 近邻（brute-force KNN）的机制只有一句话：对每个 query，逐一计算它到全部 N 个库向量的距离，排序取前 k。每次距离计算要遍历 d 个维度，于是单 query 的复杂度是 O(N·d)。在 N=100 万、d=768 的规模上，每次查询要做约 7.7 亿次乘加，单机可以扛；到 N=10 亿，每次查询变成约 7700 亿次浮点运算，且光是把向量装进内存就要 1e9 × 768 × 4 字节 ≈ 3 TB（float32）。这不是"慢一点"，是从根上做不到在线服务。

维度灾难：树形索引为什么失败

低维空间（2D、3D）有成熟的精确加速结构——KD-tree、ball-tree、R-tree——靠递归切分空间，把搜索从 O(N) 降到 O(log N)。它们的前提是"能用一个边界把远的点整片剪掉"。高维空间摧毁这个前提：当维度升到几百，所有点对之间的距离趋于相等——最近邻距离与最远邻距离的比值趋近 1。直观地说，高维球壳的体积几乎全部集中在表面附近，任意两个随机点都"几乎一样远"。

后果是 KD-tree 的剪枝条件几乎永远不成立：每次想剪掉一个分支，超球与超平面总是相交，于是回溯访问几乎所有节点，复杂度退化回 O(N)——而且常数比纯暴力还大（多了树遍历的指针跳转开销）。这就是整个领域的分水岭：精确树法在高维失败，于是只剩两条路——要么放弃精确（近似最近邻 ANN，用图法/量化法换概率正确），要么放弃稠密遍历（也是 ANN）。本章后面的全部索引都是 ANN，没有一个保证返回真正的最近邻。

01IVF：先聚类，再只看几个桶

把向量空间预先切成若干区域，查询时只进最相关的几个区域扫描——用"少看一些"换速度。

IVF（Inverted File，倒排文件索引）的机制分建索引与查询两步。建索引期：对全集做一次 k-means 聚类，得到 nlist 个质心；这些质心把空间划分成 nlist 个 Voronoi cell（每个点归属于离它最近的质心）；然后为每个 cell 维护一张倒排表，记录落在该 cell 里的所有向量。查询期：先做一次"粗筛"——计算 query 到全部 nlist 个质心的距离，挑出最近的 nprobe 个 cell；再做"精排"——只在这 nprobe 个 cell 的倒排表里暴力扫描。如果 nprobe 远小于 nlist，扫描量就从 N 降到约 N · nprobe / nlist。

nprobe：召回与延迟的直接拨杆

nprobe 是 IVF 最重要的查询期旋钮，它直接坐落在三角的 recall–延迟边上。nprobe=1 最快，但有一个结构性失败模式——边缘漏检：query 落在某个 cell 的边界附近，它真正的最近邻却在隔壁 cell 里（见图 2.2）；只探测 query 所在的那一个 cell，隔壁那个真近邻永远不会被看到。调大 nprobe 会把相邻的 cell 也纳入扫描，召回随之上升，但扫描量与延迟同步上升。nprobe 一路调到等于 nlist 时，IVF 就退化成全量暴力——recall=1.0，但也失去了全部加速。

IVF + PQ：把 cell 内的向量压成码

纯 IVF 的倒排表里存的还是全精度向量，内存占用与暴力相当（Sift1M 上约 520MB）。生产里 IVF 几乎总和 PQ（下一节）组合成 IVFPQ：cell 内不存原始向量，而存 PQ 压缩码，内存可降一到两个数量级，于是单机能扛十亿级。代价是 recall 再损一档——PQ 的近似距离叠加 IVF 的边缘漏检，两层近似累积。

带来的代价：IVF 的 recall 上限被聚类质量锁死——k-means 的边界是静态的，边缘漏检无法靠查询期完全消除，只能用更大的 nprobe 缓解，而那直接吃延迟。IVF 还需要一次全集训练（k-means）才能建索引，数据分布漂移后质心会失准、召回静默下降，需要周期性重训。相比之下图法（HNSW）无需训练、增量插入更友好——这是 HNSW 成为默认而 IVF 退居"内存敏感/超大规模"场景的原因之一。

02HNSW：跳表思想叠在邻近图上

把"高速公路 + 乡间小路"的分层导航搬到向量空间——顶层大跨步逼近，底层小步精定位，近似对数复杂度。

HNSW（Hierarchical Navigable Small World）是当前事实上的默认索引，几乎所有向量库的首选。它的结构是把跳表（skip list）的思想叠加在一张邻近图上，形成多层结构：底层（layer 0）是一张包含全部点的邻近图，每个点连着若干个近邻；往上每一层都是下层的稀疏子集，层级越高点越少、边越长（长程边）。每个新插入的点，按指数分布随机抽一个"最高层数"——绝大多数点只在底层，少数点穿透到高层充当长程枢纽。

搜索过程：greedy best-first 逐层下降

查询从顶层的固定入口点开始：在当前层做贪心 best-first 搜索——不断移动到比当前更接近 query 的邻居，直到走到一个局部最近点（没有邻居更近了）；然后以这个点为入口降到下一层，重复。越往下层越密，搜索步长越来越细。到了 layer 0，用一个大小为 ef_search 的动态候选堆做最后收敛——维护一个候选集，持续扩展直到堆里前 k 个稳定下来。整个过程跳过了大量无关区域，复杂度近似对数级 O(log N)。

为什么 HNSW 是默认

原因只有一句：在相同 recall 下，HNSW 的延迟与吞吐通常优于所有其它索引。它不需要训练（不像 IVF 的 k-means），支持增量插入，且查询期只用一个 ef_search 就能平滑地在 recall–延迟边上滑动。在 ann-benchmarks 这类公开基准上，HNSW 在 recall–QPS 曲线的高召回区段长期领先。

带来的代价（一）吃 RAM：HNSW 把全精度向量 + 每个点 M 条邻接边全部驻留内存。邻接信息本身就是一笔可观开销，叠加原始向量后，总内存通常是裸向量的 1.5–2 倍。这就是图 2.1 里 HNSW 远离"内存"角的原因——它用 RAM 买速度和召回。亿级数据上这意味着上百 GB 内存，成本陡增（这正是下文 DiskANN 存在的理由）。

带来的代价（二）删除难：删一个点会切断图的连通性，原本经它中转的路径随之断掉，召回受损。工程上的常规做法是 tombstone 软删除——标记为已删但保留在图里、查询时过滤掉，再周期性地重建索引把墓碑真正清除。频繁增删的场景下，HNSW 的图会逐渐劣化，重建是必须的运维动作。

03PQ 与量化家族：把向量压成字节

不改变"找最近邻"这件事，只把向量本身压缩——用近似的距离换断崖式的内存下降。

PQ（Product Quantization，乘积量化）是把内存往下压的主力机制。它的做法：把 D 维向量切成 m 段连续的子向量；对每一段子空间独立跑一次 k-means，训出 2^nbits 个质心（nbits=8 即每段 256 个码本条目）；然后每段只存"离它最近的那个质心的 ID"，占 1 个字节。举例：128 维向量切成 m=8 段、每段 nbits=8，原始 128 × 4 = 512 字节被压成 8 × 1 = 8 字节，约 64× 压缩。"乘积"二字来自这里——整个空间被表示成 m 个子空间码本的笛卡尔积，256^8 种组合用 8 字节就能编码。

ADC：query 不量化，查表累加

压缩后怎么算距离？用 ADC（Asymmetric Distance Computation，非对称距离计算）：query 向量不量化，保持全精度。查询时先为 query 预计算一张距离表——它的每个子段到对应子空间 256 个质心的距离，得到一张 m × 256 的表。之后计算 query 到任意库向量的距离，就退化成按库向量的 m 个码 ID 查表、累加，m 次查表加法即可。"非对称"指的就是 query 全精度、库向量量化这种不对称——它比"两边都量化"的对称方式更准，因为 query 侧没有量化误差。

量化家族的其它成员

PQ 是表达力最强但也最复杂的量化。还有两个更简单的表亲，生产里用得同样多：

• Scalar quantization（标量量化，SQ）：最朴素——按每一维的 min/max 把 float32 线性映射到 int8，4× 压缩，recall 损失极小（int8 的 256 级对大多数 embedding 足够）。几乎是免费的内存优化，很多库默认开。
• Binary quantization（二值量化，BQ）：最激进——每一维只取符号（正→1，负→0），float32 变 1 bit，32× 压缩；距离用 Hamming 距离算，检索快可达 40×。单看精度它损失巨大，但靠 oversampling + rescore 救回来：先用二值码超量召回（取比 k 多几倍的候选），再用保留的全精度向量对这批候选重新精确打分排序，recall 能拉回约 0.98。

带来的代价：纯 PQ 的 recall 可以掉到约 50%——量化误差让"哪个更近"的判断频繁出错。所以 PQ 几乎从不单独使用，总是配 IVF（成 IVFPQ，先用 IVF 缩小范围再 PQ 算距离）或配图法（DiskANN 用 PQ 码在内存里粗筛、SSD 上的全精度向量做 rescore）。此外 PQ 需要训练码本，和 IVF 一样面临分布漂移失准的问题。量化的统一代价可以归成一句：所有量化都在用"距离的精度"换"存储的体积"，而把精度补回来的唯一办法是保留一份高精度向量做 rescore——那份向量又得占地方。

04DiskANN / Vamana：把图放到 SSD 上

让图和全精度向量躺在 SSD、内存只放压缩码——用"磁盘 IO 换内存成本"，把十亿级拉进单机预算。

DiskANN 存在的理由，直接来自 HNSW 的代价：HNSW 把全精度向量加图全压在 RAM 里，十亿级要上百 GB 内存，贵得离谱。DiskANN 的机制是分层存储——把图结构和全精度向量放到 SSD 上，内存里只保留每个向量的 PQ 压缩码。查询时用内存里的 PQ 码做快速粗筛（沿图导航时用近似距离决定走向），需要精确判断时才去 SSD 读对应的全精度向量做 rescore。结果是单机 64GB RAM + 一块 NVMe SSD 就能跑 10 亿个点，recall@1 > 95%、延迟 < 5ms。

Vamana 图与 α：故意留长程边

DiskANN 用的图叫 Vamana，它是单层扁平图（不像 HNSW 那样分层）。它的核心创新是建图时 RobustPrune 剪枝里的 α 参数。剪枝决定每个节点保留哪些边：HNSW 的剪枝隐含 α=1（偏向保留短边、剪掉被"遮挡"的长边）；Vamana 用 α>1（典型 1.2）放松剪枝条件，故意保留更多长程边。多保留长程边的效果是图的直径变小——任意两点之间的跳数更少，于是 beam search 用更少的跳数就能收敛。

带来的代价：DiskANN 把延迟从"内存级"抬到"SSD 级"——虽然靠小直径把单机十亿级压进 5ms，但这仍比纯内存 HNSW 的亚毫秒慢一截，且强依赖 SSD 性能（机械盘上不可用，云上要选高 IOPS 卷）。它换来的是内存成本的断崖式下降。在图 2.1 里 DiskANN 和 IVFPQ 一起压向"内存"角，区别在 DiskANN 用图导航+SSD rescore 守住了更高的 recall。选 DiskANN 的判据很清晰：数据量大到 HNSW 的内存账单不可接受，且能接受毫秒级（而非亚毫秒）延迟。

05LSH：为什么基本被淘汰

用一族哈希让近向量高概率撞同一个桶——思路优雅，但在高维高召回需求下打不过图法。

LSH（Locality-Sensitive Hashing，局部敏感哈希）的机制：设计一族特殊的哈希函数，使得距离近的向量有较高概率被映射到同一个桶（与普通哈希刻意打散相反）。建索引时把所有向量哈希进桶，几乎是瞬时的；查询时只算 query 所在桶（及少数邻桶）里的向量距离。理论上很美——亚线性查询、建索引极快。

为什么被取代：要达到高 recall，单个哈希撞桶的概率不够，必须用很长的签名 + 很多张哈希表来提升命中概率，这导致内存急剧膨胀；而且它同样受维度灾难拖累（高维下"近的撞桶"这件事本身就变难）。更致命的是它的概率性——同一个 query 的性能不可预测，召回波动，不像 HNSW 那样行为确定、可在 recall–延迟边上精确调节。在同等 recall 目标下，HNSW 延迟更低、内存更省、行为可复现，于是 LSH 在通用向量检索里基本退场。

残留价值：LSH 没有完全消失——它的建索引极快、写入便宜，在某些写多读少、对召回要求不高、或需要快速去重/近似匹配的场景仍有用武之地。但作为"在线高召回最近邻检索"的主力，它已被图法取代。

06统一框架：在三角里推理一次

前面五种机制的全部旋钮，最终都服务于同一个动作——在 recall × 延迟 × 内存 三角里把你的点放到正确位置。

把图 2.1 落到一个具体场景上推一遍。需求：1000 万条 768 维向量，延迟预算 20ms（P99），内存预算 8GB。该选哪个索引？不背结论，用前面的旋钮一步步推。

这就是整章的方法论：先看哪个角是硬约束，让它筛掉一批索引；再看剩下的旋钮能不能把另外两个角调到达标。没有"最好的索引"，只有"在你这三个预算下、紧约束允许的索引"。下面这张总表把六种索引在三角里的位置一次性列清。