Time required to list off keys in a B-tree in sorted order?

Question

I want to sort a long list, so I put all the elements into a B-tree (each element takes O(log n) time to insert).

Once sorted, I need to read back the elements.

Do you know how it is done how long it is to read all the objects in a B-tree?

Thanks!

Answer 1

You can iterate over all of the elements in a B-tree in sorted order in time O(n) by using a modification of an inorder traversal. You would do this recursively as follows:

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.

This takes time O(n), because each key is visited exactly once. (As a fun exercise, try comparing this to how a standard inorder traversal works!) Since it takes time O(n log n) to build a B-tree from unsorted data, this sorting algorithm takes time O(n log n). You can think of it as a modification of tree sort that uses a B-tree rather than a BST.

If the B-tree is stored on-disk, this does not have very good caching performance. You would be better off using a B+ tree, which is specifically designed to optimize for inorder traversals and range searches.

Hope this helps!