Skip to main content

CBTree: 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 CBTree, a new counting-based self-adjusting binary search tree that, like splay trees, moves more frequently accessed nodes closer to the root. After m operations on n items, c of which access some item v, an operation on v traverses a path of length (log𝑚𝑐) while performing few if any rotations. In contrast to the traditional self-adjusting splay tree in which each accessed item is moved to the root through a sequence of tree rotations, the CBTree performs rotations infrequently (an amortized subconstant o(1) per operation if m ≫ n), mostly at the bottom of the tree. As a result, the CBTree scales with the amount of concurrency. We adapt the CBTree to a multicore setting and show experimentally that it improves performance compared to existing concurrent search trees on non-uniform access sequences derived from real workloads.
Publication Date: 2012
Citation: Afek, Yehuda, Haim Kaplan, Boris Korenfeld, Adam Morrison, and Robert E. Tarjan. "CBTree: A Practical Concurrent Self-Adjusting Search Tree." International Symposium on Distributed Computing (2012): pp. 1-15. doi:10.1007/978-3-642-33651-5_1
DOI: 10.1007/978-3-642-33651-5_1
ISSN: 0302-9743
EISSN: 1611-3349
Pages: 1 - 15
Type of Material: Conference Article
Journal/Proceeding Title: International Symposium on Distributed Computing
Version: Author's manuscript

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