Efficient Rebalancing of B-Trees with Relaxed Balance.

Kim S. Larsen and Rolf Fagerberg.
International Journal of Foundations of Computer Science, 7(2):169-186, 1996.

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.

---

publication

Link to the publication at the publisher's site - subscription may be required.
Text required by the publisher (if any): The publication is available via EBSCO Publishing.

open access (235 KB)

The same as the publisher's version, when the publisher permits. Otherwise, the author's last version before the publisher's copyright; this is often exactly the same, but sometimes fonts, page numbers, figure numbers, etc. are different. It may also be a full version. However, it is safe to read this version, and at the same time cite the official version, as long as references to concrete locations, numbered theorems, etc. inside the article are avoided.

other publications

Other publications by the author.