面向非易失内存的异构索引

作者：刘睿诚; 张俊晨; 罗永平; 金培权^*

来源：软件学报, 2022, 33(03): 832-848.

DOI：10.13328/j.cnki.jos.006456

• 非易失内存
• 索引
• 两层结构
• 读写优化
• ART树

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

• 单位
  中国科学院; 中国科学技术大学