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

Yehuda Afek, Haim Kaplan, Boris Korenfeld, Adam Morrison, Robert E. Tarjan

Research output: Contribution to journalArticlepeer-review

20 Scopus citations

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 m operations of which c(v) access itema v access of v traverses a path of length O(1+log m/c(v)) 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 O(n+nlog(m/n), during a sequence of operations of which n are insertions. This is o(1)(subconstant) amortized per operation if m ≫ n. 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.

Original languageEnglish (US)
Pages (from-to)393-417
Number of pages25
JournalDistributed Computing
Volume27
Issue number6
DOIs
StatePublished - Nov 23 2014

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Hardware and Architecture
  • Computer Networks and Communications
  • Computational Theory and Mathematics

Keywords

  • Optimistic concurrency control
  • Self-adjusting tree
  • Splay tree

Fingerprint

Dive into the research topics of 'The CB tree: a practical concurrent self-adjusting search tree'. Together they form a unique fingerprint.

Cite this