CBTree: A practical concurrent self-adjusting search tree

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

26 Scopus citations

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 O(log m/c) 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.

Original languageEnglish (US)
Title of host publicationDistributed Computing - 26th International Symposium, DISC 2012, Proceedings
Pages1-15
Number of pages15
DOIs
StatePublished - 2012
Event26th International Symposium on Distributed Computing, DISC 2012 - Salvador, Brazil
Duration: Oct 16 2012Oct 18 2012

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7611 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other26th International Symposium on Distributed Computing, DISC 2012
CountryBrazil
CitySalvador
Period10/16/1210/18/12

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

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

  • Cite this

    Afek, Y., Kaplan, H., Korenfeld, B., Morrison, A., & Tarjan, R. E. (2012). CBTree: A practical concurrent self-adjusting search tree. In Distributed Computing - 26th International Symposium, DISC 2012, Proceedings (pp. 1-15). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7611 LNCS). https://doi.org/10.1007/978-3-642-33651-5_1