How to, given a predetermined set of keys, reorder the keys such that the minimum number of nodes are used when inserting into a B-Tree?

Question

So I have a problem which i'm pretty sure is solvable, but after many, many hours of thinking and discussion, only partial progress has been made.

The issue is as follows. I'm building a BTree of, potentially, a few million keys. When searching the BTree, it is paged on demand from disk into memory, and each page in operation is relatively expensive. This effectively means that we want to need to traverse as few nodes as possible (although after a node has been traversed to, the cost of traversing through that node, up to that node is 0). As a result, we don't want to waste space by having lots of nodes nearing minimum capacity. In theory, this should be preventable (within reason) as the structure of the tree is dependent on the order that the keys were inserted in.

So, the question is how to reorder the keys such that after the BTree is built the fewest number of nodes are used. Here's an example:

I did stumble on this question In what order should you insert a set of known keys into a B-Tree to get minimal height? which unfortunately asks a slightly different question. The answers, also don't seem to solve my problem. It is also worth adding that we want the mathematical guarantees that come from not building the tree manually, and only using the insert option. We don't want to build a tree manually, make a mistake, and then find it is unsearchable!

I've also stumbled upon 2 research papers which are so close to solving my question but aren't quite there! Time-and Space-Optimality in B-Trees and Optimal 2,3-Trees (where I took the above image from in fact) discuss and quantify the differences between space optimal and space pessimal BTrees, but don't go as far as to describe how to design an insert order as far as I can see.

Any help on this would be greatly, greatly appreciated.

Thanks

Research papers can be found at:

http://www.uqac.ca/rebaine/8INF805/Automne2007/Sujets2007Automne/p174-rosenberg.pdf

http://scholarship.claremont.edu/cgi/viewcontent.cgi?article=1143&context=hmc_fac_pub

EDIT:: I ended up filling a btree skeleton constructed as described in the above papers with the FILLORDER algorithm. As previously mentioned, I was hoping to avoid this, however I ended up implementing it before the 2 excellent answers were posted!

Answer 1

The algorithm below should work for B-Trees with minimum number of keys in node = d and maximum = 2*d I suppose it can be generalized for 2*d + 1 max keys if way of selecting median is known.

Algorithm below is designed to minimize the number of nodes not just height of the tree.

Method is based on idea of putting keys into any non-full leaf or if all leaves are full to put key under lowest non full node.

More precisely, tree generated by proposed algorithm meets following requirements: It has minimum possible height; It has no more then two nonfull nodes on each level. (It's always two most right nodes.)

Since we know that number of nodes on any level excepts root is strictly equal to sum of node number and total keys number on level above we can prove that there is no valid rearrangement of nodes between levels which decrease total number of nodes. For example increasing number of keys inserted above any certain level will lead to increase of nodes on that level and consequently increasing of total number of nodes. While any attempt to decrease number of keys above the certain level will lead to decrease of nodes count on that level and fail to fit all keys on that level without increasing tree height. It also obvious that arrangement of keys on any certain level is one of optimal ones. Using reasoning above also more formal proof through math induction may be constructed.

The idea is to hold list of counters (size of list no bigger than height of the tree) to track how much keys added on each level. Once I have d keys added to some level it means node filled in half created in that level and if there is enough keys to fill another half of this node we should skip this keys and add root for higher level. Through this way, root will be placed exactly between first half of previous subtree and first half of next subtree, it will cause split, when root will take it's place and two halfs of subtrees will become separated. Place for skipped keys will be safe while we go through bigger keys and can be filled later.

Here is nearly working (pseudo)code, array needs to be sorted:

PushArray(BTree bTree, int d, key[] Array)
{
    List<int> counters = new List<int>{0};
    //skip list will contain numbers of nodes to skip 
    //after filling node of some order in half
    List<int> skip  = new List<int>();
    List<Pair<int,int>> skipList = List<Pair<int,int>>();

    int i = -1;
    while(true)
    {     
       int order = 0;
       while(counters[order] == d) order += 1;
       for(int j = order - 1; j >= 0; j--) counters[j] = 0;

       if (counters.Lenght <= order + 1) counters.Add(0);
       counters[order] += 1;

       if (skip.Count <= order)
              skip.Add(i + 2);    
       if (order > 0)
           skipList.Add({i,order}); //list of skipped parts that will be needed later
       i += skip[order];

       if (i > N) break;

       bTree.Push(Array[i]);
    }

    //now we need to add all skipped keys in correct order
    foreach(Pair<int,int> p in skipList)
    {
        for(int i = p.2; i > 0; i--)
            PushArray(bTree, d, Array.SubArray(p.1 + skip[i - 1], skip[i] -1))
    }
}

Example:

Here is how numbers and corresponding counters keys should be arranged for d = 2 while first pass through array. I marked keys which pushed into the B-Tree during first pass (before loop with recursion) with 'o' and skipped with 'x'.

                                                              24
        4         9             14             19                            29 
0 1 2 3   5 6 7 8   10 11 12 13    15 16 17 18    20 21 22 23    25 26 27 28    30 ...
o o x x o o o x x o  o  o  x  x  x  x  x  x  x  x  x  x  x  x  o  o  o  x  x  o  o ...
1 2     0 1 2     0  1  2                                      0  1  2        0  1 ...
0 0     1 1 1     2  2  2                                      0  0  0        1  1 ...
0 0     0 0 0     0  0  0                                      1  1  1        1  1 ...
skip[0] = 1 
skip[1] = 3 
skip[2] = 13

Since we don't iterate through skipped keys we have O(n) time complexity without adding to B-Tree itself and for sorted array;

In this form it may be unclear how it works when there is not enough keys to fill second half of node after skipped block but we can also avoid skipping of all skip[order] keys if total length of array lesser than ~ i + 2 * skip[order] and skip for skip[order - 1] keys instead, such string after changing counters but before changing variable i might be added:

while(order > 0 && i + 2*skip[order] > N) --order;

it will be correct cause if total count of keys on current level is lesser or equal than 3*d they still are split correctly if add them in original order. Such will lead to slightly different rearrangement of keys between two last nodes on some levels, but will not break any described requirements, and may be it will make behavior more easy to understand.

May be it's reasonable to find some animation and watch how it works, here is the sequence which should be generated on 0..29 range: 0 1 4 5 6 9 10 11 24 25 26 29 /end of first pass/ 2 3 7 8 14 15 16 19 20 21 12 13 17 18 22 23 27 28

Answer 2

The algorithm below attempts to prepare the order the keys so that you don't need to have power or even knowledge about the insertion procedure. The only assumption is that overfilled tree nodes are either split at the middle or at the position of the last inserted element, otherwise the B-tree can be treated as a black box.

The trick is to trigger node splits in a controlled way. First you fill a node exactly, the left half with keys that belong together and the right half with another range of keys that belong together. Finally you insert a key that falls in between those two ranges but which belongs with neither; the two subranges are split into separate nodes and the last inserted key ends up in the parent node. After splitting off in this fashion you can fill the remainder of both child nodes to make the tree as compact as possible. This also works for parent nodes with more than two child nodes, just repeat the trick with one of the children until the desired number of child nodes is created. Below, I use what is conceptually the rightmost childnode as the "splitting ground" (steps 5 and 6.1).

Apply the splitting trick recursively, and all elements should end up in their ideal place (which depends on the number of elements). I believe the algorithm below guarantees that the height of the tree is always minimal and that all nodes except for the root are as full as possible. However, as you can probably imagine it is hard to be completely sure without actually implementing and testing it thoroughly. I have tried this on paper and I do feel confident that this algorithm, or something extremely similar, should do the job.

Implied tree T with maximum branching factor M.

Top procedure with keys of length N:

1. Sort the keys.
2. Set minimal-tree-height to ceil(log(N+1)/log(M)).
3. Call insert-chunk with chunk = keys and H = minimal-tree-height.

Procedure insert-chunk with chunk of length L, subtree height H:

1. If H is equal to 1:
   1. Insert all keys from the chunk into T
   2. Return immediately.
2. Set the ideal subchunk size S to pow(M, H - 1).
3. Set the number of subtrees T to ceil((L + 1) / S).
4. Set the actual subchunk size S' to ceil((L + 1) / T).
5. Recursively call insert-chunk with chunk' = the last floor((S - 1) / 2) keys of chunk and H' = H - 1.
6. For each of the ceil(L / S') subchunks (of size S') except for the last with index I:
   1. Recursively call insert-chunk with chunk' = the first ceil((S - 1) / 2) keys of subchunk I and H' = H - 1.
   2. Insert the last key of subchunk I into T (this insertion purposefully triggers a split).
   3. Recursively call insert-chunk with chunk' = the remaining keys of subchunk I (if any) and H' = H - 1.
7. Recursively call insert-chunk with chunk' = the remaining keys of the last subchunk and H' = H - 1.

Note that the recursive procedure is called twice for each subtree; that is fine, because the first call always creates a perfectly filled half subtree.