Research On The PCM-based B+-tree Index

With the high-speed technology development and the advent of big data era, data storage requirements and response time requirements are constantly improving. However, it is difficult to solve storage problems from the software perspective, and we need a new kind of storage medium to get rid of the restrictions of the mechanical properties of the disk. In recent years, with the progress in materials science, the new memory technologies develop rapidly. The emergence of new storage technology has brought new opportunities for the research on the efficient big data storage and management. Many researchers began to pay attention to non-volatile memory, which is represented by PCM, following the Flash study heat.PCM, as a current alternative new memory to DRAM, has attractive properties such as byte addressable, non-volatile, low energy consumption and big capacity, and causes great concern of scholars. However, the DRAM-based data management method is not available for the PCM-based memory database because the differences between PCM and traditional DRAM memory medium. First, DRAM is volatile storage medium and can be used to store the dynamic data in calculation process; while PCM is non-volatile, both dynamically calculated data and persistent static data such as files are suitable to PCM. Secondly, PCM cannot completely replace DRAM as main memory medium. Although PCM has fast read speed, its slow write operations and a limited number of write cycles make it still need DRAM to guarantee the performance in the storage infrastructure. Thus, the traditional memory data management mechanism cannot be used on PCM, including spatial distribution, storage organization and index. In this paper, we focus on the indexing algorithm, which is one of the in-memory data management mechanism, to discuss how to optimize the traditional indexing mechanism in order to make it efficient for the PCM-based memory data management.The main contribution of this paper can be summarized as follows:(1)We proposed the overflow B+-tree (OB+-tree) index read access optimization algorithm CB+-tree. This paper first defines the read and write tendency of leaf node, and analyze the methods of read and write tendency judgment. Then we elaborate the overflow chain adjustment policies using read and write tendency judgment mechanism, and present the query, insert and delete operations. Finally, comparative experiments show that the CB+-tree can effectively reduce the number of PCM read by 25%, and improve overall performance by approximately 15% on average, compared with OB+-tree.(2)We proposed an OB+-tree index optimization algorithm called XB+-tree using the auxiliary storage DRAM. Based on DRAM and PCM hybrid memory architecture, we use DRAM, which has high write performance, to compensate for the PCM shortcomings. The write tendency nodes need to migrate to DRAM with the using of read and write tendency mechanism. Meanwhile, we proposed the node management algorithm for small-capacity DRAM. Experimental results show that the XB+-tree can effectively reduce the PCM frequency of reading and writing. Compared with OB+-tree, the number of read and write to PCM decrease 31% and 64% respectively, the overall performance of the hybrid memory architecture also has improved by 38% on average.