Master of Science in Computer Science
First Committee Member
Ajoy K. Datta
Second Committee Member
Third Committee Member
Fourth Committee Member
Number of Pages
We present a partial blocking implementation of concurrent binary search tree data structure that is contention friendly, fast and scales well. It uses a technique, called lazy splaying to move frequently accessed items close to the root without making the root of the tree a sequential bottleneck. Most of the self adjusting binary search trees are constrained to guarantee the height of a tree even in the presence of concurrency. But, this methodology roughly guarantees the height of a tree only in the absence of contention and limits the contention during concurrent accesses.
The main idea is to divide the update operation into two operations:an eager abstract modification with lazy splayingthat completes quickly and makes at most one local rotation of the tree on each access as a function of historical access frequencies; anda lazy structural adaptation with long/semi splayingwhich implements top down recursive splaying of the tree that may be postponed to diminish contention and re-balance the tree during less contention. This way, the frequently accessed items perform full splaying but after few accesses only and always appear near the root of the tree. Whereas, the infrequently accessed items will not get enough pushes up the tree and stay in the bottom part of the tree.
As in sequential counting based splay tree, the amortized time bound of each operation isO(log N), whereNis the number of items in the tree.
Binary Search Tree; Computer multitasking; Data structures (Computer science); Database searching; Search theory
Regmee, Mahesh Raj, "Self Adjusting Contention Friendly Concurrent Binary Search Tree by Lazy Splaying" (2014). UNLV Theses, Dissertations, Professional Papers, and Capstones. 2134.