非易失内存（non-volatile memory，NVM）为数据存储与管理带来新的机遇，但同时也要求已有的索引结构针对NVM的特性进行重新设计.围绕NVM的存取特性，重点研究了树形索引在NVM上的访问、持久化、范围查询等操作的性能优化，并提出了一种上下两层结构的异构索引HART.该索引结合了B+树与Radix树的特点，同时利用了Radix结点搜索快以及B+树范围查询性能好的优点.对整体架构进行了精心设计，改进了Radix树的路径压缩策略，设计了NVM写友好的结点结构，并将Radix树叶结点集中存储和链接.同时在仿真NVM设备以及傲腾真实NVM平台上进行了实验，对比了HART的不同衍生变种的性能，并与多个NVM索引进行了对比.结果表明，HART的写性能和点查询性能优于现有的类B+树索引，范围查询性能优于基于Radix的WOART索引，具有较好的综合性能.

Non-volatile memory (NVM) introduces new opportunities to data storage and management, but it also requires existing indices to be revisited according to the properties of NVM. This study, based on the access characteristics of NVM, focuses on the performance optimization of the access, persistence, range query, and other operations of tree indexes on NVM. A two-layer heterogeneous index called HART is presented. HART takes advantage of the high range query performance of the B+-tree and the fast node search speed of the Radix tree. The index structure is redesigned and the strategy of path compression for the Radix tree is improved. Moreover, a write-efficient node is proposed for NVM and the Radix leaf nodes together with a link are stored. The experiments are conducted on both simulated NVM and real Intel Optane persistent memory modules and different variants of HART are compared to several existing NVM indices. The results show that HART achieves better performance for point queries and writes than existing B+tree-like indices. In addition, it outperforms the existing Radix-tree-based WOART index in range query performance. As a result, HART can deliver high overall performance.

国家自然科学基金（62072419）