Adapting B⁺-Tree for Emerging Nonvolatile Memory-Based Main Memory

Among the emerging nonvolatile memory (NVM) technologies, some resistive memories, including phase change memory (PCM), spin-Transfer torque magnetic random access memory (STT-RAM), and metal-oxide resistive RAM (ReRAM), have been considered as promising replacements of conventional dynamic RAM (DRAM) to build future main memory systems. Main memory databases can benefit from their nice features, such as their low leakage power and nonvolatility, the high density of PCM, the good read performance and low read energy consumption of STT-RAM, and the low cost of ReRAM's crossbar architecture. However, they also have some disadvantages, such as their long write latency, high write energy, and limited lifetime, which bring challenges to database algorithm design for NVM-based memory systems. In this paper, we focus on the design of the ubiquitous B⁺-Tree, aiming to make it NVM-friendly. We present a basic cost model for NVM-based memory systems which distinguishes writes from reads, and propose detailed CPU cost and memory access models for search, insert, and delete operations on a B⁺-Tree. Based on the proposed models, we analyze the CPU costs and memory behaviors of the existing NVM-friendly B⁺-Tree schemes, and find that they suffer from three issues. To address these issues we propose three different schemes. Experimental results show that our schemes can efficiently improve the performance, reduce the memory energy consumption, and extend the lifetime for NVM-based memory systems.