Skip to main content

The CB tree: a practical concurrent self-adjusting search tree

Author(s): Afek, Yehuda; Kaplan, Haim; Korenfeld, Boris; Morrison, Adam; Tarjan, Robert E

To refer to this page use:
Abstract: We present the CB tree, a counting-based self-adjusting binary search tree in which, as in splay trees, more-frequently accessed items move closer to the root. In a sequential execution, after 𝑚 operations of which 𝑐(𝑣) access item 𝑣, an access of 𝑣 traverses a path of length (1+log𝑚𝑐(𝑣)) while doing few if any rotations. Unlike the original splay tree, in which each access moves the accessed item all the way to the root via a sequence of rotations, accesses in a CB tree do very few rotations, specifically (𝑛+𝑛log𝑚𝑛), during a sequence of 𝑚 operations of which 𝑛 are insertions. This is 𝑜(1) (subconstant) amortized per operation if 𝑚≫𝑛. We adapt the CB tree into a scalable concurrent self-adjusting BST. We show experimentally that the concurrent CB tree scales well because it, too, performs few rotations, and therefore self-adjusts without having rotations create a bottleneck. Our evaluation shows that the concurrent CB tree performs better than existing concurrent search trees on non-uniform access sequences derived from real workloads.
Publication Date: 2014
Citation: Afek, Yehuda, Haim Kaplan, Boris Korenfeld, Adam Morrison, and Robert E. Tarjan. "The CB tree: a practical concurrent self-adjusting search tree." Distributed Computing 27, no. 6 (2014): 393-417. doi:10.1007/s00446-014-0229-0
DOI: 10.1007/s00446-014-0229-0
ISSN: 0178-2770
EISSN: 1432-0452
Pages: 393 - 417
Type of Material: Journal Article
Journal/Proceeding Title: Distributed Computing
Version: Author's manuscript

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.