Practical concurrent binary search trees via logical ordering
Authors:
Open Access
- 6 February 2014
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGPLAN Notices
- Vol. 49 (8) , 343-356
Abstract
We present practical, concurrent binary search tree (BST) algorithms that explicitly maintain logical ordering information in the data structure, permitting clean separation from its physical tree layout. We capture logical ordering using intervals, with the property that an item belongs to the tree if and only if the item is an endpoint of some interval. We are thus able to construct efficient, synchronization-free and intuitive lookup operations. We present (i) a concurrent non-balanced BST with a lock-free lookup, and (ii) a concurrent AVL tree with a lock-free lookup that requires no synchronization with any mutating operations, including balancing operations. Our algorithms apply on-time deletion; that is, every request for removal of a node, results in its immediate removal from the tree. This new feature did not exist in previous concurrent internal tree algorithms. We implemented our concurrent BST algorithms and evaluated them against several state-of-the-art concurrent tree algorithms. Our experimental results show that our algorithms with lock-free contains and on-time deletion are practical and often comparable to the state-of-the-art.Keywords
This publication has 13 references indexed in Scilit:
- A general technique for non-blocking trees2014
- Fast concurrent lock-free binary search trees2014
- A concurrent red–black treeJournal of Parallel and Distributed Computing, 2013
- A Contention-Friendly Binary Search TreeLecture Notes in Computer Science, 2013
- A non-blocking internal binary search tree2012
- Concurrent cache-oblivious b-trees2005
- Performance analysis of BSTs in system software2004
- On optimistic methods for concurrency controlACM Transactions on Database Systems, 1981
- Concurrency of operations on B-treesActa Informatica, 1977
- Symmetric binary B-Trees: Data structure and maintenance algorithmsActa Informatica, 1972