Research And Implementation Of A Non-volatile Memory Based Intelligent Index

Indexing techniques are essential to efficiently managing the explosive growth of data in this prosperous digital age.Most existing indexing schemes are based on B+ tree for DRAMs,while the DRAM capacity is reaching its limits,which hinders its further deployment in large volume storage systems.The emerging Non-Volatile Memory(NVM)devices provide on-pair performance with DRAM but having higher storage densities.Hence,NVMs are promising alternatives for the existing DRAMs.However,existing widely deployed B+tree index methods and their variants are not ready for the large volume NVMs,as their performance drops when the data size grows.The emerging Learned Index(LI)shows an efficient way to mitigate difficulties brought by data sizes,while existing LI techniques are also not optimized for NVMs.Aiming at the problem of how to use NVM to efficiently index massive data,a new intelligent index structure LI-Tree based on NVM is proposed.LI-Tree provides improved performance for both point queries and range queries.Specifically,LI-Tree consists of three layers: the LI-based model layer,the static routing layer,and the small B+tree forest layer.The model layer takes advantage of Learned Index philosophy,and efficiently partitions large data sizes into small sizes of which are managed by a small B+tree.A small B+tree with a low tree height is efficient for insert operations and both point and range queries.The static routing layer bridges the model layer and the forest layer,and it also reduces the training overhead for the model layer.Besides,LI-Tree crafts its expansions for the growing data size and consistent performance.On the real NVM memory device,the LI-Tree system prototype is implemented,and the performance is compared with Fast-Fair,a typical B+ tree index structure optimized for NVM.Evaluation results show that,when compared to B+tree indices,LI-Tree improves the performance of insertion,query,and deletion by up to 70%,30%,and 130%,respectively.Comparing to existing Learned Index methods,LI-TREE improves the insert performance by up to 150%.LI-Tree also sustains the high performance under growing data sizes.