A concurrent red–black tree

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.

► We have implemented a concurrent red–black tree based on optimistic concurrency techniques.
► In high contention scenarios our tree has up to 14% better throughput than other solutions.
► From now on there is a concurrent red–black tree that is competitive enough to be used in concurrent applications.
► Our new rebalancing operation maintains balance using fewer rotations.