Research On B~+-Tree Based Efficient Indexing Structure For Non-Volatile Memory

With the popularity of 5g high-speed mobile network technology,the large-scale use of mobile terminals makes the explosive growth of data volume,and the application puts forward higher requirements for the data storage scale and access performance of the system.The emergence of new non-volatile memory(NVM)provides new opportunities for efficient storage and modification of tree structure-based indexes.However,the traditional tree structure can not make full use of the characteristics of NVM because it will migrate a large number of entries in nodes,resulting in serious performance degradation and NVM lifetime loss.Improved solutions such as NV-Tree keep only leaf nodes in NVM to reduce the number of NVM writes.However,frequent upper-level node reconstruction operations by NV-Tree will cause greater memory consumption and management overhead.To solve the above problems,this thesis proposes a non-volatile and efficient index structure based on B~+-tree under hybrid storage architecture,which is called Marionette Tree(MT-Tree).Its main purpose is to minimize the memory overhead,reduce the use of memory resources,and reduce the wear and tear of the NVM,and improve the service life of the NVM.The main contributions of this article are as follows:Firstly,to reduce the data consistency overhead of index structure and the number of NVM writes,this thesis adopts a hybrid storage architecture,including discrete non-leaf nodes stored in DRAM,shadow arrays storing non-leaf node pointers,and leaf nodes persistent on NVM.Such a hybrid storage architecture can not only improve the performance of MT-tree but also significantly reduce the number of NVM writes and improve the service life of NVM.Secondly,this thesis designs a delayed split mechanism to further optimize the performance of MT-Tree and minimize the management overhead of shadow arrays.This solution delays the splitting of non-leaf nodes by migrating the key-value pairs in the parent leaf node(the parent node of the leaf node),thereby reducing the number of modifications and reconstruction of the shadow array.Thirdly,for the data consistency problem based on NVM,this thesis designs a data consistency mechanism for each basic operation of MT-Tree,and proposes a corresponding recovery mechanism when the index structure appears inconsistent during operation.Finally,this thesis implements the prototype structure of MT-Tree and conducts experimental verification in a workstation equipped with a Linux system.At the same time,performance experiments,memory overhead,and wear level experiments were carried out using YCSB workload.The experimental comparison objects are the typical NVM-based index structure NV-Tree and FAST+FAIR.The experimental results show that the performance of MT-Tree in operation is better than NV-Tree and FAST+FAIR.Besides,the peak memory overhead of MT-Tree is only 0.3%of NV-Tree,and the maximum NVM write times of NV-Tree and FAST+FAIR are 17.1 times and 258.48times that of MT-Tree,respectively.