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

Ping Chi, Wang Chien Lee, Yuan Xie

Research output: Contribution to journalArticlepeer-review

13 Scopus citations


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.

Original languageEnglish (US)
Article number7368150
Pages (from-to)1461-1474
Number of pages14
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Issue number9
StatePublished - Sep 2016

All Science Journal Classification (ASJC) codes

  • Software
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering


Dive into the research topics of 'Adapting B+-Tree for Emerging Nonvolatile Memory-Based Main Memory'. Together they form a unique fingerprint.

Cite this