Optimal pagination of B-trees with variable-length items

Abstract

Two algorithms are developed for the optimal organization of B-trees (and variations) with variable-length items. The first algorithm solves a problem posed by McCreight, that of finding a pagination of n items that minimizes the sum of key lengths promoted to the next higher level of the tree. The algorithm requires O(n log n) time and O(n) space. The second algorithm constructs the minimum depth tree in O(n 3 log n) time from the n items. Both methods rely on dynamic programming arguments and can be interpreted as shortest-path problems. Practical approaches for implementing the algorithms are discussed.