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

Diehr, George; Faaland, Bruce

Commun. ACM 27, 241-247 (1984).

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.

MSC:

68R10	Graph theory (including graph drawing) in computer science
68P05	Data structures

Keywords:

algorithms; sum of key lengths; minimum depth tree; dynamic programming; shortest-path problems