Page 186 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Unit 8: B-trees

To insert the key “59”, we first simply search for that key. If 59 is found, the key is already in the Notes

tree and the insertion is superfluous. Otherwise, we must end up at a leaf node at the bottom
level of the tree where 59 would be stored. In the above case, the leaf node contains 58, 60, 61, and
room for a fourth key, so 59 is simply inserted in the leaf node in sorted order:
[58 59 60 61]
Now you’ll insert the key “77”. The initial search leads us to the leaf node where 77 would be
inserted, but the node is already full with 4 keys: 74, 75, 76, and 78. Adding another key would
violate the rule that order 2 B-trees can’t have more than 4 keys. Because of this “overfl ow”
condition, the leaf node is split into two leaf nodes. The leftmost 2 keys are put in the left node,
the rightmost 2 keys are put in the right node, and the middle key is “promoted” by inserting it
into the parent node above the leaf. Here, inserting 77 causes the 74-75-76-78 node to be split into
two nodes, and 76 is moved up to the parent node that contained 72 and 84:
Before inserting 77 After inserting 77
[ 72 84 . .] [ 72 76 84 .]
| | | | | | |
-+ | +- --+ | | +--
| | |
| +----+ +------+
| | |
v v v
[74 75 76 78] [74 75 . .] [77 78 . .]
In this case, the parent node contained only 2 keys (72 and 84), leaving room for 76 to be promoted
and inserted. But if the parent node was also already full with 4 keys, then it too would have to
split. Indeed, splitting may propagate all the way up to the root node. When the root splits, the
B-tree grows in height by one level, and a new root with a single promoted key is formed. (A
situation when an order n root node sometimes has fewer than n keys, just like the situation

described earlier when the root node stores the very first key placed in the B-tree.)

B-trees shrink when keys are deleted. To delete a key, first perform the usual search operation
to locate the node containing the key. (If the key isn’t found, it isn’t in the tree and can’t be
deleted.)
If the found key is not in a leaf, move it to a leaf by swapping the key with the logical “next” key.

In a B-tree, the “next” key is always the first key in the leftmost leaf of the right subtree.

Example: In this B-tree we want to delete “37”, which is not in a leaf. “xx” indicates key
values that don’t matter:
[ xx 37 xx xx ]
|
|
+->[ xx xx xx xx ]
|
|
+->[ xx xx xx xx ]
|
|
+->[41 43 . .]

You follow the pointer immediately to the right of 37 to find 37’s right subtree, then follow the
leftmost pointers in each subnode until we reach a leaf. The first key in the leaf is “41”, the logical

“next” key after 37 in the list of all keys in the tree. By swapping 37 and 41, we can move 37 to
a leaf node to set up a deletion without violating the key order or pointer order of the overall
B-tree.
Once the key we want is in a leaf, we can delete it. If at least n keys remain in the node, we’re
done, otherwise it is an “underflow”, since every node (except the root) must have at least n

keys.

LOVELY PROFESSIONAL UNIVERSITY 181