Pivotal B+tree for Byte-Addressable Persistent Memory
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...
| Main Authors: | , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2022-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/9764757/ |
| _version_ | 1818232069784862720 |
|---|---|
| author | Jonghyeon Yoo Hokeun Cha Wonbae Kim Wook-Hee Kim Sung-Soon Park Beomseok Nam |
| author_facet | Jonghyeon Yoo Hokeun Cha Wonbae Kim Wook-Hee Kim Sung-Soon Park Beomseok Nam |
| author_sort | Jonghyeon Yoo |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-12-12T11:00:26Z |
| format | Article |
| id | doaj.art-4bc3aa8c9d25472c9db618cf83144c61 |
| institution | Directory Open Access Journal |
| issn | 2169-3536 |
| language | English |
| last_indexed | 2024-12-12T11:00:26Z |
| publishDate | 2022-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj.art-4bc3aa8c9d25472c9db618cf83144c612022-12-22T00:26:32ZengIEEEIEEE Access2169-35362022-01-0110467254673710.1109/ACCESS.2022.31709169764757Pivotal B+tree for Byte-Addressable Persistent MemoryJonghyeon Yoo0Hokeun Cha1Wonbae Kim2Wook-Hee Kim3Sung-Soon Park4https://orcid.org/0000-0002-7284-3520Beomseok Nam5https://orcid.org/0000-0001-5481-6070Department of Software, Sungkyunkwan University, Suwon, South KoreaDepartment of Computer Sciences, University of Wisconsin–Madison, Madison, WI, USAUlsan National Institute of Science and Technology, Ulsan, South KoreaDepartment of Software, Konkuk University, Seoul, South KoreaGluesys, Anyang, South KoreaDepartment of Software, Sungkyunkwan University, Suwon, South KoreaOver 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.https://ieeexplore.ieee.org/document/9764757/Tree data structuresfault tolerancedatabase concurrency operations |
| spellingShingle | Jonghyeon Yoo Hokeun Cha Wonbae Kim Wook-Hee Kim Sung-Soon Park Beomseok Nam Pivotal B+tree for Byte-Addressable Persistent Memory IEEE Access Tree data structures fault tolerance database concurrency operations |
| title | Pivotal B+tree for Byte-Addressable Persistent Memory |
| title_full | Pivotal B+tree for Byte-Addressable Persistent Memory |
| title_fullStr | Pivotal B+tree for Byte-Addressable Persistent Memory |
| title_full_unstemmed | Pivotal B+tree for Byte-Addressable Persistent Memory |
| title_short | Pivotal B+tree for Byte-Addressable Persistent Memory |
| title_sort | pivotal b x002b tree for byte addressable persistent memory |
| topic | Tree data structures fault tolerance database concurrency operations |
| url | https://ieeexplore.ieee.org/document/9764757/ |
| work_keys_str_mv | AT jonghyeonyoo pivotalbx002btreeforbyteaddressablepersistentmemory AT hokeuncha pivotalbx002btreeforbyteaddressablepersistentmemory AT wonbaekim pivotalbx002btreeforbyteaddressablepersistentmemory AT wookheekim pivotalbx002btreeforbyteaddressablepersistentmemory AT sungsoonpark pivotalbx002btreeforbyteaddressablepersistentmemory AT beomseoknam pivotalbx002btreeforbyteaddressablepersistentmemory |