AbstractIn this paper the construction of optimal B-trees for n keys, n key weights, and n+1 gap weights, is investigated. The best algorithms up to now have running time O(k n3 log n), where k is the order of the B-tree. These algorithms are based on dynamic programming and use step by step construction of larger trees from optimal smaller trees. We present a new algorithm, which has running time O(k nalpha), with alpha = 2 + log 2 / log (k+1). This is a substantial improvement to the former algorithms. The improvement is achieved by applying a different dynamic programming paradigm. Instead of step by step construction from smaller subtrees a decision model is used, where the keys are placed by a sequential decision process in such a way into the tree, that the costs become optimal and the B-tree constraints are valid.
Categories and Subject Descriptors: E.1 [Data Structures]; H.2.2 [Database Management]: Physical Design; I.2.8 [Artificial Intelligence]: Problem Solving, Control Methods, and Search
Additional Key Words and Phrases: B-Tree, optimization, dynamic programming
Selected references
- Rudolf Bayer and Edward M. McCreight. Organization and maintenance of large ordered indices. Acta Informatica, 1:173-189, 1972.
- Vijay K. Vaishnavi, Hans-Peter Kriegel, and D. Wood. Optimum multiway search trees. Acta Informatica, 14:119-133, 1980.