B+ tree insertion order

Question

Is there a possible way to find the original insertion order of a B+ tree?

I have this tree:

{ [ (1 2) 3 (5 6 7) ] 8 [ (9 10) 11 (12 13) 14 (14 16 17) 18 ( 19 20) ] }

Example tree

Answer 1

No.

For example in your case, the last two inserts could have been 7, 17 or 17, 7 and there is absolutely no way to tell which was which. Indeed of 5, 6, 7 one of the three was inserted after the other two and there is no record of which is which.

This can also be seen immediately from the pigeon hole principle. First let's put an upper bound on how many k-way B-trees there can be with n things in it.

The structure of any b-tree with n things can be encoded as a stream of the sizes of the nodes. From the size of the top node, you know what how many second tier nodes there are, ditto for third tier from second tier. A node can have anywhere from 1..k things in it. There cannot be more nodes than elements. Therefore we can specify a B-tree by first specifying how many nodes there are, then the sizes of the nodes. (Not all sets of numbers will be a B-tree.) For every size s of B-tree, there are k^s <= k^n of them. Therefore n k^n is an upper bound on how many k-way B-trees there can be. Which is exponential growth.

But the number of orders in which elements might be inserted is n!. This function grows strictly faster than exponential growth, and so you cannot recover the order from the B-tree.