Page 29 - 《软件学报》2026年第3期

992 软件学报 2026 年第 37 卷第 3 期

混合索引结构. SPANN 在内存中存储倒排列表的质心点作为粗粒度索引, 并将大规模原始数据划分到磁盘中的倒
排列表, 图 10 展示了其基本的结构. 索引构建阶段采用分层平衡聚类算法, 通过多约束优化将数据递归划分为均
匀的子集, 控制单个倒排列表的最大长度, 从而降低单次磁盘访问开销. 针对边界向量易丢失的问题, 提出闭包多
簇分配策略: 对靠近多个簇质心的边界点进行复制存储 (如最多 8 个副本), 提升其召回概率. 该方法在保持倒排列
表长度平衡的同时, 仅增加 20% 存储开销即可有效缓解近邻搜索的边界效应问题.

中心点 倒排列表
. . .
V 1 V 4 V 5
. . .
V 2 V 5 V 7
. . .
V 6 V 5 V 8
内存 磁盘
图 10 基于文献 [67] 展示的 SPANN 的索引结构

在查询优化方面, SPANN 设计了查询感知的动态剪枝机制. 搜索时优先从内存中的 SPTAG 索引 (基于空间
划分树与近邻图) 快速定位 K 个最近质心, 然后根据查询与质心的距离动态调整候选列表: 仅访问与最近质心距
离相差在阈值范围内的倒排列表 (如设定相对误差阈值 ε = 0.6). 这种自适应策略使得不同难度的查询获得差异化
的搜索深度, 相比于固定候选数策略减少 40% 磁盘访问. 与 DiskANN 对比, SPANN 在相同 32 GB 内存配置下实
现 2 倍加速, 召回率超过 90%. 在分布式场景中, 通过多约束平衡分片与查询负载预测算法, 将 10 亿级数据均匀分
布到 32 台机器, 使单查询平均访问机器数降至 6.3 台, 比随机分片降低 80% 计算开销.
3.4.2 基于图和量化的方法
[36]
DiskANN 是基于 SSD 的图索引方案, 其核心是新型图索引算法 Vamana. 该算法通过引入可调节参数 α (α ⩾ 1)
优化图结构直径, 在保证高召回率的同时减少搜索路径长度. 与 HNSW 和 NSG 相比, Vamana 的图结构在 10 亿级
数据规模下可将搜索路径的磁盘随机访问次数降低到 1/3–1/2, 同时支持通过参数 α 灵活平衡图密度与搜索效率.
与 HNSW 等传统图索引相比, Vamana 通过调节 α 参数实现了更灵活的图密度与路径长度平衡. 此外, Vamana 在
构建过程中采用反向边插入策略, 增强图的连通性, 避免局部最优陷阱.
DiskANN 通过分片和内存-磁盘混合索引存储的策略, 将 10 亿级索引部署于单节点的 64 GB 内存与 SSD 组
合环境中. 首先, DiskANN 采用分治的策略, 通过 K-means 聚类将数据集划分为 40 个子集, 每个数据点分配至最
近的 2 个子集, 并在各子集上独立构建 Vamana 子图索引; 最终合并所有子图形成全局索引, 确保跨子集的查询路
径连通性. 其次, DiskANN 结合量化压缩与全精度缓存降低内存占用; 使用乘积量化 (PQ) 将向量压缩至 32 字节
存储于内存, 同时在 SSD 中保存全精度向量与图结构. 搜索时, 通过束搜索批量预取多个节点的邻居信息, 减少
SSD 随机访问次数; 并利用 SSD 的 4 KB 对齐读取特性, 将全精度向量与邻接列表存储于同一磁盘扇区, 实现隐式
重排序 (implicit re-ranking), 以压缩向量引导搜索方向, 最终通过全精度距离计算提升召回率. 此外, DiskANN 采
用热点缓存策略, 将距离搜索起点 3–4 跳内的节点数据预加载至内存, 进一步减少磁盘 I/O. 实验结果表明,
DiskANN 在 SIFT1B 数据集上仅需 348 GB SSD 空间与 64 GB 内存, 即可支持每秒 5 000+次 recall@1 达 95% 以
上的查询. 这种“内存压缩+SSD 原始向量”的混合存储模式为 10 亿级 ANNS 任务提供了高精度、低延迟与低成
本的单机解决方案. 此外, Starling [142] 是一个基于图的磁盘内存索引方案. 它分为磁盘和内存索引两部分, 内存部分
通过采样来建立摘要图以实现快速定位到查询区域附近, 而磁盘部分采用数据重排序来提升数据的局部性访问以
降低磁盘 I/O.
SPANN 和 DiskANN 均通过粗粒度内存索引引导细粒度磁盘访问解决 I/O 瓶颈. SPANN 以倒排索引为核心,
通过数据均匀划分、边界点冗余和动态剪枝优化磁盘访问效率, 在低延迟和低内存场景下优势显著, 且构建速度
更快, 但需要存储点的冗余副本数据, 因此比较消耗磁盘空间. DiskANN 以图索引为基石, 结合量化压缩与硬件特