Logo Data Structures and Algorithms with Object-Oriented Design Patterns in C++
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. E.g., consider a leaf node with n<M subtrees and n-1 keys of the form

displaymath65686

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_inline65706. Suppose the key to be inserted falls between tex2html_wrap_inline64406 and tex2html_wrap_inline65710, i.e., tex2html_wrap_inline64484. When we insert the pair tex2html_wrap_inline65706 into T we get the new leaf T' given by

displaymath65687

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

displaymath65688

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

eqnarray21956

Note, tex2html_wrap_inline65734 is a valid B-tree node because it contains tex2html_wrap_inline65628 subtrees and tex2html_wrap_inline65656 keys. Similarly, tex2html_wrap_inline65740 is a valid B-tree node because it contains tex2html_wrap_inline65742 subtrees and tex2html_wrap_inline65744 keys. Note that there is still a key left over, namely tex2html_wrap_inline65746.

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_inline65734 and tex2html_wrap_inline65740, and the left-over key, tex2html_wrap_inline65746. This situation is resolved as follows: First, tex2html_wrap_inline65734 replaces T in the parent of T. Next, we take the pair tex2html_wrap_inline65766 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.

   figure21969
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.

   figure22221
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 © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.