Skip Navigation
York U: Redefine the PossibleHOME | Current Students | Faculty & Staff | Research | International
Search »FacultiesLibrariesCampus MapsYork U OrganizationDirectorySite Index
Future Students, Alumni & Visitors
2011 Technical Reports

Non-blocking k-ary Search Trees

Trevor Brown and Joanna Helga

Technical Report CSE-2011-04

York University

June 2011


This paper presents the first concurrent non-blocking k-ary search tree. Our data structure generalizes the recent non-blocking binary search tree of Ellen et al. to trees in which each internal node has k children. Larger values of k decrease the depth of the tree, but lead to higher contention among processes performing updates to the tree. Our Java implementation uses single-word compare-and-set operations to coordinate updates to the tree. We present experimental results from two machines. The first one is a 32-core Intel machine with 32 hardware threads available, and the second machine is a 16-core Sun machine with 128 hardware contexts. The experimental results show that our implementation achieves higher throughput than the Java class library's non-blocking skip list. Our implementation also outperforms the lock-based AVL tree of Bronson et al., which is the leading concurrent search tree. Our experimental results show that our algorithm scales extremely well.

Download paper in PDF format.

The documents distributed by this server have been provided by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a noncommercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.