DiskANN 缓存算法深度解析：面向十亿级向量的高效磁盘索引
一、序言：当向量数据突破内存极限
随着大模型和多模态AI的普及，向量数据库需要处理的数据规模正从百万级向数十亿级跃迁。传统的内存索引（如HNSW）虽然搜索速度极快，但在十亿向量规模下，动辄TB级别的内存成本令人望而却步。纯磁盘方案又面临巨大的I/O延迟。DiskANN（Disk-based Approximate Nearest Neighbor）正是为解决这一矛盾而生的算法，它由微软印度研究院在2019年提出，凭借一套精巧的缓存设计，在SSD上实现了接近内存级索引的搜索性能。
DiskANN目前已集成进Qdrant的磁盘索引引擎中，成为大规模向量存储的核心竞争力。本文将深入剖析DiskANN的缓存算法——从Vamana图的分层布局，到缓存替换策略、预取机制和内存布局优化，并辅以源码级解读。
二、DiskANN缓存算法的背景
2.1 DiskANN的整体架构
DiskANN基于Vamana图（一种改进的HNSW图），关键创新在于将图数据分两部分存储：
全量数据存储在SSD上，包括所有点的完整向量和图邻接表。SSD容量大、成本低，每GB仅几分钱。
内存缓存仅保留搜索频繁访问的“热点”节点和入口点，大小可控（例如几十GB），从而以有限内存处理十亿级数据集。
搜索时，算法从图的高层入口开始，利用缓存节点的邻接信息跳转到磁盘上的点，按需加载向量和邻接表。一个高效的缓存策略，决定了搜索延迟和吞吐量。
