- Relaxed Multi-Way Trees with Group Updates.
- Kim S. Larsen.
Journal of Computer and System Sciences, 66(4): 657-670, 2003.
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, WWW search engines,
and differential indexing.
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.
This is an improvement over the existing results
in the most interesting cases.
- 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 ScienceDirect.
open access (176 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.