城市图书馆的周师傅遇到了职业生涯最大的难题：馆里藏书涨到了十亿册，可经费却被砍了大半。过去，图书馆把每本书的“完整摘要”和“推荐卡网络”（哪些书相似、哪些书值得互相推荐）全部摆在阅览室里——读者进门翻一翻就能找到书，这就是 HNSW 的做法，找书飞快。但十亿册书的推荐卡和摘要加起来要占上千 GB 的阅览室，而“阅览室”（内存）的价格是“地下仓库”（SSD 磁盘）的十倍以上，根本买不起。 DiskANN 的解法朴素而巧妙：把推荐卡网络连同书本身全部搬进地下大仓库（SSD），阅览室里只留一个“迷你索引卡盒”——每本书用几十个比特的缩写代码记录内容要点（这叫乘积量化压缩）。找书时，周师傅先翻索引卡锁定大致方向，再去仓库按推荐卡走几步，最后把几本候选书抱回阅览室精读。虽然每次坐仓库电梯要花点时间，但他每次多带几张卡出来（预取），几十趟就能摸到目标。这篇文章就用“小目录 + 大仓库”的比喻，带你读懂 DiskANN 的原理、Vamana 图、乘积量化压缩、搜索流程与工程选型。

岗位关联

掌握 DiskANN 的“图放磁盘 + PQ 码进内存”思路，是解决十亿级向量检索内存瓶颈的硬技能，直接决定搜索、推荐、RAG 系统的召回架构选型与成本控制。

目录
  1. 可视化演示
  2. 一、内存受限困境
  3. 二、DiskANN设计
  4. 三、Vamana图结构
  5. 四、乘积量化压缩
  6. 五、搜索性能优化
  7. 六、工程实践要点
  8. 七、算法对比选型
  9. AI 应用场景
  10. Python 演示
  11. 常见误区
  12. 面试题

可视化演示

模拟Vamana有向图的贪婪路由搜索、SSD节点对齐存储与内存缓存预取策略，展示DiskANN在内存受限场景的检索过程。

本节配有交互动效（进入视口后自动加载，约 3KB）。

模式1：Vamana图贪婪路由 青色节点为已访问路径 橙色为目标查询点 next = argmin dist(q, neighbors) 长程边加速远距离跳转。

一、内存受限困境

周师傅的图书馆正在经历一场“书灾”：总馆藏书达到十亿册，而阅览室却因经费削减缩水到原来的十分之一。最让他头疼的不是书多，而是“书架”贵——服务器内存每 GB 的价格是 SSD 磁盘的十倍以上，想靠加内存解决问题，预算是天文数字。他站在空荡荡的阅览室中央，看着堆不下的搬运箱，第一次认真考虑：是不是不该让所有书都待在阅览室里？

在向量检索的世界里，HNSW 就是那个“把什么都放阅览室”的激进方案。它既要存每条商品、文档的 embedding 向量（一串描述内容特征的数字），又要存一张“推荐卡网络”（图的邻接关系），全部常驻内存。十亿条 128 维 float32 向量本身就是 512GB，再算上图结构的邻居指针，轻松逼近 1TB。一台 1TB 内存的服务器贵得离谱，于是团队只能被迫降维、降采样、或者拆成几十台机器分布式部署，成本和复杂度双双飙升。

HNSW 的内存账可以精确算出来：向量本体占大头，图的邻接表占小头。

周师傅看着这个数字直摇头：与其花十倍价钱买书架，不如让大部分书在地下仓库睡觉，阅览室只留一张“迷你索引卡”。这个朴素的念头，正是 DiskANN 的出发点——内存放不下，不是问题，问题是你非要把一切都塞进内存。

MHNSW≈N×(d×4+R×8) bytes\displaystyle M_{HNSW} \approx N \times (d \times 4 + R \times 8) \ \text{bytes}
这个公式把内存花销分成两笔：一笔是“书的摘要”（向量本身），一笔是“推荐卡的格”（图指针）。N 越大、维度 d 越高、出度 R 越大，阅览室就越挤。
  1. 向量本体每条向量有 d 个维度，每个 float32 数值占 4 字节，N 条向量合计占用的内存。
    N×d×4\displaystyle N \times d \times 4
  2. 图邻接开销HNSW 里每个节点平均连向 R 个邻居，每条邻居关系用 8 字节的指针存储。
    N×R×8\displaystyle N \times R \times 8
  3. 两项相加把向量本体和邻接表相加，就是 HNSW 的全部常驻内存。
    MHNSW≈N×(d×4+R×8)\displaystyle M_{HNSW} \approx N \times (d \times 4 + R \times 8)

二、DiskANN设计

周师傅的新方案很快就定了：把整套推荐卡网络和全部藏书搬进地下大仓库（SSD），阅览室只留一个比鞋盒还小的“迷你索引卡盒”。他算过一笔账：NVMe SSD 的随机读延迟只有几十微秒，坐仓库电梯一趟虽说不便宜，但整个找书流程只需要坐几十趟，加起来也就几毫秒——完全在读者可接受的范围内。

DiskANN 的工程师们做了和三步走完全一样的决策：第一，图结构和完整向量放到 SSD 上，利用 SSD 优秀的随机读性能；第二，内存里只保留乘积量化（PQ）压缩后的短码，每条向量从 512 字节缩到 8 字节左右；第三，查询到达时，先在内存里用 PQ 码算出粗略距离，找到起点，再去磁盘上沿着图走，最后把候选的完整向量拉回内存做精确重排序。三步环环相扣，缺一不可。

内存账本一下子清爽了：

周师傅的第一版方案顺利上线：读者借书的时间从原来的“书架前徘徊”变成了“翻卡、下楼、走几步、抱书回来”。读者没觉得变慢，财务部却乐开了花——省下的钱够买三倍容量的 SSD。这个“小目录 + 大仓库”的架构，就是 DiskANN 能在十亿级数据上落地的根本原因。

MDiskANN≈N×m×log⁡2k8 bytes≈MHNSW10∼20\displaystyle M_{DiskANN} \approx \frac{N \times m \times \log_2 k}{8} \ \text{bytes} \approx \frac{M_{HNSW}}{10 \sim 20}
PQ 码把每条向量压成 m 个码字，每个码字用 log₂k 个比特表示。算下来 DiskANN 的内存需求只有 HNSW 的十分之一到二十分之一——阅览室缩成了索引卡盒。
  1. 单条 PQ 码的位宽一条向量被切成 m 段，每段用 k 个质心之一表示，每段需要 log₂k 个比特。
    m×log⁡2k bits\displaystyle m \times \log_2 k \ \text{bits}
  2. 换算成字节N 条向量的码加起来，除以 8 从比特换算成字节。
    N×m×log⁡2k8 bytes\displaystyle \frac{N \times m \times \log_2 k}{8} \ \text{bytes}
  3. 与 HNSW 对比以 128 维、m=16、k=256 为例，单条码只有 16×8=128 比特，是原向量 512 字节的 1/32，再叠加省掉的图结构，总量约为 HNSW 的 1/10~1/20。
    MDiskANN≈MHNSW10∼20\displaystyle M_{DiskANN} \approx \frac{M_{HNSW}}{10 \sim 20}

三、Vamana图结构

仓库里的推荐卡怎么贴，是周师傅最花心思的地方。他起初想照搬 HNSW 的“分层书架”：顶层放最热门的书，往下逐层细分。但在仓库里，层与层之间要坐不同的电梯，每换一层都是一次昂贵的磁盘读。周师傅决定反其道而行：仓库里只建一层书架，但每本书的推荐卡贴得又密又精——这一层的图结构就是 DiskANN 的 Vamana 图。

Vamana 图是一个单层有向图，每个节点有固定的出度 R（典型值 32~64），比 HNSW 每层的邻居数大得多。构建时先通过随机投影或聚类初始化一个粗略的图骨架，然后逐点插入：用当前的图找到近似最近邻作为候选，再对候选做“多样性剪枝”。剪枝的规则很讲究——与其把所有近邻都连上，不如只保留那些“方向不同”的邻居，让推荐卡覆盖不同的知识区域，避免邻居扎堆。

与 HNSW 相比，Vamana 放弃了多层跳跃，用单层大度数换来了两个关键收益：图直径更小——从任意点出发到达目标所需的跳数更少；磁盘友好——每一跳都只是顺序地读一个节点的邻居列表，没有层级间的跳转开销。周师傅的体会是：在仓库里少坐电梯，比书架分得多精美更重要。Vamana 正是“用更大的单层图，换更短的路程”。

保留候选 yj 当且仅当 ∥yj−x∥<∥yj−xi∥,∀xi∈Sx\displaystyle \text{保留候选 } y_j \ \text{当且仅当} \ \| y_j - x \| < \| y_j - x_i \|, \quad \forall x_i \in S_x
这条规则的意思是：一个新候选 y 要成为 x 的邻居，它必须比“已经选中的任何邻居 xᵢ”都离 x 更近。如果它离某个老邻居反而更近，说明它俩“太像了”，留一个就够。
  1. 候选与中心的距离先算新候选 yⱼ 与中心节点 x 的距离，这是它作为邻居的基本资格。
    ∥yj−x∥\displaystyle \| y_j - x \|
  2. 与已选邻居逐一比较把 yⱼ 与集合 Sₓ 中每个已保留邻居 xᵢ 的距离都算出来。
    ∥yj−xi∥,∀xi∈Sx\displaystyle \| y_j - x_i \|, \quad \forall x_i \in S_x
  3. 全称条件判定只有当 yⱼ “比谁都离中心更近”时才保留它，从而保证邻居在方向上彼此分散、覆盖更广。
    ∥yj−x∥<∥yj−xi∥\displaystyle \| y_j - x \| < \| y_j - x_i \|

四、乘积量化压缩

迷你索引卡到底怎么记录一本书的内容？周师傅发明了一套“缩写编码”：把一本书的 128 个特征数值切成 4 段，每段 32 个数；对每一段，从 16 种“典型片段”里挑最接近的一种，记下它的编号。这样一来，一本书的摘要就变成了 4 个编号，每个编号 4 个比特，总共 16 比特——而原来的完整摘要要 512 字节。这个把向量切成小段、逐段量化压缩的方法，就是乘积量化（Product Quantization，PQ）。

PQ 的码本（codebook）怎么来？靠聚类。对每一段子向量，用 k-means 聚出 k 个质心作为“典型片段”，所有向量在某一维段上都用最近的质心编号表示。查询时，DiskANN 会预计算“查询向量 vs 每个质心”的距离查找表（LUT），然后把码字对应的距离累加，得到近似的向量距离。整个过程全是查表和小整数加法，快得惊人。

压缩比可以精确表达：

周师傅很清楚：索引卡上的缩写只够“猜方向”，不够“定结果”。所以 DiskANN 的搜索严格分成两段——先用 PQ 码在内存里快速粗筛、导航，最后一定把候选的完整向量从磁盘拉回来做精确距离计算。压缩负责省内存，重排序负责保精度，两人各司其职。索引卡永远只是地图，真正的答案永远在书里。

r=32dmlog⁡2k\displaystyle r = \frac{32d}{m \log_2 k}
压缩比是“原来的比特数”除以“压缩后的比特数”。128 维向量、切成 8 段、每段 256 个质心时，压缩比高达 64 倍。
  1. 原向量比特数每条向量 d 个 float32 数值，每个数 32 比特。
    32d bits\displaystyle 32d \ \text{bits}
  2. 压缩后比特数切成 m 段，每段用 log₂k 个比特的质心编号表示。
    mlog⁡2k bits\displaystyle m \log_2 k \ \text{bits}
  3. 两者相除得压缩比比值就是信息量的缩减倍数，也是内存和带宽节省的倍数。
    r=32dmlog⁡2k\displaystyle r = \frac{32d}{m \log_2 k}

五、搜索性能优化

周师傅的日常工作形成了一套固定流程：先翻迷你索引卡，找出与读者需求最像的几本书作为起点；然后攥着一张“推荐卡清单”坐电梯下仓库，每到一个书架就取出推荐卡，看看它指向谁；他每次最多同时跟踪 L 个候选（这叫波束宽度），一批批地扩展；最后把搜集到的候选书抱回阅览室，对照完整摘要精读，挑出最合适的几本。整个过程，就是 DiskANN 的波束搜索（Beam Search）。

要让这个流程跑得快，有三个关键手段。第一是热点缓存：仓库里最常被翻的书架，周师傅直接把它们的推荐卡复印件揣在口袋里，内存里缓存热点节点，能省掉大量重复的磁盘读。第二是批量预取：每次下仓库不单独取一张卡，而是一次性把当前所有候选的邻居列表都读出来，把几十次随机小 IO 合并成几次大 IO，充分利用 SSD 的并发能力。第三是控制跳数：Vamana 图保证了从起点到目标通常只需要 40~80 跳。

一次查询的整体延迟可以建模为：

周师傅倚在仓库门口总结道：所谓性能优化，无非是“少跑路、一次多带、该记的记在兜里”。缓存让热门书架不再反复折腾电梯，预取让每一趟电梯都满载，而 Vamana 图保证了路本身不远。三者合起来，让“坐仓库电梯的图书馆”在读者体验上几乎追平了“全在阅览室的图书馆”。

Tsearch≈h×Tio+Tpq\displaystyle T_{\text{search}} \approx h \times T_{io} + T_{pq}
h 是图的跳数（磁盘读次数），T_io 是单次 SSD 随机读延迟，T_pq 是内存中 PQ 距离计算时间。现代 NVMe SSD 的单次随机读约 50~100 微秒，所以 40~80 跳对应 2~8 毫秒，再加上 PQ 计算的零点几毫秒，总体延迟可控。
  1. 单跳的 IO 代价每读一个节点的邻居列表，就是一次磁盘随机读，花费 T_io。
    Tio\displaystyle T_{io}
  2. 全路程的总 IO 时间h 跳的路程乘以单跳时间，是延迟的绝对大头。
    h×Tio\displaystyle h \times T_{io}
  3. 加上内存计算时间PQ 距离查表和候选维护只占零点几毫秒，但必须计入总账。
    Tsearch≈h×Tio+Tpq\displaystyle T_{\text{search}} \approx h \times T_{io} + T_{pq}

六、工程实践要点

把方案从纸面变成现实，周师傅踩了不少坑。首先是新书上架：十万册新书到馆，如果逐本搬入并现场贴推荐卡，构建过程会阻塞读者借书。他的做法是“深夜赶工”——先在离线集群上把新书和新旧推荐关系批量算好，生成增量索引文件，再在低峰期热切换上线。这就是 DiskANN 的批量构建：充分并行、分片处理，构建期间在线查询完全不受影响。

日常运营中，增量更新是另一门手艺。每本新书到馆，先算它的 PQ 码放进索引卡盒，再在图上找到它的近邻、连上新边，同时按出度 R 做裁剪；下架的书不直接删除，而是打上“失效标记”（tombstone），等积累到一定量再触发一次局部重建。参数调优更是周师傅的必修课：出度 R 越大图越“密”、跳数越少但构建越贵；波束宽度 L 越大搜索越稳但每次扩展的开销越高；PQ 的段数 m 越大距离越精确但码更长。

上线效果如何，要用一把客观的尺子来量：

周师傅把图书馆的运营心得记在小本上：构建要离线并行、更新要增量轻量、上线要指标说话。磁盘上的图可以慢慢长，但每一步都要可测量、可回滚。正是这套“白天服务读者、夜里悄悄整架”的工程节奏，让 DiskANN 在真实生产环境里既稳又省。

Recall@K=∣GK(q)∩RK(q)∣K\displaystyle \text{Recall@K} = \frac{\left| \mathcal{G}_K(q) \cap \mathcal{R}_K(q) \right|}{K}
Recall@K 衡量的是“最该被找到的 K 本书里，系统真的找回了多少”。真值集 G_K 是暴力计算出的精确最近邻，检索集 R_K 是 DiskANN 返回的结果，两者的交集大小除以 K 就是召回率。
  1. 真值集合用暴力全量计算得到的、与查询 q 真正最相似的 K 个点的集合。
    GK(q)\displaystyle \mathcal{G}_K(q)
  2. 检索结果集合DiskANN 实际返回的 K 个候选点的集合。
    RK(q)\displaystyle \mathcal{R}_K(q)
  3. 交集与比值两个集合重合的元素个数除以 K，就是召回率，取值 0 到 1。
    ∣GK(q)∩RK(q)∣K\displaystyle \frac{\left| \mathcal{G}_K(q) \cap \mathcal{R}_K(q) \right|}{K}

七、算法对比选型

不同的图书馆有不同的活法。社区小图书馆藏书几百万册，全部放在阅览室（HNSW），读者进门三秒钟就能找到书，但规模天花板明显；中型档案馆用卡片目录柜（IVF-PQ），先按大类粗筛再在类内细找，内存适中、规模中等；而国家总馆这样十亿册的庞然大物，只能走 DiskANN 的“小目录 + 大仓库”路线。周师傅的经验是：没有最好的算法，只有最合适的规模。

三者的适用边界其实很清晰。HNSW 面向千万级以内、要求亚毫秒延迟、内存预算充足的场景，比如在线广告的实时召回；IVF-PQ 面向千万到亿级、内存中度紧张的场景，用倒排粗分桶 + PQ 压缩做折中；DiskANN 面向亿到十亿级、内存预算紧绷的场景，接受 1~10 毫秒延迟换取极低的内存成本和庞大的容量。选型的核心判据是一道算术题：

周师傅最后在馆务会上说了一句话，成了图书馆界的名言：“先算账，再选型。”量级、内存、延迟预算三笔账算清楚，方案自然浮出水面。DiskANN 不是用来取代谁的银弹，而是在“内存装不下”这个现实约束下，用 SSD 的容量和毫秒级延迟换回十亿级检索能力的正确答案。

Mneed=N×(d×4+R×8)  与可用内存 Mavail 比较\displaystyle M_{\text{need}} = N \times (d \times 4 + R \times 8) \ \ \text{与可用内存 } M_{\text{avail}} \text{ 比较}
先算全内存方案需要多少内存，再对照你的可用内存。如果 M_need 远超 M_avail，就别硬撑 HNSW 了，直接选 DiskANN。
  1. 全内存方案的内存需求把向量和邻接表都放进内存所需的字节数，是选型的第一道门槛。
    Mneed=N×(d×4+R×8)\displaystyle M_{\text{need}} = N \times (d \times 4 + R \times 8)
  2. 可用资源约束单机或集群实际能提供的内存上限，是硬约束。
    Mavail\displaystyle M_{\text{avail}}
  3. 比较决策M_need 显著大于 M_avail 时选择 DiskANN；放得下且要求极致低延迟则选 HNSW；中等规模预算紧可选 IVF-PQ。
    Mneed>Mavail⇒选择 DiskANN\displaystyle M_{\text{need}} > M_{\text{avail}} \Rightarrow \text{选择 DiskANN}

AI 应用场景

场景一：电商平台的十亿级商品向量召回

阶段：在线召回（海量候选生成）

解决的问题：电商平台将商品图文特征编码成 embedding 向量，商品量达到十亿级。传统 HNSW 方案需要约 1TB 内存常驻，服务器成本极高；降采样又牺牲召回精度。DiskANN 把图和向量放在 SSD，内存只保留 PQ 码，将单机内存需求压到 100GB 以内，让十亿级召回从“买不起”变成“单机可跑”。

具体案例：某头部电商的“相似商品”功能，接入 DiskANN 后召回延迟稳定在 3~8ms，p99 控制在 15ms 以内，内存占用仅为原 HNSW 方案的 1/12，硬件成本下降约 70%。遇到大促新增海量商品时，利用增量化更新在低峰期平滑上线，无需全量重建。

场景二：短视频推荐的增量候选池

阶段：召回池构建与更新

解决的问题：短视频平台每天新增数千万条新视频，如果全量重建 HNSW 索引，计算和 IO 开销巨大。DiskANN 支持轻量增量插入：新视频算好 PQ 码插入索引卡盒，并在 Vamana 图上就近连边，分钟级即可对全网可见。这让“新内容秒级进入召回池”成为可能，显著提升推荐的新鲜度。

具体案例：某短视频平台的“你可能喜欢”召回链路，使用 DiskANN 管理 50 亿条视频向量，配合热点缓存策略，热门视频的命中缓存率超过 60%，整体 QPS 提升 3 倍，新视频从发布到可被召回的时间从小时级缩短到分钟级。

场景三：私有化部署的亿级向量数据库

阶段：离线建库 + 在线查询

解决的问题：银行、政务等场景要求数据不出内网，服务器配置受限，无法提供超大内存。DiskANN 让亿级向量库跑在普通配置的单机上：SSD 存全量，内存只放压缩码，既满足安全合规，又把硬件门槛降到普通机架服务器即可承载。

具体案例：某金融机构的合同语义检索系统，1.2 亿条合同片段向量部署在单台 64GB 内存 + 2TB NVMe SSD 的服务器上，支持内部员工语义检索，平均查询延迟 6ms，召回率保持在 95% 以上，通过了等保合规审计。

Python 演示

python103 行
import numpy as np  class ProductQuantizer:    """Product quantization: compress vectors into short codes."""    def __init__(self, M=4, K=16, seed=42):        self.M = M        self.K = K        self.seed = seed        self.codebooks = []        self.sub_d = 0     def fit(self, X):        """Learn codebooks by k-means on each sub-space."""        rng = np.random.RandomState(self.seed)        d = X.shape[1]        self.sub_d = d // self.M        for m in range(self.M):            sub = X[:, m * self.sub_d:(m + 1) * self.sub_d]            centroids = sub[rng.choice(len(sub), self.K, replace=False)]            for _ in range(12):                dists = ((sub[:, None, :] - centroids[None, :, :]) ** 2).sum(-1)                labels = dists.argmin(1)                for k in range(self.K):                    if (labels == k).any():                        centroids[k] = sub[labels == k].mean(0)            self.codebooks.append(centroids)     def encode(self, X):        """Map each vector to its nearest centroid ids (the PQ code)."""        codes = []        for m in range(self.M):            sub = X[:, m * self.sub_d:(m + 1) * self.sub_d]            dists = ((sub[:, None, :] - self.codebooks[m][None, :, :]) ** 2).sum(-1)            codes.append(dists.argmin(1))        return np.stack(codes, axis=1)     def pq_dist(self, codes, q):        """Approximate distance via lookup tables of centroid distances."""        total = np.zeros(codes.shape[0], dtype=np.float32)        for m in range(self.M):            sub = q[m * self.sub_d:(m + 1) * self.sub_d]            lut = ((self.codebooks[m] - sub) ** 2).sum(1)            total += lut[codes[:, m]]        return total  class MiniDiskANN:    """Simplified DiskANN: k-NN graph on 'disk' + PQ codes in memory."""    def __init__(self, M=4, K=16, R=6):        self.pq = ProductQuantizer(M, K)        self.R = R        self.points = None        self.codes = None        self.adj = None     def build(self, X):        self.points = X        self.pq.fit(X)        self.codes = self.pq.encode(X)        n = len(X)        self.adj = []        for i in range(n):            dists = ((X - X[i]) ** 2).sum(1)            nn = dists.argsort()[1:self.R + 1]            self.adj.append(nn.tolist())     def search(self, q, topk=5, beam=6):        """Beam search over the graph, then re-rank with full vectors."""        dists = self.pq.pq_dist(self.codes, q)        frontier = [int(dists.argmin())]        visited = set()        for _ in range(8):            new = set()            for node in frontier:                if node in visited:                    continue                visited.add(node)                for nb in self.adj[node]:                    if nb not in visited:                        new.add(nb)            if not new:                break            cand = list(new)            cand_d = self.pq.pq_dist(self.codes[cand], q)            order = sorted(zip(cand_d, cand))[:beam]            frontier = [c for _, c in order]        exact = sorted(visited, key=lambda i: ((self.points[i] - q) ** 2).sum())        return exact[:topk]  if __name__ == "__main__":    rng = np.random.RandomState(0)    X = rng.randn(3000, 32).astype(np.float32)    model = MiniDiskANN(M=4, K=16, R=6)    model.build(X)    q = X[123]    hits = model.search(q, topk=5)    truth = ((X - q) ** 2).sum(1).argsort()[:5].tolist()    overlap = len(set(hits) & set(truth))    print("retrieved:", hits)    print("ground truth:", truth)    print("recall@5 =", overlap / 5)
目的：用约百行代码实现一个极简 DiskANN 原型——PQ 压缩建迷你索引、k-NN 图模拟磁盘上的 Vamana 图、波束搜索 + 完整向量重排序，最后用 Recall@5 验证效果。
  1. labels = dists.argmin(1)每个子向量分配到最近的质心，得到码字编号，这是 PQ 编码的核心一步。
  2. self.codebooks.append(centroids)每一段子空间都学出一个码本，码本质量直接决定粗筛精度。
  3. lut = ((self.codebooks[m] - sub) ** 2).sum(1)预计算查询向量与所有质心的距离，形成查找表，避免逐点算距离。
  4. total += lut[codes[:, m]]通过查表把每段的质心距离累加，得到近似的查询-向量距离，速度远快于完整距离。
  5. dists = ((X - X[i]) ** 2).sum(1)构建图时用完整向量计算真实近邻（对应 Vamana 建图时的精确距离），保证图质量。
  6. frontier = [int(dists.argmin())]波束搜索的起点是 PQ 距离最小的点，相当于“先翻索引卡找最相似的书”。
  7. visited.add(node)维护已访问集合，防止图搜索走回头路，也构成重排序的候选池。
  8. cand_d = self.pq.pq_dist(self.codes[cand], q)对每轮新扩展出的候选按 PQ 距离排序，只保留波束宽度内的精英。
  9. exact = sorted(visited, key=lambda i: ((self.points[i] - q) ** 2).sum())最后用完整向量对访问过的所有候选精确排序，这是召回率的关键兜底。
  10. overlap = len(set(hits) & set(truth))把检索结果与暴力真值求交集，量化召回质量。

常见误区

误区我总觉得“凡是检索必须全放内存才快”，磁盘一参与就是慢的象征，DiskANN 的查询延迟肯定比 HNSW 差一个数量级以上。

正解这个直觉停留在机械硬盘时代。现代 NVMe SSD 的随机读延迟只有 50~100 微秒，而 DiskANN 借助 Vamana 图只需要 40~80 次随机读，总延迟 2~8 毫秒。更重要的是，当数据量到十亿级时，HNSW 要么内存放不下，要么被迫分布式分片，跨机通信的延迟和成本反而更高。DiskANN 用“毫秒级延迟 + 极低内存”换来了单机承载十亿级数据的能力，这不是变慢，而是换了一种更划算的代价结构。

为何常见：人们容易把“内存”和“快”绑定、“磁盘”和“慢”绑定，却忽略了 SSD 随机读性能的飞跃，以及内存放不下时不得不分布式带来的隐性开销。

误区把向量从几百字节压成几个字节，信息丢了一大半，召回率肯定崩盘，感觉 PQ 只是个“省内存但没用”的花架子。

正解DiskANN 是两阶段设计——PQ 码只在内存里做粗筛和导航，决定“往哪个方向走”；真正打分时，会把候选的完整向量从磁盘读回来精确计算距离。压缩只负责缩小搜索范围，不负责最终排名。实验中，PQ 导航 + 完整向量重排序的精度损失通常可以控制在 1~2 个百分点以内。迷你目录只帮你找书架，最终借哪本书还是要翻原书——精度由重排序兜底。

为何常见：只盯着压缩这一步的信息损失，忽略了检索管线的最后一步重排序设计，把“粗筛手段”误当成了“最终决策”。

误区既然 DiskANN 是“更先进”的方案，那所有向量检索场景都该无脑上 DiskANN，HNSW 迟早被淘汰。

正解两者是互补关系而非替代关系。HNSW 全内存、亚毫秒延迟，在千万级以下、QPS 要求极高的场景依然是首选；DiskANN 有磁盘 IO 开销，延迟在毫秒级，适合亿级以上、内存紧张的场景。选型的唯一标准是“内存账算不算得过来”。就像社区图书馆和国家总馆各有各的活法，你不能因为国家总馆的仓库方案先进，就让社区图书馆也去修地下仓库。

为何常见：把技术的演进线性外推成“新的必然取代旧的”，忽视了不同量级和延迟预算下各有最优解。

误区DiskANN 的核心不就是“把图放到磁盘上”吗？那内存里除了 PQ 码应该什么都不用管，缓存什么的都不重要。

正解DiskANN 的目标是“极小内存”而非“零内存”。真实场景中，热点节点和热门子图的访问高度集中，把高热度节点缓存在内存能命中一半以上的图访问，显著减少磁盘 IO。配合批量预取，缓存策略对 QPS 的影响可达数倍。周师傅的口袋里永远揣着最常被翻的推荐卡复印件——缓存不是可有可无，而是性能优化的第一杠杆。

为何常见：把“图存磁盘”理解成“完全抛弃内存”，忽略了检索热度分布的不均匀性，也忽略了缓存是 IO 型系统最经典的优化手段。

面试题

Q1. 十亿条 128 维 float32 向量仅存储向量本体需要多少内存？

单选题 · easy

  • A.约 50 GB
  • B.约 512 GB← 正确答案
  • C.约 5 TB
  • D.约 128 GB

答案：B。1e9 × 128 × 4 字节 = 512 GB，即每十亿条 128 维向量光“书的内容”就要 512GB“阅览室”，还没算图结构。这正是 HNSW 在十亿级场景下内存爆掉的直接原因，也是 DiskANN 用 PQ 码压缩的动机。

Q2. DiskANN 把主要数据结构分别放在哪里？

单选题 · easy

  • A.全部放在显卡显存
  • B.全部放在内存运行
  • C.图放磁盘 PQ 码在内存← 正确答案
  • D.数据在内存图在磁盘

答案：C。DiskANN 的核心分工是“图 + 完整向量上 SSD，PQ 压缩码驻内存”。D 把数据放内存是反的——完整向量 512GB 放不进去才需要 PQ 码，而 C 才是“小目录（内存）+ 大仓库（SSD）”的正确姿势。

Q3. DiskANN 搜索时在内存中用什么完成粗筛导航？

单选题 · easy

  • A.完整浮点向量
  • B.PQ 码距离表← 正确答案
  • C.倒排索引列表
  • D.内存哈希索引

答案：B。DiskANN 在内存里维护的是 PQ 压缩码和对应的距离查找表（LUT），查询时用查表累加得到近似距离来导航。完整浮点向量在磁盘上，倒排索引是 IVF 的机制，哈希表不提供近似最近邻能力。

Q4. PQ 压缩中，一条向量被切成 m 段、每段用 k 个质心量化，压缩后每条向量占用多少比特？

单选题 · mid

  • A.32d 比特
  • B.m×log₂k 比特← 正确答案
  • C.m×k 比特
  • D.k×log₂m 比特

答案：B。每段只需要记录“选了哪个质心”，所以每段占 log₂k 比特，m 段合计 m×log₂k。32d 是压缩前的位数，m×k 是码本大小而非码长。压缩比的公式 r = 32d / (m×log₂k) 正是由这个码长推导而来。

Q5. 关于 Vamana 图与 HNSW 的区别，下列说法正确的有？

多选题 · mid

  • A.Vamana 是单层大度数图← 正确答案
  • B.Vamana 需要多样性剪枝← 正确答案
  • C.HNSW 是单层小度数图
  • D.Vamana 跳数更多且每跳更省

答案：AB。Vamana 是单层图且出度 R 更大，构建时用“比已有邻居更靠近中心”的规则做多样性剪枝，保证邻居方向分散。HNSW 是多层跳表结构。Vamana 的图直径更小、跳数更少而非更多，D 说反了。

Q6. 以下哪些是 DiskANN 常用的性能优化手段？

多选题 · mid

  • A.热点节点内存缓存← 正确答案
  • B.批量预取邻居列表← 正确答案
  • C.全部节点载入显存
  • D.完整向量重排序← 正确答案

答案：ABD。热点缓存减少重复磁盘读，批量预取把多次随机读合并为大 IO，重排序用完整向量保证精度，三者都是 DiskANN 的标配。把全部节点载入显存违背了“省内存”的初衷，不现实也没必要。

Q7. DiskANN 为何选择 SSD 而非 HDD 作为图的存储介质？

单选题 · mid

  • A.顺序读写吞吐更高
  • B.随机读延迟远低于 HDD← 正确答案
  • C.随机读与 HDD 差不多
  • D.容量比 HDD 大很多

答案：B。图遍历的本质是大量随机读——每次跳转都要读任意位置的邻居列表。HDD 随机读延迟高达数毫秒，SSD 只有 50~100 微秒，差两个数量级。容量上 HDD 反而更大，关键差异是随机访问性能。

Q8. 某库有 1 亿条 128 维向量，HNSW 出度 R=32，估算总内存需求（含向量与邻接表）？

单选题 · hard

  • A.内存约 8 GB
  • B.内存约 25 GB
  • C.内存约 77 GB← 正确答案
  • D.内存约 128 GB

答案：C。代入公式 M = N×(d×4 + R×8) = 1e8×(512 + 256) = 7.68e10 字节 ≈ 77GB。其中向量本体约 51GB，图邻接表约 26GB。这个量级在单机内存里已经是“很贵”的存在，也是 DiskANN 想省掉的部分。

Q9. 哪些场景更适合选择 DiskANN 而非 HNSW？

多选题 · hard

  • A.十亿级商品向量召回← 正确答案
  • B.单机内存预算紧张← 正确答案
  • C.千万级亚毫秒延迟需求
  • D.图数据量极小可常驻内存

答案：AB。DiskANN 的定位是“大容量 + 小内存”，十亿级和内存紧张正是它的主场。千万级且要求亚毫秒延迟时 HNSW 优势明显；图小到能常驻内存时直接全内存方案即可，没必要引入磁盘 IO 的毫秒级开销。

Q10. 以下哪些因素会导致 DiskANN 召回率下降？

多选题 · hard

  • A.PQ 码本设置过小← 正确答案
  • B.波束宽度 L 过小← 正确答案
  • C.图出度 R 设置过大
  • D.重排候选集太小← 正确答案

答案：ABD。码本太小则质心粗糙，粗筛方向容易偏；波束宽度太小会漏掉正确路径；重排候选集太小把正确答案挡在门外。出度 R 过大反而让图更密、跳数更少，通常提升召回但增加构建开销，不会导致召回下降。