想象你走进一座能装下十亿本书的超大图书馆。前台检索台（内存）又小又贵，只能放几十本常用书；真正的大书库（SSD）在地下仓库，容量巨大但找一本书要花更久。如果有读者说“我想看和这本风格相似的书”，管理员不可能把十亿本全搬上来一本本比较，那要等到闭馆。 DiskANN 就像一位聪明的图书管理员：他在仓库里给每本书都做了一张“指路卡”，卡片上只写几本风格相近的书的位置。读者来问时，他从门口的一张入口卡出发，沿着卡片上的线索一路抄近道，几步就走到目标附近。那些常被问到的入口卡放在前台缓存，避免每次都要下仓库翻箱倒柜。这就是 DiskANN 的直觉——把图索引放在 SSD 上，用少量内存缓存入口点和热数据，让十亿级向量的近邻搜索在单机上也能做到低延迟。在数据库系统设计中，它把“容量”和“速度”这对矛盾，用一张聪明的“指路网”化解了。

岗位关联

掌握 DiskANN，你就理解了现代向量数据库如何在磁盘上支撑十亿级检索，这是推荐、多模态搜索、云数据库等 AI 基础设施岗位的核心技能之一。

目录
  1. 可视化演示
  2. 为什么需要DiskANN
  3. 向量检索基础
  4. Vamana图构建
  5. 磁盘与缓存协同
  6. 搜索算法流程
  7. 索引构建与数据更新
  8. 性能评估与权衡
  9. AI 应用场景
  10. Python 演示
  11. 常见误区
  12. 面试题

可视化演示

展示系统处理流水线、实时性能指标曲线及多方案对比分析，包含数据流转、吞吐延迟监控与方案评估。

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

系统可视化 处理流程：输入→处理→模型→输出 性能监控：实时指标 P=L×T

为什么需要DiskANN

图书馆的检索台只能放几十本书，但真正的藏书在地下仓库里，数量以十亿计。向量检索面对的是同样的问题：每个对象被表示成一段数字向量，比如一本书的风格特征、一张图片的语义特征。如果所有向量都要放进内存，容量会很快耗尽。

假设有一亿条 100 维的浮点向量，每条向量要占 400 字节，总内存需求高达 40GB；如果到十亿条，就是 400GB。普通服务器内存既装不下，也买不起。SSD 虽然随机访问比内存慢，但容量大、价格低，能把图索引和数据都放进去。DiskANN 的核心思路就是“让大多数数据住在 SSD，只把最关键的一小部分留在内存”。

如果把全部书都堆在检索台上，图书馆早就塌了。DiskANN 的选择是把书搬进地下仓库，再用一张“指路网”告诉管理员怎么快速找到想看的书。这种“大容量存储 + 图索引 + 少量缓存”的搭配，正是数据库系统设计中应对超大规模向量检索的常用思路。

内存需求=N×d×4 字节\text{内存需求}=N \times d \times 4\ \text{字节}
这个公式告诉你：向量数量 N 和维度 d 一旦上亿，内存就会爆炸，必须把存储重心移到磁盘。
  1. N向量条数：表示库里有多少条向量数据，十亿级数据的 N 是 10⁹。
    N=109N = 10^9
  2. d向量维度：每条向量有几个数字，例如 100 维。
    d=100d = 100
  3. 4 字节单个浮点数的占用：每个维度通常用 32 位浮点数存储，算下来就是 400GB 级内存需求。
    N×d×4=109×100×4=400GBN \times d \times 4 = 10^9 \times 100 \times 4 = 400\text{GB}

向量检索基础

读者说出“我想看某本书”，管理员不能只看封面，还要理解这本书“像什么”。在向量检索里，这个“像什么”就是一串数字：向量。两本书像不像，取决于两个向量的距离近不近。距离越近，说明它们越相似。

最朴素的做法是暴力扫描：把仓库里的每本书都拿来和读者需求算一遍距离，然后挑出距离最小的 K 本。这个办法虽然准确，但十亿本书就意味着十亿次距离计算，单机根本扛不住。于是我们需要“索引”来减少计算量，而图索引是其中很高效的一类。

没有索引时，管理员要一本本翻书；有了 K 近邻的概念，就能明确“最近”的定义。但暴力扫描仍然像把整座仓库翻个底朝天，所以才需要 DiskANN 用图来“抄近路”。

d(q,p)=∑i=1d(qi−pi)2d(q,p)=\sqrt{\sum_{i=1}^{d}(q_i-p_i)^2}
这就是最常用的欧氏距离，用来衡量查询向量 q 和候选向量 p 有多接近。
  1. q_i 与 p_i查询向量和候选向量的第 i 个分量，相当于两本书在第 i 个特征维度上的取值。
    qi, piq_i, \ p_i
  2. 求差平方先算每个维度上的差距，再平方，避免正负抵消。
    (qi−pi)2(q_i - p_i)^2
  3. 求和开根号把所有维度的差距累加后开平方，得到两点间的直线距离。
    ∑i=1d(qi−pi)2\sqrt{\sum_{i=1}^{d}(q_i-p_i)^2}

Vamana图构建

为了让管理员少跑路，DiskANN 使用了一套叫 Vamana 的图构建算法。它把每个向量当成图里的一个节点，每个节点只连接少量“风格相近”的邻居。这张图不是把所有相似关系都画出来，而是刻意裁剪，保证图既稀疏，又能提供足够的“捷径”。

Vamana 构建时会给每个节点找一批候选邻居，再按距离从近到远连接。它还会保留一些特别长的边，这些长边就像图书馆走廊里的快速通道，能让搜索从图的一端快速跳到另一端。参数 R 控制每个节点最多保留多少条出边，R 越小，图越稀疏，存储和 IO 越省；R 越大，图越密集，搜索路径可能更短。

构建完图，管理员还要选出“入口点”——一般是离所有节点都比较近的中心节点。它相当于图书馆门口的导览台，搜索时从这里起步。Vamana 图用有限的边和长距离捷径，让“地下仓库”也能快速导航。

∣E∣=O(N×R)|E| = O(N \times R)
这张图的总边数大约等于节点数乘以平均出边数，因此是稀疏的，可以存放在 SSD 上。
  1. N图的节点数：每个向量对应一个节点。
    N=109N = 10^9
  2. R最大出边数：每个节点最多连向 R 个邻居，是控制图体积的关键参数。
    R=32R = 32
  3. O(N×R)线性级别的边规模：边数不会随着 N 变成平方级，所以图可以被持久化到磁盘。
    ∣E∣=O(N×R)|E| = O(N \times R)

磁盘与缓存协同

图在 SSD 上，但每次搜索都要从磁盘读节点，速度仍然不够。于是 DiskANN 做了两个聪明的安排：第一，把入口点显式缓存在内存里，这样每次查询的第一跳不需要访问磁盘；第二，依赖操作系统的页缓存，把频繁访问的热门节点留在内存中。

这就像管理员把最常用的几本推荐书放在前台，读者来了直接就能拿到。SSD 的随机读虽然比内存慢，但只要搜索只访问几十个节点，并且能按批次读取，就不需要把整张图都读进内存。DiskANN 会把相邻节点尽量存在同一批页面里，一次 IO 读回多个节点，从而摊薄延迟。

缓存不是把整座图书馆搬进前台，而是只放“入口卡”和“热门卡”。DiskANN 用这种手段把磁盘 IO 降到了可接受的范围，让 SSD 上的图索引实际跑起来依然很快。

IO平均≈∣V访问∣−∣V命中∣BIO_{平均} \approx \frac{|V_{访问}| - |V_{命中}|}{B}
搜索访问的节点越多，缓存命中的节点越多，单次 IO 读入的节点越多，磁盘访问次数就越少。
  1. V_访问搜索时碰到的节点总数：每一步贪心路由都会打开若干邻居节点。
    ∣V访问∣|V_{访问}|
  2. V_命中已经在内存缓存中的节点数：入口点和热门节点不用再下仓库读。
    ∣V命中∣|V_{命中}|
  3. B一次批量读入的节点数：把多个节点打包在一个 IO 里，相当于一次搬一摞书而不是一本本搬。
    IO平均≈∣V访问∣−∣V命中∣BIO_{平均} \approx \frac{|V_{访问}| - |V_{命中}|}{B}

搜索算法流程

当读者提出查询时，管理员从内存里的入口点出发，查看这个节点的邻居，计算每个邻居与查询向量的距离，然后走向距离最近的那个。这个过程不断重复：每到一个新节点，就看它周围有没有更近的邻居；如果所有邻居都比当前节点更远，就停下来，把当前节点作为答案。

为了更稳，DiskANN 在实际搜索时会维护一个候选集，同时保留多个“有希望”的节点，而不是只走一条路。每一步都从候选集中取出最优点，再把它的未访问邻居加进去，按距离排序。这就是贪心路由加上束搜索，既快又不容易陷进局部死胡同。

这张“指路网”不需要看完全部空间，只沿着几个方向试探。近似搜索看似“偷懒”，但因为有长边捷径和候选集，实际能很快逼近真正的近邻。

vnext=arg⁡min⁡u∈N(vcur)d(u,q)v_{next} = \arg\min_{u \in \mathcal{N}(v_{cur})} d(u, q)
每一步都选“离查询最近的未访问邻居”，这是图索引搜索的核心动作。
  1. v_cur当前所在节点：搜索路径上此刻站着的图书节点。
    vcurv_{cur}
  2. N(v_cur)当前节点的邻居集合：Vamana 图中与当前节点相连的候选书。
    N(vcur)\mathcal{N}(v_{cur})
  3. argmin找最小距离对应的节点：在邻居里挑一个距离查询最近的节点，作为下一步。
    vnext=arg⁡min⁡u∈N(vcur)d(u,q)v_{next} = \arg\min_{u \in \mathcal{N}(v_{cur})} d(u, q)

索引构建与数据更新

图书馆不会永远只有旧书，新书会不断上架，旧书也会下架。DiskANN 的图索引同样需要支持更新。新向量加入时，先在图里做一次搜索，找到距离它最近的几个节点，然后把新节点与这些节点连起来，增量地挂到图上；删除向量时，不会立刻物理抹掉，而是先打上一个“墓碑”标记，让查询不再返回它。

墓碑多了会浪费空间，所以系统会定期压缩：把有效数据重新写一遍，去掉无效标记，并重建相关边。此外，DiskANN 还常用乘积量化（PQ）压缩向量本身，把每个维度占用的空间从 4 字节压缩到更少，从而减少磁盘读取量。这些策略让索引既能持续更新，又能控制存储成本。

对读者来说，新书一上架就能借，下架的书也不会再出现。管理员不需要每晚重画整张图书馆地图，只需要定期整理那些“暂停借阅”的旧书位，这就是 DiskANN 在动态数据场景下的优雅之处。

U=NliveNlive+NtombstoneU = \frac{N_{live}}{N_{live} + N_{tombstone}}
空间利用率等于有效数据占总数据的比例，墓碑越多，利用率越低，越需要压缩整理。
  1. N_live有效向量数：还没被删除、能正常参与检索的节点。
    NliveN_{live}
  2. N_tombstone墓碑标记数：已经逻辑删除但还没物理清理的节点。
    NtombstoneN_{tombstone}
  3. U空间利用率：这个比例越低，说明无效数据越多，系统应该触发压缩。
    U=NliveNlive+NtombstoneU = \frac{N_{live}}{N_{live} + N_{tombstone}}

性能评估与权衡

如何衡量这套指路网好不好？一是“找得全不全”，二是“找得快不快”。找得全用召回率衡量：假设精确搜索能找到 K 个真正最近邻，近似搜索返回的 K 个结果里，有多少个是真正近邻。找得快用 QPS 衡量，也就是每秒能处理多少个查询请求。

DiskANN 和内存索引 HNSW 经常被拿来对比。HNSW 是多层图，主要面向内存；DiskANN 是单层图，面向 SSD。DiskANN 牺牲了一部分极致延迟，换来了更大的容量和更低的内存成本。十亿级向量在单机上做到低延迟，本身就是一种权衡后的胜利。

把书放到地下仓库，并不意味着一定找不到；只要指路网设计得足够好，管理员依然能快速、精准地把书放到读者面前。DiskANN 的终极目标，就是用更少的内存，换来接近内存索引的召回和可接受的延迟。

Recall@K=∣Rexact∩Rapprox∣K\text{Recall@K} = \frac{|\mathcal{R}_{exact} \cap \mathcal{R}_{approx}|}{K}
召回率越高，说明近似检索丢失的真正近邻越少。
  1. R_exact精确近邻集合：暴力扫描得到的前 K 个真正最近邻。
    Rexact\mathcal{R}_{exact}
  2. R_approx近似检索结果集合：DiskANN 在图上搜索返回的前 K 个结果。
    Rapprox\mathcal{R}_{approx}
  3. 交集大小除以 K返回结果中有多少比例是真的最近邻。
    ∣Rexact∩Rapprox∣K\frac{|\mathcal{R}_{exact} \cap \mathcal{R}_{approx}|}{K}

AI 应用场景

推荐系统候选召回

阶段：召回阶段（Retrieval）

解决的问题：传统推荐系统在召回时要从数亿商品中找出用户可能感兴趣的物品，如果全部放入内存，成本极高；DiskANN 把商品向量放到 SSD 上，用图索引快速筛出候选集，再把候选交给精排模型。

具体案例：某短视频平台有十亿条视频 embedding，用户请求到达后，先用 DiskANN 在百毫秒内召回几千条相关视频，再经过粗排、精排输出最终推荐列表。

图片与视频去重

阶段：特征匹配与去重

解决的问题：海量 UGC 内容中重复或近似重复的图片、视频需要被识别，暴力两两比对在十亿规模下不可行；DiskANN 能按向量相似度找到同一内容的多个拷贝。

具体案例：内容平台每天上传千万级图片，系统为每张图生成 embedding 后写入 DiskANN 索引，上传时检索是否存在重复内容，命中后自动打标或拦截。

云数据库内置向量检索

阶段：数据库查询加速

解决的问题：数据库系统希望能像跑 SQL 一样跑“找相似”查询，但传统 B+ 树不擅长高维相似度检索；DiskANN 作为向量索引组件，可以与数据库存储引擎结合，让 SQL 查询和向量检索在同一个系统内完成。

具体案例：云数据库产品在表字段上创建 DiskANN 向量索引，用户执行“ORDER BY 向量距离 LIMIT 10”时，数据库自动走磁盘图索引，避免全表扫描。

Python 演示

python53 行
import mathimport random def euclidean(a, b):    return math.sqrt(sum((x - y) * (x - y) for x, y in zip(a, b))) def add_edge(graph, u, v):    if v not in graph[u]:        graph[u].append(v)    if u not in graph[v]:        graph[v].append(u) def build_vamana(points, R=3):    n = len(points)    graph = [[] for _ in range(n)]    for i in range(n):        cand = sorted(range(n), key=lambda j: euclidean(points[i], points[j]))        for j in cand[1:R + 1]:            add_edge(graph, i, j)    return graph def greedy_search(graph, points, query, start, beam=5, steps=6):    visited = {start}    frontier = [start]    for _ in range(steps):        nxt = []        for node in frontier:            for nb in graph[node]:                if nb not in visited:                    visited.add(nb)                    nxt.append(nb)        if not nxt:            break        nxt.sort(key=lambda v: euclidean(points[v], query))        frontier = nxt[:beam]    candidates = frontier + [start]    return min(candidates, key=lambda v: euclidean(points[v], query)) def main():    random.seed(42)    points = [[random.random() for _ in range(8)] for _ in range(80)]    graph = build_vamana(points, R=4)    query = [random.random() for _ in range(8)]    hit = greedy_search(graph, points, query, start=0, beam=5, steps=8)    exact = min(range(80), key=lambda i: euclidean(points[i], query))    d_hit = euclidean(points[hit], query)    d_exact = euclidean(points[exact], query)    print("greedy hit:", hit, "distance:", round(d_hit, 4))    print("exact best:", exact, "distance:", round(d_exact, 4))    print("ratio:", round(d_hit / d_exact, 4)) if __name__ == "__main__":    main()
目的：用随机向量模拟一个简化版 Vamana 图，并在这个图上做贪心搜索，演示 DiskANN“从入口点沿图找近邻”的核心流程。
  1. graph = build_vamana(points, R=4)每个节点只连接距离最近的 4 个邻居，形成一张稀疏图。
  2. greedy_search(graph, points, query, start=0, beam=5, steps=8)从第 0 个节点出发，用束搜索维护多条候选路径。
  3. nxt.sort(key=lambda v: euclidean(points[v], query))把邻居按到查询向量的距离排序，模拟贪心选点的逻辑。
  4. frontier = nxt[:beam]只保留距离最近的 beam 个节点，控制每一步的搜索宽度。
  5. min(candidates, key=lambda v: euclidean(points[v], query))在走过的所有节点中，返回离查询最近的一个作为结果。

常见误区

误区索引都放到 SSD 上了，搜索时肯定要把图从磁盘搬进内存，精度和速度一定不如 HNSW 这类内存索引。

正解DiskANN 的图搜索只访问从入口点出发的一小部分节点，而不是全图扫描。加上长边捷径、候选集和批量读取，实际访问的节点数可能只有几十到几百。它能在召回率接近内存索引的同时，让十亿级向量只占很小的内存。

为何常见：人们容易把“容量大”和“速度慢”直接划等号，忽略了图索引的访问模式是稀疏的。

误区DiskANN 把所有东西都放到了磁盘上，所以内存占用可以是零。

正解DiskANN 仍然需要内存存放入口点、图搜索过程中的候选集、以及操作系统页缓存里的热门节点。它只是把“全部向量都在内存”变成“只缓存关键节点”，把内存需求从几百 GB 降到几 GB。

为何常见：名字里的“磁盘”二字容易让人误以为内存没用了，实际上缓存协同正是它的核心设计之一。

误区图索引放在 SSD 上，每秒处理查询时肯定要把图的所有边都扫一遍。

正解搜索是贪心路由加束搜索，从入口点开始，每一步只考察当前节点和候选集中的邻居。它不会遍历全图，而是沿着一条狭窄的“搜索路径”前进，直到邻居都不再更优。

为何常见：把“图”想象成了链表或全表，忘了图检索的本质是局部探索。

误区Vamana 和 HNSW 都是图索引，只是名字不同，随便叫什么都行。

正解HNSW 是多层跳表式图结构，主要面向内存；Vamana 是单层图，用 R 控制出边、用 α 保留长边，并且针对 SSD 的批量读取做了裁剪。两者的搜索策略和 IO 特征有明显差异。

为何常见：看起来都是“画点连线”，但一层的捷径设计和多层的分层导航，在磁盘场景下区别很大。

误区PQ 压缩把向量精度降低了，检索结果肯定乱七八糟。

正解压缩只用于估算距离和减少 IO，图结构本身仍然保留；实际系统中可以先用量化向量快速筛选，再用原始向量做最终重排，把精度损失控制在很低的水平。

为何常见：看到“有损”两个字，就会担心结果不可用，忽略了工程上的重排校正手段。

面试题

Q1. DiskANN 被设计用来解决什么问题？

单选题 · easy

  • A.内存放不下十亿级向量的近邻检索← 正确答案
  • B.提升 CPU 的浮点运算速度
  • C.替代关系型数据库的事务功能
  • D.增加 SSD 硬盘的物理存储容量

答案：A。DiskANN 的核心目标是让超大规模向量索引不再依赖昂贵内存，而是放到 SSD 上仍能高效近邻检索。B 不是索引问题，C 是数据库事务问题，D 是硬件物理容量问题，都不是它的设计动机。

Q2. 在向量的 K 近邻检索中，召回率 Recall@K 描述的是？

单选题 · mid

  • A.返回结果中正确结果的比例
  • B.真实近邻有多少被返回覆盖← 正确答案
  • C.近似距离与精确距离的比值
  • D.检索请求每秒成功次数

答案：B。召回率关注“该找到的有没有被找到”，即真实 K 近邻中有多少出现在返回结果里。A 更像精确率，C 是距离误差，D 是 QPS。

Q3. 以下哪些做法能帮助 DiskANN 减少磁盘 IO？

多选题 · mid

  • A.将入口点放在内存缓存中← 正确答案
  • B.对访问节点做批量读取← 正确答案
  • C.把所有向量都加载进内存
  • D.构建稀疏图减少无效邻居← 正确答案

答案：ABD。入口点缓存避免首跳读盘，批量读取把多次 IO 合并成一次，稀疏图减少搜索时要打开的邻居数。C 把所有向量加载进内存违背 DiskANN 的磁盘设计初衷。

Q4. Vamana 图构建时使用 R 参数主要控制什么？

单选题 · mid

  • A.每个节点最多保留的出边数← 正确答案
  • B.查询请求返回的向量个数
  • C.向量数据的浮点精度位数
  • D.SSD 随机读的等待时间

答案：A。R 是 Vamana 图中每个节点的最大出边数，决定图的稀疏程度。K 近邻的 K 才控制返回数量，向量精度由数据类型决定，SSD 等待时间与 R 无关。

Q5. 贪心搜索在图索引上移动时，每一步会选择哪个邻居？

单选题 · hard

  • A.与当前节点距离最近的邻居
  • B.与查询向量距离最近的邻居← 正确答案
  • C.与入口点距离最近的邻居
  • D.随机选择一个未访问邻居

答案：B。贪心搜索的目标是逼近查询向量，所以每一步都看邻居中谁离查询最近。A 只看当前节点会丢失方向，C 会一直围绕入口点，D 没有利用距离信息。

Q6. 关于 DiskANN 的搜索过程，下列说法正确的是？

多选题 · hard

  • A.从缓存入口点开始贪心游走← 正确答案
  • B.通过候选集维护多个备选节点← 正确答案
  • C.必须访问图中每一个节点
  • D.可用量化向量近似计算距离← 正确答案

答案：ABD。DiskANN 从入口点出发，用候选集做束搜索，并且可以用压缩向量快速估算距离。它不需要访问所有节点，所以 C 错误。

Q7. 为什么 DiskANN 能把图索引放在 SSD 而不是内存？

单选题 · easy

  • A.SSD 容量大且随机读足够快← 正确答案
  • B.SSD 比内存访问延迟更低
  • C.SSD 不需要缓存入口点
  • D.SSD 能消除所有近似误差

答案：A。SSD 容量大、成本低，且随机读性能足以支撑“访问少量节点”的图搜索。内存延迟其实比 SSD 更低，所以 B 错误；入口点和误差问题依然存在。

Q8. DiskANN 中的量化（PQ/压缩）主要目标是？

单选题 · mid

  • A.减小向量占用空间从而减少读写成本← 正确答案
  • B.提高向量的维度增加表达能力
  • C.将向量转化为关系数据库的表
  • D.强制所有向量变成整数向量

答案：A。PQ 压缩的动机是降低向量存储和 IO 开销，让 SSD 上的索引更省空间。它不会提高维度，也不会把向量变成数据库表。

Q9. 在 DiskANN 中，入口点缓存为什么能显著降低延迟？

单选题 · hard

  • A.避免每次搜索都从磁盘读取起点← 正确答案
  • B.入口点中存有全部向量数据
  • C.入口点是距离查询最近的唯一答案
  • D.入口点数量等于向量总数

答案：A。每次查询都要从入口点起步，如果入口点在内存里，第一跳就不需要访问 SSD，省掉了最稳定的固定延迟。入口点只是一个导航起点，不是全部数据，也不是唯一答案。

Q10. 数据更新场景下，DiskANN 常见的设计策略包括？

多选题 · extreme

  • A.新向量增量加入图并连接邻居← 正确答案
  • B.删除时先用墓碑标记逻辑删除← 正确答案
  • C.每次更新必须重建全部图索引
  • D.周期压缩清理墓碑并重写文件← 正确答案

答案：ABD。增量插入、墓碑标记、周期压缩是磁盘索引常用的更新组合。每次更新都重建全图代价太高，所以 C 错误。