Page 180 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Unit 8: B-trees

8.5 Inserting a New Item Notes

When inserting an item, first do a search for it in the B-tree. If the item is not already in the B-tree,
this unsuccessful search will end at a leaf. If there is room in this leaf, just insert the new item
here. Note that this may require that some existing keys be moved one to the right to make room
for the new item. If instead this leaf node is full so that there is no room to add the new item, then
the node must be “split” with about half of the keys going into a new node to the right of this
one. The median (middle) key is moved up into the parent node. (Of course, if that node has no
room, then it may have to be split as well.) Note that when adding to an internal node, not only
might we have to move some keys one position to the right, but the associated pointers have to
be moved right as well. If the root node is ever split, the median key moves up into a new root
node, thus causing the tree to increase in height by one.
Insert the following letters into what is originally an empty B-tree of order 5: C N G A H E K Q M
F W L T Z D P R X Y S Order 5 means that a node can have a maximum of 5 children and 4 keys.

All nodes other than the root must have a minimum of 2 keys. The first 4 letters get inserted into
the same node, resulting in this picture:

A C G N

When we try to insert the H, we fi nd no room in this node, so we split it into 2 nodes, moving
the median item G up into a new root node. Note that in practice we just leave the A and C in the
current node and place the H and N into a new node to the right of the old one.

G

A C H N

Inserting E, K, and Q proceeds without requiring any splits:

G

A C E H K N Q

Inserting M requires a split. Note that M happens to be the median key and so is moved up into
the parent node.

LOVELY PROFESSIONAL UNIVERSITY 175