INSERT

So far, we've built up ways of creating a B-Tree, and described how to locate an object in a B-Tree. We lack, however, a way to put things into one of those trees, so that they can be found. "Insert" may not performed as often as "find", but it is pretty important.

The first half of the algorithm is pretty easy. Since all the data is stored at the leaves, we just do the "interior node" part of the find, to locate the leaf in which this data should be stored. In the leaf we just do a linear search until we find the right spot to put the new data.

Note, this might mean having to moved some/most/all of the rest of the data in this leaf, to keep the items in order. But, we're happy to do almost any kind of O(n) processing if we can avoid disk hits.

The only trick is what if there is already m things in this leaf. Well, then only m things are allowed in the leaf, and this would be the m+1th. No good.

NEXT BACK