.png){kind=icon}
.png){kind=icon}
Return
Circ-Tree: A B plus -Tree Variant With Circular Design for Persistent Memory
.png){kind=icon}
OA
AI
DOI：10.1109/TC.2020.3047972.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Several B+-tree variants have been developed to exploit the byte-addressable non-volatile memory (NVM). We attentively investigate the properties of B+-tree and find that, a conventional B+-tree node is a linear structure in which key-value (KV) pairs are maintained from the zero offset of a node. These KV pairs are shifted in a unidirectional fashion for insertions and deletions. Inserting and deleting one KV pair may inflict a large amount of write amplifications due to shifting existing KV pairs. This badly impairs the performance of in-NVM B+-tree. In this article, we propose a novel circular design for B+-tree. With regard to NVM's byte-addressability, our Circ-Tree embraces tree nodes in a circular structure without a fixed base address, and bidirectionally shifts KV pairs for insertions and deletions to minimize write amplifications. We have implemented a prototype for Circ-Tree and conducted extensive experiments. Experimental results show that Circ-Tree significantly outperforms two state-of-the-art in-NVM B+-tree variants, i.e., NV-tree and FAST+FAIR, by up to 1.6x and 8.6x, respectively, in terms of write performance. The end-to-end comparison by running YCSB to KV stores built on NV-tree, FAST+FAIR, and Circ-Tree reveals that Circ-Tree yields up to 29.3 and 47.4 percent higher write performance, respectively, than NV-tree and FAST+FAIR.
Keywords:
Nonvolatile memory
Random access memory
Writing
Computer crashes
Hard disks
Data structures
Memory management
Persistent memory
B plus -tree
non-volatile memory
crash consistency
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
3.8
Papers:
5.3K
Citations:
9.8K
Organization
View more organizations