Relaxed Multi-Way Trees with Group Updates

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review


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.
Original languageEnglish
Title of host publicationProceedings of the Twentieth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems
Number of pages8
PublisherAssociation for Computing Machinery
Publication date2001
Publication statusPublished - 2001
EventTwentieth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems - Santa Barbara, United States
Duration: 21. May 200123. May 2001


ConferenceTwentieth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems
Country/TerritoryUnited States
CitySanta Barbara


Dive into the research topics of 'Relaxed Multi-Way Trees with Group Updates'. Together they form a unique fingerprint.

Cite this