B 3 -Tree: Byte-Addressable Binary B-Tree for Persistent Memory

• Published in: ACM transactions on storage 2020-08, Vol.16 (3), p.1-27
• Main Authors: Cha, Hokeun, Nam, Moohyeon, Jin, Kibeom, Seo, Jiwon, Nam, Beomseok
• Format: Article
• Language: English
• ISSN: 1553-3077; 1553-3093
• DOI: 10.1145/3394025

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.