Rethinking self-balancing binary search tree over phase change memory with write asymmetry

Phase change memory (PCM) has become a promising candidate to replace DRAM in some massive/big data applications because of its low leakage power, non-volatility, and high density. However, most of the existing memory read/write intensive algorithms/designs are not aware of the endurance and write asymmetry issues of PCM. In particular, self-balancing binary search trees, which are widely used to manage massive data in the big-data era, were designed without the consideration of PCM characteristics and could degrade the memory performance. In this work, we rethink the design of self-balancing binary search trees, and propose a write-asymmetry-aware self-balancing tree to reduce the tree management overhead by decreasing the total/average number of bit flips of tree rotations with the consideration of the endurance and write asymmetry issues of PCM. Experimental results show that our solution significantly outperforms the original implementation of a self-balancing binary search tree, in terms of minimizing the total number of bit flips when the amount of data is large.