Optimal pagination of B-trees with variable-length items. (English) Zbl 0587.68061

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.


68R10 Graph theory (including graph drawing) in computer science
68P05 Data structures
Full Text: DOI