Cover Data Structures and Algorithms with Object-Oriented Design Patterns in Java
next up previous contents index

Inserting Items into a B-Tree

The algorithm for insertion into a B-Tree begins as do all the other search tree insertion algorithms: To insert item x, we begin at the root and conduct a search for it. Assuming the item is not already in the tree, the unsuccessful search will terminate at a leaf node. This is the point in the tree at which the x is inserted.

If the leaf node has fewer than M-1 keys in it, we simply insert the item in the leaf node and we are done. For example, consider a leaf node with n<M subtrees and n-1 keys of the form

displaymath64556

For every new key inserted in the node, a new subtree is required too. In this case because T is a leaf, all its subtrees are empty trees. Therefore, when we insert item x, we really insert the pair of items tex2html_wrap_inline64576. Suppose the key to be inserted falls between tex2html_wrap_inline63256 and tex2html_wrap_inline64296, i.e., tex2html_wrap_inline63322. When we insert the pair tex2html_wrap_inline64576 into T we get the new leaf T' given by

displaymath64557

What happens when the leaf is full? That is, suppose we wish to insert the pair, tex2html_wrap_inline64576 into a node T which already has M-1 keys. Inserting the pair in its correct position gives a result of the form

displaymath64558

However, this is not a valid node in a B-tree of order M because it has M+1 subtrees and M keys. The solution is to split node T' in half as follows

eqnarray21134

Note, tex2html_wrap_inline64604 is a valid B-tree node because it contains tex2html_wrap_inline64492 subtrees and tex2html_wrap_inline64520 keys. Similarly, tex2html_wrap_inline64610 is a valid B-tree node because it contains tex2html_wrap_inline64612 subtrees and tex2html_wrap_inline64614 keys. Note that there is still a key left over, namely tex2html_wrap_inline64616.

There are now two cases to consider--either T is the root or it is not. Suppose T is not the root. Where we once had the single node T, we now have the two nodes, tex2html_wrap_inline64604 and tex2html_wrap_inline64610, and the left-over key, tex2html_wrap_inline64616. This situation is resolved as follows: First, tex2html_wrap_inline64604 replaces T in the parent of T. Next, we take the pair tex2html_wrap_inline64636 and recursively insert it in the parent of T.

Figure gif illustrates this case for a B-tree of order three. Inserting the key 6 in the tree causes the leaf node to overflow. The leaf is split in two. The left half contains key 5; and the right, key 7; and key 6 is left over. The two halves are re-attached to the parent in the appropriate place with the left-over key between them.

   figure21147
Figure: Inserting items into a B-tree (insert 6).

If the parent node fills up, then it too is split and the two new nodes are inserted in the grandparent. This process may continue all the way up the tree to the root. What do we do when the root fills up? When the root fills, it is also split. However, since there is no parent into which to insert the two new children, a new root is inserted above the old root. The new root will contain exactly two subtrees and one key, as allowed by Definition gif.

Figure gif illustrates this case for a B-tree of order three. Inserting the key 3 in the tree causes the leaf node to overflow. Splitting the leaf and reattaching it causes the parent to overflow. Similarly, splitting the parent and reattaching it causes the grandparent to overflow but the grandparent is the root. The root is split and a new root is added above it.

   figure21392
Figure: Inserting items into a B-tree (insert 3).

Notice that the height of the B-tree only increases when the root node splits. Furthermore, when the root node splits, the two halves are both attached under the new root. Therefore, the external nodes all remain at the same depth, as required by Definition gif.




next up previous contents index

Bruno Copyright © 1998 by Bruno R. Preiss, P.Eng. All rights reserved.