B-tree Insertions

---

An insertion searches the tree for the new key and inserts the new key into the leaf node that is identified by the search. Simply update the index record if an attempt to insert a new key into an index record that is not full. If the new key is the new largest key in the index record, the next higher level of the index must be updated.

When insertion into an index record causes it to be overfull, it is split into two records, each with half of the keys. Since a new index node has been created at this level, the largest key in this new node must be inserted into the next higher level node.

The figures show how fifteen keys are inserted in the order     C S H P Q A G X W Y B E U M K     into an order four B-tree.

• (a)—Beginning with an empty tree, the first four keys are inserted into the root.
• (b)—Inserting Q will cause the root node to overflow. React to the potential overflow by splitting the node, leaving two nodes: C H P and Q S. A new root node is created and the keys of the two leaf nodes—namely, P and S—are inserted into the root node.
• (c)—The next key, A, is inserted into the first leaf node. The insertion of G will then cause the first node to overflow. Again, the overflowing node is split and the new node inserted into the root.