Document Type

Technical Report

Publication Date



Synchronization, Data structures (Computer science), Computer networks -- Scalability, Computer multitasking


Operating system performance and scalability on sharedmemory many-core systems depends critically on efficient access to shared data structures. Scalability has proven difficult to achieve for many data structures. In this paper we present a novel and highly scalable concurrent red-black tree. Red-black trees are widely used in operating systems, but typically exhibit poor scalability. Our red-black tree has linear read scalability, uncontended read performance that is at least 25% faster than other known approaches, and deterministic lookup times for a given tree size, making it suitable for realtime applications.


Portland State University Computer Science Department Technical Report 10-06, January 2011.

Persistent Identifier