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)。您可以将其视为使用 B-tree 而不是 BST的树排序的修改。

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

希望这可以帮助！