Research On Tree Indexes Based On Non-Volatile Memory

Non-Volatile Memory(NVM)is a new type of storage medium that has emerged in recent years.Due to its bit-addressability like traditional DRAM(and thus can be directly accessed by the CPU),as well as its non-volatile nature and large capacity,NVM offers new challenges and opportunities for current database systems based on the"DRAM+HDD" architecture.With the introduction of NVM into computer systems,core components of traditional database systems,such as indexes,buffer management,and storage management,need to be redesigned or optimized to utilize the characteristics of NVM.This thesis focuses on the access characteristics of NVM and the challenges it poses to database systems,with a particular focus on new index technologies for NVM.Specifically,based on the popular B+tree index in current database systems,this thesis proposes an optimized NVM-based B+ tree index scheme(including index structure and operation algorithms)and introduces a new tree-based index for NVM,which enables the B+tree index to adapt to both DRAM/NVM hybrid memory architecture and pure NVM memory architecture and to achieve better access performance.The main contributions of this thesis are summarized as follows:(1)We propose a new index structure called FI-tree(Fast-Insert Tree)for the DRAM/NVM hybrid memory architecture.In view of the persistent nature of NVM and its characteristic of slower write performance compared to read performance,this thesis proposes a new type of index structure called FI-tree that is optimized for DRAM/NVM hybrid memory architecture in database systems.FI-tree redesigns the leaf node structure stored in NVM,reducing the number of cacheline write-backs for each data write without affecting the node capacity,thereby reducing the average cost of a single insert operation.FI-tree also improves the splitting algorithm to reduce the overall number of splits and optimize the overall write performance.The experimental results on a real Intel Optane persistent memory platform show that FI-tree can achieve higher write performance while maintaining high read performance.(2)We propose a new index structure called Burger-tree for the NVM-only memory architecture.We explore the significance of the NVM-only memory architecture and propose a B+tree variant called Burger-tree.Burger-tree decouples the B+tree into three layers and designs cacheline-friendly node data structures and algorithms for each layer’s access characteristics to improve the overall read and write performance.The new index also maintains consistency for all operations,allowing it to be immediately used after system crashes.The experimental results on a real Intel Optane persistent memory platform show that the read and write performance of Burger-tree outperforms existing index structures for the NVM-only memory architecture.