Bp-Tree: A Predictive B+-Tree for Reducing Writes on Phase Change Memory

Phase change memory (PCM) has been considered an attractive alternative to flash memory and DRAM. It has promising features, including non-volatile storage, byte addressability, fast read and write operations, and supports random accesses. However, there are challenges in designing algorithms for PCM-based memory systems, such as longer write latency and higher energy consumption compared to DRAM. In this paper, we propose a new predictive B+-tree index, called the B-p-tree, which is tailored for database systems that make use of PCM. Our B-p-tree reduces data movements caused by tree node splits and merges that arise from insertions and deletions. This is achieved by pre-allocating space on PCM for near future data. To ensure the space are allocated where they are needed, we propose a novel predictive model to ascertain future data distribution based on the current data. In addition, as in [4], when keys are inserted into a leaf node, they are packed but need not be in sorted order. We have implemented the B-p-tree in PostgreSQL and evaluated it in an emulated environment. Our experimental results show that the B-p-tree significantly reduces the number of writes, therefore making it write and energy efficient and suitable for a PCM-like hardware environment.