我想对一个长列表进行排序，所以我将所有元素放入一个 B 树中(每个元素需要 O(log n) 时间来插入)。
排序后，我需要读回元素。
你知道读取一个B树中的所有对象需要多长时间吗？
谢谢!
最佳答案
您可以使用对中序遍历的修改，在时间 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 ，专门为优化中序遍历和范围搜索而设计。
希望这对您有所帮助!
关于algorithm - 按排序顺序列出 B 树中的键所需的时间？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/17094431/