algorithm - 按排序顺序列出 B 树中的键所需的时间？

Question

我想对一个长列表进行排序，所以我将所有元素放入一个 B 树中(每个元素需要 O(log n) 时间来插入)。

排序后，我需要读回元素。

你知道读取一个B树中的所有对象需要多长时间吗？

谢谢!

Answer 1

您可以使用对中序遍历的修改，在时间 O(n) 内按排序顺序遍历 B 树中的所有元素。您可以按如下方式递归执行此操作:

To list off all elements of tree T in sorted order:
    Let the children of T be C0, C1, C2, ... Cn
    Let the keys of T be K1, K2, ..., Kn

    Output C0
    For i from 1 to n:
       Output Ki
       Recursively list all elements of Ci in order.

这需要时间 O(n)，因为每个键只被访问一次。 (作为一个有趣的练习，尝试将其与标准中序遍历的工作方式进行比较!)由于从未排序的数据构建 B 树需要时间 O(n log n)，因此该排序算法需要时间 O(n log n)。您可以将其视为对 tree sort 的修改。使用 B 树而不是 BST。

如果 B-tree 存储在磁盘上，这并没有很好的缓存性能。你最好使用 B+ tree ，专门为优化中序遍历和范围搜索而设计。

希望这对您有所帮助!