Page 421 - 《软件学报》2025年第5期

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn
2025,36(5):2321−2341 [doi: 10.13328/j.cnki.jos.007198] [CSTR: 32375.14.jos.007198] http://www.jos.org.cn
©中国科学院软件研究所版权所有. Tel: +86-10-62562563

*
PLTree: 一个高性能持久化内存学习索引

张志国 1,2 , 谢钟乐 1,2 , 陈 珂 1,2 , 寿黎但 1,2

(区块链与数据安全全国重点实验室 (浙江大学), 浙江 杭州 310027)
1
2
(浙江大学 计算机科学与技术学院, 浙江 杭州 310027)
通信作者: 谢钟乐, E-mail: xiezl@zju.edu.cn

摘 要: 持久化内存 (persistent memory, PM) 作为主存的补充和替代, 为数据存储提供了相对较低的价格成本, 并
且保证了数据的持久化. 为 PM 设计的传统结构索引 (如 B+树等) 未能充分利用数据分布特点来发挥索引在 PM
上的读写性能. 最近的研究尝试利用学习索引的数据分布感知能力提升索引在 PM 上的读写性能并实现持久化.
但在面对真实世界的数据时, 现有基于 PM 的持久化学习索引的数据结构设计会导致额外的内存访问, 从而影响
读写性能. 针对 PM 学习索引在面对真实数据时读写性能下降的问题, 提出一种 DRAM/PM 混合架构的学习索引
PLTree. 它通过以下方法提升在 PM 上的读写性能并减轻数据分布颠簸对性能的影响: (1) 使用两阶段方法构建索
引消除内部节点的局部搜索, 减少 PM 的访问. (2) 利用模型搜索来优化 PM 上的查找性能并通过在 DRAM 存储元
数据加速查找. (3) 根据 PM 的特性设计了日志式分层溢出缓存结构, 优化写入性能. 实验结果表明, 在不同数据集
上, 与现有的持久化内存索引 (APEX, FPTree, uTree, NBTree 和 DPTree) 相比, PLTree 在索引构建性能上平均提升
了约 1.9–34 倍; 单线程查询/插入性能平均提升了约 1.26–4.45 倍和 2.63–6.83 倍; 在多线程场景, 查询/插入性能最
高提升了约 10.2 倍和 23.7 倍.
关键词: 学习型索引; 持久化内存; 持久化内存索引; 数据库
中图法分类号: TP311

中文引用格式: 张志国, 谢钟乐, 陈珂, 寿黎但. PLTree: 一个高性能持久化内存学习索引. 软件学报, 2025, 36(5): 2321–2341. http://
www.jos.org.cn/1000-9825/7198.htm
英文引用格式: Zhang ZG, Xie ZL, Chen K, Shou LD. PLTree: High-performance Learning Index for Persistent Memory. Ruan Jian
Xue Bao/Journal of Software, 2025, 36(5): 2321–2341 (in Chinese). http://www.jos.org.cn/1000-9825/7198.htm

PLTree: High-performance Learning Index for Persistent Memory
1,2
1,2
1,2
ZHANG Zhi-Guo , XIE Zhong-Le , CHEN Ke , SHOU Li-Dan 1,2
1
(State Key Laboratory of Blockchain and Data Security (Zhejiang University), Hangzhou 310027, China)
2
(College of Computer Science and Technology, Zhejiang University, Hangzhou 310027, China)
Abstract: Persistent memory (PM), serving as a supplement and potential replacement for main memory, offers a lower cost for data
storage while ensuring data persistence. However, traditional index structures tailored for PM like B+ trees fail to fully exploit the
distribution characteristics of data for optimizing reading and writing performance on PM. Recent research endeavors have sought to
enhance indexes’ reading and writing performance on PM and support index persistence through the data distribution awareness of learning
indexes. Nonetheless, existing designs of persistent learning index structures suffer from additional PM accesses and poor performance
when confronted with real-world data. To address the performance degradation of persistent learning indexes in the face of real data
distributions, this study proposes a learning index PLTree, a DRAM/PM hybrid architecture. PLTree optimizes reading and writing
performance under real data distributions through the following approaches: (1) a two-stage approach to construct the index, eliminating
last-mile search in internal nodes and reducing the access of PM, (2) model-based search for efficient query performance on PM and

* 基金项目: 浙江省尖兵研发攻关计划 (2024C01021); 浙江省科技创新领军人才计划 (2023R5214)
收稿时间: 2023-12-11; 修改时间: 2024-01-21, 2024-03-10; 采用时间: 2024-03-28; jos 在线出版时间: 2024-06-14
CNKI 网络首发时间: 2024-06-17