A concurrent red–black tree.

Abstract

With the proliferation of multiprocessor computers, data structures capable of supporting several processes are a growing need. Concurrent data structures seek to provide similar performance to sequential data structures while being accessible concurrently by several processes and providing synchronization mechanisms transparently to those processes.

Red–black trees are an important data structure used in many systems. Unfortunately, it is difficult to implement an efficient concurrent red–black tree for shared memory processes; so most research efforts have been directed towards other dictionary data structures, mainly skip-lists and AVL trees.

In this paper we present a new type of concurrent red–black tree that uses optimistic concurrency techniques and new balancing operations to scale well and support contention.

Our tree performs favorably compared to other similar dictionaries; in particular, in high contention scenarios it performs up to 14% better than the best-known concurrent dictionary solutions.