王永锋，陈志广

中山大学计算机学院，广东 广州 510006

1 引言

非易失性内存是一种新兴的存储介质，其具备字节可寻址、内存级别读写时延的特性，这给当前大量的存储系统带来了根本性的变革。非易失性内存正在迅速发展，现有的大部分非易失性内存（如相变内存[1]、STT-RAM[2]等）仍处于研究阶段，但由美光科技有限公司和英特尔联合研制的傲腾持久内存（基于3D XPoint[3]）已经发布，并且投入市场。由此，在存储系统中尽可 能发挥非易失性内存性能优势的需求越发迫切。其中，面向非易失内存研发新型持久索引数据结构是解决该问题的关键。

在存储系统的设计与实现中，持久索引数据结构是核心之一。文件系统中文件路径到索引节点的寻址、大文件中偏移量到指定数据块的寻址、键值存储系统中根据键寻找值的数据结构、数据库中的聚集索引等，都需要持久存储的索引数据结构，且这些持久索引数据结构的实现对系统本身的性能至关重要。但这些持久索引数据结构目前大多面向传统存储设备进行优化，而不能高效利用非易失性内存的硬件特性。将这些持久索引数据结构在非易失性内存上重新设计实现，并面向非易失性内存的硬件特性进行优化，能够大大降低存储系统的时延、提升吞吐量。

近年来，已经有一些工作对非易失性内存上的存储系统进行了深入的探讨和研究。陈游旻等人[4]在大数据环境下分析了基于新型存储硬件进行存储系统构建的挑战和趋势；……