Suppose that the following search field values are deleted, in the given order, from the B + -tree of Exercise 18.19, show how the tree will shrink and show the final tree. The deleted values are: 65, 75, 43, 18, 20, 92, 59, 37.

Question

What will be an ideal response?

Answer 1

An important note about a deletion algorithm for a B + -tree is that deletion of a key value

from a leaf node will result in a reorganization of the tree if: (i) The leaf node is less

than half full; in this case, we will combine it with the next leaf node (other algorithms

combine it with either the next or the previous leaf nodes, or both), (ii) If the key value

deleted is the rightmost (last) value in the leaf node, in which case its value will appear

in an internal node; in this case, the key value to the left of the deleted key in the left

node replaces the deleted key value in the internal node. Following is what happens to the

tree number 19 after the specified deletions (not tree number 20):

Deleting 65 will only affect the leaf node. Deleting 75 will cause a leaf node to be less

than half full, so it is combined with the next node; also, 75 is removed from the

internal node leading to the following tree:







Deleting 43 causes a leaf node to be le