For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
CAWBT: NVM-Based B+Tree Index Structure Using Cache Line Sized Atomic Write
Dokeun LEE Seongjin LEE Youjip WON
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2019/12/01
Online ISSN: 1745-1361
Type of Manuscript: PAPER
Category: Software System
non-volatile memory, key-value store, index structure, B+tree,
Full Text: PDF(790.6KB)>>
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.