License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.OPODIS.2016.34
URN: urn:nbn:de:0030-drops-71032
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7103/
He, Meng ;
Li, Mengdu
Deletion without Rebalancing in Non-Blocking Binary Search Trees
Abstract
We present a provably linearizable and lock-free relaxed AVL tree called the non-blocking ravl tree. At any time, the height of a non-blocking ravl tree is upper bounded by log_d (2m) + c, where d is the golden ratio, m is the total number of successful INSERT operations performed so far and c is the number of active concurrent processes that have inserted new keys and are still rebalancing the tree at this time. The most significant feature of the non-blocking ravl tree is that it does not rebalance itself after DELETE operations. Instead, it performs rebalancing only after INSERT operations. Thus, the non-blocking ravl tree is much simpler to implement than other self-balancing concurrent binary search trees (BSTs) which typically introduce a large number of rebalancing cases after DELETE operations, while still providing a provable non-trivial bound on its height. We further conduct experimental studies to compare our solution with other state-of-the-art concurrent BSTs using randomly generated data sequences under uniform distributions, and find that our solution achieves the best performance among concurrent self-balancing BSTs. As the keys in access sequences are likely to be partially sorted in system software, we also conduct experiments using data sequences with various degrees of presortedness to better simulate applications in practice. Our experimental results show that, when there are enough degrees of presortedness, our solution achieves the best performance among all the concurrent BSTs used in our studies, including those that perform self-balancing operations and those that do not, and thus is potentially the best candidate for many real-world applications.
BibTeX - Entry
@InProceedings{he_et_al:LIPIcs:2017:7103,
author = {Meng He and Mengdu Li},
title = {{Deletion without Rebalancing in Non-Blocking Binary Search Trees}},
booktitle = {20th International Conference on Principles of Distributed Systems (OPODIS 2016)},
pages = {34:1--34:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-031-6},
ISSN = {1868-8969},
year = {2017},
volume = {70},
editor = {Panagiota Fatourou and Ernesto Jim{\'e}nez and Fernando Pedone},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7103},
URN = {urn:nbn:de:0030-drops-71032},
doi = {10.4230/LIPIcs.OPODIS.2016.34},
annote = {Keywords: concurrent data structures, non-blocking data structures, lock-free data structures, self-balancing binary search trees, relaxed AVL trees}
}
|
Keywords: |
|
concurrent data structures, non-blocking data structures, lock-free data structures, self-balancing binary search trees, relaxed AVL trees |
|
Collection: |
|
20th International Conference on Principles of Distributed Systems (OPODIS 2016) |
|
Issue Date: |
|
2017 |
|
Date of publication: |
|
06.04.2017 |
