B3-Tree: Byte-Addressable Binary B-Tree for Persistent Memory
- Title
- B3-Tree: Byte-Addressable Binary B-Tree for Persistent Memory
- Author
- 서지원
- Keywords
- Non-volatile memory; data structure; persistent indexing
- Issue Date
- 2020-07
- Publisher
- ASSOC COMPUTING MACHINERY
- Citation
- ACM TRANSACTIONS ON STORAGE, v. 16, no. 3, article no. 17
- Abstract
- In this work, we propose B-3-tree, a hybrid index for persistent memory that leverages the byte-addressability of the in-memory index and the page locality of B-trees. As in the byte-addressable in-memory index, B-3-tree is updated by 8-byte store instructions. Also, as in disk-based index, B-3-tree is failure-atomic since it makes every 8-byte store instruction transform a consistent index into another consistent index without the help of expensive logging. Since expensive logging becomes unnecessary, the number of cacheline flush instructions required for B-3-tree is significantly reduced. Our performance study shows that B-3-tree outperforms other state-of-the-art persistent indexes in terms of insert and delete performance. While B-3-tree shows slightly worse performance for point query performance, the range query performance of B-3-tree is 2x faster than FAST and FAIR B-tree because the leaf page size of B-3-tree can be set to 8x larger than that of FAST and FAIR B-tree without degrading insertion performance. We also show that read transactions can access B-3- tree without acquiring a shared lock because B-3-tree remains always consistent while a sequence of 8-byte write operations are making changes to it. As a result, B-3-tree provides high concurrency level comparable to FAST and FAIR B-tree.
- URI
- https://dl.acm.org/doi/10.1145/3394025https://repository.hanyang.ac.kr/handle/20.500.11754/169323
- ISSN
- 1553-3077; 1553-3093
- DOI
- 10.1145/3394025
- Appears in Collections:
- COLLEGE OF ENGINEERING[S](공과대학) > COMPUTER SCIENCE(컴퓨터소프트웨어학부) > Articles
- Files in This Item:
There are no files associated with this item.
- Export
- RIS (EndNote)
- XLS (Excel)
- XML