- 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
is the degree of the B-tree,
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.
- 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 by the author.