Pivotal B+tree for Byte-Addressable Persistent Memory
Jonghyeon Yoo, Hokeun Cha, Wonbae Kim and 3 more
IEEE Access · 2022
doi:10.1109/access.2022.3170916 (opens in a new tab)
We email you when a new notice or a question about this paper appears.
Abstract
Over the past few years, various indexes have been redesigned for byte-addressable persistent memory. In this work, we design and implement <italic>PB</italic>+<italic>tree</italic> (Pivotal B+tree) that resolves the limitations of state-of-the-art fully persistent B+trees. First, PB+tree reduces the number of expensive shift operations by up to half by managing two sub-arrays separated by a <italic>pivot</italic> key. Second, PB+tree reads cachelines in ascending order, which makes PB+tree benefit from hardware prefetchers and run faster than state-of-the-art persistent B+trees that access cachelines in non-contiguous or descending order. Third, PB+tree employs an optimistic lock-free search algorithm to avoid repeatedly visiting the same tree node. Although the optimistic lock-free search algorithm involves a risk of visiting incorrect child nodes, PB+tree guarantees correct search results using the <italic>lazy correction</italic> algorithm using doubly linked sibling pointers. Our performance study shows that PB+tree outperforms the state-of-the-art fully persistent indexes by a large margin. A search algorithm without optimistic locking risks visiting the wrong child node, but PB+tree uses a <italic>lazy correction</italic> algorithm with doubly linked sibling pointers to ensure correct search results. Our performance studies show that PB+trees outperform state-of-the-art fully persistent indexes.
Abstract licence: CC BY-NC-ND
Reads
Read by people on this page
None yet.
Checked or read by AI through naulon
None yet.
A person counts once a day per paper. We keep no cookie and no address: a reader is a hash that changes every day. Any month under five reads shows no number.
Are you an author?
Is this your paper?
Claim it to add your note and be paid when agents cite it. Free.