Abstract
Any Btree has height at least ceil[log_B(n)]. Static Btrees achieving this height are easy to build. In the dynamic case, however, standard Btree rebalancing algorithms only maintain a height within a constant factor of this optimum. We investigate exactly how close to ceil[log_B(n)] the height of dynamic Btrees can be maintained as a function of the rebalancing cost. In this paper, we prove a lower bound on the cost of maintaining optimal height ceil[log_B(n)], which shows that this cost must increase from Omega(1/B) to Omega(n/B) rebalancing per update as n grows from one power of B to the next. We also provide an almost matching upper bound, demonstrating this lower bound to be essentially tight. We then give a variant upper bound which can maintain nearoptimal height at low cost. As two special cases, we can maintain optimal height for all but a vanishing fraction of values of n using Theta(log_B(n)) amortized rebalancing cost per update and we can maintain a height of optimal plus one using O(1/B) amortized rebalancing cost per update. More generally, for any rebalancing budget, we can maintain (as n grows from one power of B to the next) optimal height essentially up to the point where the lower bound requires the budget to be exceeded, after which optimal height plus one is maintained. Finally, we prove that this balancing scheme gives Btrees with very good storage utilization.
BibTeX  Entry
@InProceedings{fagerberg_et_al:LIPIcs:2019:11531,
author = {Rolf Fagerberg and David Hammer and Ulrich Meyer},
title = {{On Optimal Balance in BTrees: What Does It Cost to Stay in Perfect Shape?}},
booktitle = {30th International Symposium on Algorithms and Computation (ISAAC 2019)},
pages = {35:135:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771306},
ISSN = {18688969},
year = {2019},
volume = {149},
editor = {Pinyan Lu and Guochuan Zhang},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2019/11531},
URN = {urn:nbn:de:0030drops115313},
doi = {10.4230/LIPIcs.ISAAC.2019.35},
annote = {Keywords: Btrees, Data structures, Lower bounds, Complexity}
}
Keywords: 

Btrees, Data structures, Lower bounds, Complexity 
Collection: 

30th International Symposium on Algorithms and Computation (ISAAC 2019) 
Issue Date: 

2019 
Date of publication: 

28.11.2019 