Welcome to the InfoSci Platform
Lock-Free Binary Search Tree Based on Leaf Search

Lock-Free Binary Search Tree Based on Leaf Search

Yang Zhang, Xin Yu, Dongwen Zhang, Mengmeng Wei, Yanan Liang
Copyright: © 2017 |Volume: 8 |Issue: 2 |Pages: 15
ISSN: 1942-3926|EISSN: 1942-3934|EISBN13: 9781522512684|DOI: 10.4018/IJOSSP.2017040103
Cite Article Cite Article

MLA

Zhang, Yang, et al. "Lock-Free Binary Search Tree Based on Leaf Search." IJOSSP vol.8, no.2 2017: pp.44-58. http://doi.org/10.4018/IJOSSP.2017040103

APA

Zhang, Y., Yu, X., Zhang, D., Wei, M., & Liang, Y. (2017). Lock-Free Binary Search Tree Based on Leaf Search. International Journal of Open Source Software and Processes (IJOSSP), 8(2), 44-58. http://doi.org/10.4018/IJOSSP.2017040103

Chicago

Zhang, Yang, et al. "Lock-Free Binary Search Tree Based on Leaf Search," International Journal of Open Source Software and Processes (IJOSSP) 8, no.2: 44-58. http://doi.org/10.4018/IJOSSP.2017040103

Export Reference

Mendeley
Favorite Full-Issue Download

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.

Request Access

You do not own this content. Please login to recommend this title to your institution's librarian or purchase it from the IGI Global bookstore.