Anzeige
Erschienen in:
2012 | OriginalPaper | Buchkapitel
CBTree: A Practical Concurrent Self-Adjusting Search Tree
verfasst von : Yehuda Afek, Haim Kaplan, Boris Korenfeld, Adam Morrison, Robert E. Tarjan
Erschienen in: Distributed Computing
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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
$\mathcal{O}(\log\dfrac{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.