Concurrent manipulation of binary search trees


To implement a concurrent binary search tree system (CBSC) that can support any number of concurrent processes which perform searching, insertion, deletion, and rotation on the tree, but allow any process to lock only a constant number of nodes at any time. Also, in the systems, searches are essentially never blocked.


H.T. Kung and Philip L. Lehman. Concurrent manipulation of binary search trees. ACM Transactions on Database Systems, 5(3):354-382, 1980.

Additional reading material

Implementation details