Belga B-trees

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=logO(1)N. We also show how to transform any static BST into a static B-tree which is faster by a Θ(logB) factor; the transformation is randomized and we show that randomization is necessary to obtain any significant speedup.