Belga B-Trees

摘要

We revisitself-adjustingexternal 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, whereTango Trees(Demaine et al., SIAM J. Comput.37(1), 240-251,2007) were shown to be O(log log N)-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(log logN) factor of the best offline B-tree model algorithm, provided B = log O(1)N. We also show how to transform any static BST into a static B-tree which is faster by a Theta(log B) factor; the transformation is randomized and we show that randomization is necessary to obtain any significant speedup.