 Efficient Rebalancing of BTrees with Relaxed Balance.
 Kim S. Larsen and Rolf Fagerberg.
International Journal of Foundations of Computer Science, 7(2):169186, 1996.
Btrees 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 Btree,
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 Btree, the results
are in fact obtained for the more general (a,b)trees, so we have results
for both of the common Btree versions as well as 23 trees and 234 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.