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

邱海浪 等: LSMDiskANN: 更新友好型磁盘向量索引框架 1059

Key words: vector database; disk vector index; dynamic vector index; log-structured merge (LSM)

在“万物皆向量”的时代, 向量数据库应运而生. 各类模态的数据 (如文本、图像、视频等) 可以通过自然语言
处理、图像处理等深度学习模型转换为高维嵌入向量, 进而被深度学习模型利用, 实现多模态检索功能 [1–3] . 其中,
最基本且核心的查询操作是 K 近邻 (K-nearest neighbor, KNN) 查询. 向量数据库则用于存储和索引这些高维向量
并提供高效的 KNN 查询服务. 但是, 由于众所周知的“高维诅咒”问题 [4] , 在可接受的时间内获得精确的 KNN 结果
几乎是不可能的. 因此, 在向量数据库的应用场景中, KNN 查询通常指的是 K 近似近邻 (K-approximate nearest
neighbor, KANN) 查询. 过去 20 年中, 为提升向量查询效率, 研究者提出了多种向量索引技术, 主要可分为两类: 基
于图的索引 [5−8] 与基于分区的索引 [9−12] . 其中图索引由于其优越的搜索性能而备受青睐, 因此也成为本文研究的重
点方向.
然而, 目前主流的图索引方法大多基于内存构建与更新. 随着数据量持续暴涨, 仅依赖内存显然无法满足大规
模向量数据集的需求. 因此, 近年来出现了大量基于磁盘的向量索引研究 [11,13,14] , 这些研究通过向量压缩算法与导
航结构设计, 以较小的搜索性能损失换取低内存占用, 并控制磁盘 I/O 访问量, 从而实现高效的 KNN 搜索.
在数据量急剧增长的同时, 另一个核心挑战随之出现: 如何支持大规模向量更新. 如图 1 所示, 在典型的检索
增强生成 (retrieval-augmented generation, RAG) 场景中, 向量数据库背后的知识库需要持续动态更新, 这些更新可
能来自视频网站每日新增的视频数据 [15] 或是学术文献数据库的日常扩充 [16] 等. 围绕这方面的研究主要从以下两
点出发: (1) 动态向量索引算法的设计 [17−19] , 传统索引往往采用周期性重建的方式应对更新, 这类工作尝试在现有
索引结构上引入增量更新机制, 从而避免全量重建带来的高开销; (2) 面向高更新吞吐量的索引架构优化 [18,20,21] ,
这些工作则聚焦于调整索引布局与层次结构, 进而提高索引系统对高频写入与查询的支持能力.

私有知识库
向量数据库 多媒体
数据

向量化 文档
用户 大语言模型 查询提示 模型

结构化
数据
查询元素 查询向量
向量化
模型

图 1 RAG 场景示例

因此, 目前大部分专用向量数据库均建立于 NoSQL 数据库之上, 比如 Milvus [21] 、Qdrant [22] 和 Weaviate [23] . 通
过 LSM (log-structured merge) 树架构, 这些专用向量数据库实现了数据表的高写入吞吐、低内存占用与高效主键
点查找. 然而, 在这种架构中, 向量索引作为向量列的次级索引, 如何在不影响主表写入性能的前提下高效更新, 是
一个需要解决的关键问题.
[18]
为此, FreshDiskANN 被提出, 它是目前最具代表性的图结构磁盘向量索引方法之一, 也是 BIGANN-2023 比
赛 Stream Search 赛道的基准方法 [24] . FreshDiskANN 的架构类似单层 LSM 树, 采用 FreshVamana 算法, 在内存中
进行增量图构建, 并周期性地将其合并到磁盘索引中. 在向量搜索与更新问题上, 该算法展现了优秀的搜索与更新
性能. 然而, 我们在实验中观察到其仍存在以下不足. (1) 合并操作频率高: 每当内存索引写满时都会触发一次与磁
盘索引的合并, 造成过高的合并频率, 严重影响前台查询性能. (2) 磁盘 I/O 利用率低: 每次合并需要遍历磁盘索引
中所有向量点, 但根据 Greator [25] 的分析, 实际需要更新的点可能仅占 4%, 导致大量不必要的 I/O. (3) 合并操作中
删除阶段的磁盘 I/O 开销大: 整个合并过程的删除阶段需顺序扫描磁盘索引两趟, 带来额外的磁盘 I/O 开销.
针对上述问题, 本文提出了 LSMDiskANN, 一个以 FreshDiskANN 为基础的更新友好型磁盘向量索引框架. 为