Uncoupling updating and rebalancing in chromatic binary search trees
Otto Nurmi, Eljas Soisalon-Soininen · 1991
In order to gain maximal efficiency of the concurrent use of search trees the number of nodes to be locked at a time should be as small aa possible, and the locks should be released aa soon aa possible.We propose a new rebalancing method for binary search treea that allows rebalancing to be uncoupled from updating, so as to make updating faster.The trees we use are obtained by relaxing the balance conditions of red-black trees.When not involved with updating, the rebalancing task can be performed as a shadow process being active all the time, or it can be performed outside rush hours, at night, for example.1.