B-Trees with Relaxed Balance.

Kim S. Larsen and Rolf Fagerberg.
In 9th International Parallel Processing Symposium (IPPS), pages 196-202. IEEE Computer Society Press, 1995.

B-trees with relaxed balance have been defined to facilitate fast updating on shared-memory asynchronous parallel architectures. To obtain this, rebalancing has been uncoupled from the updating such that extensive locking can be avoided in connection with updates.

We analyze B-trees with relaxed balance, and prove that 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. Assuming that the size of nodes are at least twice the degree, we prove that rebalancing can be performed in amortized constant time. So, 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 the higher up in the tree a lock due to a rebalancing operation occurs, the larger a subtree which cannot be accessed by other processes for the duration of that lock.

All of these 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): none.

full version

Link to the journal version containing all the material and proofs, some of which are usually omitted in the conference version due to space constraints.

other publications

Other publications by the author.