R&D: Rethinking B-epsilon Tree Indexing Structure over NVM with Support of Multi-write Modes

ACM Digital Library has published, in ASPDAC ’25: Proceedings of the 30th Asia, an article written by Hui-Tang Luo, and Tseng-Yi Chen, National Central Univ., Taoyuan, Taiwan

Abstract: “The B^ϵ tree is an essential indexing structure in modern file and database systems, renowned for its high read and write performance. However, constructing a Bε tree involves substantial write overhead due to repetitive key writing during flushing. This study presents the mw-B^ϵ tree, a novel approach leveraging multi-write modes in persistent memory to reduce B^ϵ tree construction costs. By dynamically adapting write modes based on node update frequencies, the mw-B^ϵ tree outperforms traditional fixed-mode indexing schemes. Our research demonstrates that integrating multi-write mode support in non-volatile memory (NVM) can significantly enhance the efficiency of B^ϵ tree indexing. Experimental results using real-world workloads show that the mw-Bε tree reduces power consumption by up to 43.5% and energy usage by 27.6%, while also improving write latency. This work is the first to investigate and address power consumption challenges in Bε tree construction, providing a compelling case for the adoption of multi-write modes in NVM technologies for indexing structures.“