CAWBT: NVM-Based B+Tree Index Structure Using Cache Line Sized Atomic Write

Dokeun LEE  Seongjin LEE  Youjip WON  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E102-D   No.12   pp.2441-2450
Publication Date: 2019/12/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2019EDP7034
Type of Manuscript: PAPER
Category: Software System
Keyword: 
non-volatile memory,  key-value store,  index structure,  B+tree,  

Full Text: PDF(790.6KB)>>
Buy this Article




Summary: 
Indexing is one of the fields where the non-volatile memory (NVM) has the advantages of byte-addressable characteristics and fast read/write speed. The existing index structures for NVM have been developed based on the fact that the size of cache line and the atomicity guarantee unit of NVM are different and they tried to overcome the weakness of consistency from the difference. To overcome the weakness, an expensive flush operation is required which results in a lower performance than a basic B+tree index. Recent studies have shown that the I/O units of the NVM can be matched with the atomicity guarantee units under limited circumstances. In this paper, we propose a Cache line sized Atomic Write B+tree (CAWBT), which is a minimal B+tree structure that shows higher performance than a basic b+ tree and designed for NVM. CAWBT has almost same performance compared to basic B+tree without consistency guarantee and shows remarkable performance improvement compared to other B+tree indexes for NVM.