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

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

数量有限, 从而实现内存占用与查询效率的平衡.
1.3 动态向量索引
伴随向量数据体量的迅猛增长, 其更新频率也呈现爆炸式提升. 例如, YouTube 每分钟有超过 500 h 的视频内
容上传 [44] , 京东每天有亿级的图像数据产生 [45] , 阿里巴巴在双十一期间产生超 500 PB 非结构化数据 [20] . 对于传统
向量索引, 处理更新的策略就是定期重建整个索引, 这在实际生产环境中成本极高, 种种需求催生了动态向量索引
的研究.
动态向量索引的研究方向主要包括两方面. (1) 一方面是改进现有索引算法, 使其支持更新操作, 从而避免频
繁重建整个索引. 这方面的两个代表性工作是微软提出的 SPFresh [17] 与 FreshDiskANN [18] , 二者分别基于 SPANN 和
DiskANN 拓展了更新能力. 前者解决了倒排索引在更新过程中倒排列表长度失衡问题; 后者解决了图索引更新效
率等问题. (2) 另一方面则聚焦于设计更适合高频更新场景的索引架构, 进而提升索引的吞吐量. 例如: AnalyticDB-V [20]
通过批处理层和流处理层的两层架构设计, 实现数据的对外无感更新, 但其底层向量索引仍是静态, 从而引发更新
性能问题; 作为典型 NoSQL 数据库, Milvus [21] 采用基于 LSM 的存储架构, 将数据表划分为多个分片, 并在每个分
片上构建静态向量索引, 在数据表进行合并时同步重建向量索引, 达到无感更新效果. 但是受限于嵌入式索引与数
据表高度耦合的缺点; FreshDiskANN 本质上可看作单层 LSM 结构, 其在内存中维护增量数据并定期合并至磁盘
主索引. 但是由于单层的限制, 每当内存索引写满时即需合并, 导致合并操作过于频繁, 严重影响前台查询性能.
此外, 近期还有两项针对 FreshDiskANN 的改进研究: IP-DiskANN [46] 为减少合并操作删除阶段的邻居修补开
销, 通过查询结果来近似删除点的入边邻居列表, 但该方法会不断累积逻辑删除的冗余边, 从而需要额外引入索引
的定期清理操作; Greator [25] 则引入图拓扑结构独立存储方案, 将图拓扑结构作为一种向量索引的索引, 结合局部更
新策略和近似剪枝策略提高小批量更新场景下的合并操作效率. 但是, 小批量更新场景的实际应用意义值得商榷,
且图拓扑结构的额外单独存储在大部分高维向量数据集下, 其所引发的额外存储开销比例不容小觑 (如 SIFT 中,
在邻居列表长度为 64 时, 比例为 50%). 总而言之, 上述两项研究均侧重于算法层面的调整与修改, 而本文的创新
则侧重于调整索引布局与架构设计, 因此彼此互补且不冲突.

1.4 LSM 次级索引
在 NoSQL 数据库中, 为支持大规模数据的高效写入, 同时兼具灵活性与可拓展性, 基于 LSM 的存储架构被
广泛采用. 其将主表存储设计为多层可合并的组件, 兼顾写入吞吐与查询性能. 但实际应用中, 除了主键查询, 往往
还需在非主键列上建立索引, 即“次级索引”. 如何保证次级索引在高写入负载下仍能高效更新, 成为 NoSQL 领域
的研究焦点 [47] . 其中, 一大解决方案则是将次级索引也 LSM 化, 这类索引统称为 LSM 次级索引, 包括: LSM 倒排
索引 [48] 、LSM B 树 [49] 、LSM R 树 [49−51] 等, 其中, 本文所提框架设计灵感则来源于 LSM R 树——用于支持空间数
据的 KNN 与范围查询的树索引结构, 在 Apache AxterixDB [49] 中有完整的开源实现.
在架构上, LSM R 树由内存层与磁盘层组成, 称为“组件”. 内存层组件包含 R 树与记录删除键的 B+树, 磁盘
层组件则额外加入布隆过滤器用于快速过滤删除标记. 当写入操作执行时, 数据首先写入内存组件, 内存组件写满
后刷新为磁盘组件. 当磁盘组件数量超过阈值 C 时, 将根据合并策略 (如 Constant 或 Prefix) 执行合并. 当 KNN 搜
索执行时, 需遍历所有组件, 按照生命周期从老到新逐个进行查询与删除键的过滤. 通过 LSM 化改造, AsterixDB
显著提升了读写混合场景下的系统吞吐与 QPS, 也为本文提出的基于 LSM 思想的磁盘向量索引框架提供了强有
力的可行性支撑.

2 基础知识

本文所提架构主要基于 FreshDiskANN [18] 进行改进, 下面就相关概念和系统基本过程予以介绍.
2.1 K 近似近邻查询
K 近邻 (KNN) 查询常用于从大规模数据集中检索与给定查询项相似的数据. 在向量数据库中, 数据以向量形
式表示, KNN 查询即为寻找与查询向量最接近的 K 个向量. 在实际应用中, KNN 查询广泛用于如下场景: (1) 检索