14/07/2020

Efficient concurrent range queries in b+-trees using RCU-HTM

Dimitrios Siakavaras, Panagiotis Billis, Konstantinos Nikas, Georgios Goumas, Nectarios Koziris

Keywords: RCU-HTM, HTM, RCU, search trees, concurrent data structures

Abstract: In this work, we exploit RCU-HTM, a synchronization mechanism that combines Read-Copy-Update (RCU) and Hardware Transactional Memory (HTM) to support linearizable and highly efficient range queries in a concurrent B+-tree. Range queries in our B+-tree start with an asynchronized traversal and then perform a horizontal scan of leaf nodes, by following sibling pointers, using hardware transactions. Despite its simplicity, our RCU-HTM based B+-tree with range query support greatly outperforms state-of-the-art map data structures for range queries in several execution scenarios.

 0
 0
 0
 0
This is an embedded video. Talk and the respective paper are published at SPAA 2020 virtual conference. If you are one of the authors of the paper and want to manage your upload, see the question "My papertalk has been externally embedded..." in the FAQ section.

Comments

Post Comment
no comments yet
code of conduct: tbd

Similar Papers