Lock-Free Binary Search Tree Based on Leaf Search

Lock-Free Binary Search Tree Based on Leaf Search

Yang Zhang (School of Information Science and Engineering, Hebei University of Science and Technology, Shijiazhuang, China), Xin Yu (School of Information Science and Engineering, Hebei University of Science and Technology, Shijiazhuang, China), Dongwen Zhang (School of Information Science and Engineering, Hebei University of Science and Technology, Shijiazhuang, China), Mengmeng Wei (School of Information Science and Engineering, Hebei University of Science and Technology, Shijiazhuang, China) and Yanan Liang (School of Information Science and Engineering, Hebei University of Science and Technology, Shijiazhuang, China)
Copyright: © 2017 |Pages: 15
DOI: 10.4018/IJOSSP.2017040103

Abstract

Binary search tree is one of the most important data structures in program design. This article proposes a novel lock-free algorithm, which can implement the lock-free operations, such as search, insert and delete, using compare and swap (CAS). Unlike the previous studies of handling the inside node in a tree, the authors' algorithm handles the insert and delete operations by considering of the subtree. This article presents the details of the lock-free algorithm, which can effectively reduce the contention between the update operations. The experiment compares the algorithm with other two lock-free algorithms by throughput. Evaluation results show that the throughput of the algorithm outperforms that of the other two concurrent BSTs when the number of threads is more than 4. The authors' algorithm will be competitive when the concurrency is high.
Article Preview

2. Lock-Free Binary Search Tree

CAS are one of the basic atomic instructions, which now are supported by almost all processors. One CAS instruction has three operands: memory address value V, the old expected value A, and the new value B. The value in V can be updated into B if and only if A is equal to this value.

According to the search pattern, BST is divided into an internal search tree and an external (leaf-oriented) search tree. The internal search tree maintains the value in the internal node, while in the external search tree, only the leaf node is stored with the actual key value, and internal nodes of the tree are used to guide a search operation along the path to the correct leaf. Our algorithm is based on a leaf-oriented search tree. Each internal node has only two children, which satisfies the following limitations: For each internal node x, the keys of all descendants in the left hand are less than x, and those of all descendants in the right hand are greater than or equal to the key of x.

Our BST implements the dictionary abstract data type and supports three operations: insert (k), delete (k), and contains (k). For convenience, we refer to the insert and delete operations as update operations.

Complete Article List

Search this Journal:
Reset
Open Access Articles
Volume 10: 4 Issues (2019): Forthcoming, Available for Pre-Order
Volume 9: 4 Issues (2018): 3 Released, 1 Forthcoming
Volume 8: 4 Issues (2017)
Volume 7: 4 Issues (2016)
Volume 6: 1 Issue (2015)
Volume 5: 3 Issues (2014)
Volume 4: 4 Issues (2012)
Volume 3: 4 Issues (2011)
Volume 2: 4 Issues (2010)
Volume 1: 4 Issues (2009)
View Complete Journal Contents Listing