A concurrent redblack 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. Redblack trees are an important data structure used in many systems. Unfortunately, it is difficult to implement an efficient concurrent redblack 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 redblack 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.
redblack tree concurrent data structure algorithm design