Search trees with relaxed balance were introduced with the aim of facilitating fast updating on shared-memory asynchronous parallel archi- tectrues. To obtain this, rebalancing has been uncoupled form the updating, so extensive locking in connection with updates is avoided. Rebalancing is taken care of by background processes, which do only a constant amount of work at a time before they release locks.
展开▼
