B-trees with relaxed balance are defined to facilitate fast updating in a concurrent database environment. Updating and rebalancing are uncoupled such that extensive locking can be avoided in connection with updates. However, weaker constraints than the usual ones are maintained such that the tree can still be balanced efficiently independent of the updating processes. The choice of constraints and conditions under which the different rebalancing operations can be carried out is critical for the overall complexity. We prove that with the rebalancing operations presented here, each update gives rise to at most floor(log_a(N/2)) + 1 rebalancing operations, where a is the degree of the B-tree, and N is the bound on its maximal size since it was last in balance.
Using techniques of amortized analysis, we prove that in the long run, rebalancing is constant time on average, even if any particular update could give rise to logarithmic time rebalancing. We also prove that the amount of rebalancing done at any particular level decreases exponentially going from the leaves towards the root. This is important since locking close to the root can significantly reduce the amount of parallelism possible in the system.
Though the object of interest to us here is the B-tree, the results are in fact obtained for the more general (a,b)-trees, so we have results for both of the common B-tree versions as well as 2-3 trees and 2-3-4 trees.