Optimal pagination of B-trees with variable-length items
Optimal pagination of B-trees with variable-length items
复制标题
具有可变长度项的 B 树的最佳分页
DOI：
--
复制
发表时间：
1984
期刊：
影响因子：
--
通讯作者：
B. Faaland
中科院分区：
文献类型：
--
作者：
G. Diehr;B. Faaland
两个算法开发的最佳组织的B-树（和变化）与可变长度的项目。第一个算法解决了McCreight提出的一个问题，即找到一个n个项目的分页，使提升到树的下一个更高级别的键长度之和最小化。该算法需要O（n log n）时间和O（n）空间。第二个算法从n个元素中构造最小深度树，时间复杂度为O（n3 logn）。这两种方法都依赖于动态编程参数，可以解释为最短路径问题。实现算法的实用方法进行了讨论。
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.