Belga B-Trees
Author(s)
Demaine, Erik D; Iacono, John; Koumoutsos, Grigorios; Langerman, Stefan
DownloadAccepted version (583.4Kb)
Open Access Policy
Open Access Policy
Creative Commons Attribution-Noncommercial-Share Alike
Terms of use
Metadata
Show full item recordAbstract
We revisit self-adjusting external memory tree data structures, which combine the optimal (and practical) worst-case I/O performances of B-trees, while adapting to the online distribution of queries. Our approach is analogous to undergoing efforts in the BST model, where Tango Trees (Demaine et al. 2007) were shown to be O(loglogN) -competitive with the runtime of the best offline binary search tree on every sequence of searches. Here we formalize the B-Tree model as a natural generalization of the BST model. We prove lower bounds for the B-Tree model, and introduce a B-Tree model data structure, the Belga B-tree, that executes any sequence of searches within a O(loglogN) factor of the best offline B-tree model algorithm, provided B= log[superscript O(1)]N. We also show how to transform any static BST into a static B-tree which is faster by a Θ(log B) factor; the transformation is randomized and we show that randomization is necessary to obtain any significant speedup.
Description
Part of the Lecture Notes in Computer Science book series (LNCS, volume 11532)
Date issued
2019-07Department
Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science; Massachusetts Institute of Technology. Computer Science and Artificial Intelligence LaboratoryJournal
Lecture Notes in Computer Science
Publisher
Springer International Publishing
Citation
Demaine, Erik D. et al. “Belga B-Trees.” 14th International Computer Science Symposium, Lecture Notes in Computer Science, 11532, Springer, 2019, 93-105. © 2019 The Author(s)
Version: Author's final manuscript
ISSN
0302-9743