- Relaxed Multi-Way Trees with Group Updates.
- Kim S. Larsen.
In 20th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS), pages 93-101. ACM Press, 2001.
Data structures with relaxed balance differ from standard
structures in that rebalancing can be delayed and interspersed
with updates. This gives extra flexibility in both sequential
and parallel applications.
We study the version of multi-way trees
called (a,b)-trees (which includes B-trees)
with the operations insertion, deletion, and group insertion.
The latter has applications in for instance
document databases and WWW search engines.
We prove that we obtain the optimal asymptotic rebalancing complexities
of amortized constant time for insertion and deletion
and amortized logarithmic time in the size of the group
for group insertion.
These results hold even for the relaxed version.
Our results also demonstrate that a binary tree scheme
with the same complexities can be designed.
This is an improvement over the existing results.
- Link to the publication at the publisher's site - subscription may be required.
Text required by the publisher (if any):
The publication is available from ACM.
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 by the author.