Chapter 14, Problem 4PE

Explanation of Solution

B⁺ -tree:

• In this case, initially it is considered that the B⁺-tree is empty and the values are inserted in ascending order.
• It is not possible to have a value less that n/2 as the non-root node and in this case the non-root node can only have 2-3 key values.
• The first two key values (2,3) get added to the root node.
• Next, when the key value 9 is inserted in the tree, it directly goes to the second level node, between key values 5 and 11.
• Next, when key value 10 is inserted in the B⁺-tree, it goes to a leaf node, after the key value 5 and 7.
• Next, when the key value 8 is inserted;
  • A new leaf node with key value 9 and 10 is created.
  • The key value 8 is added to the end of the leaf node with values 5 and 7.
• Next, when key value 23 is deleted from this B⁺-tree, the structure of the whole tree changes, as after removal of key value 23 from its leaf node, it has only one key value left, but this is not allowed. So,
  • That leaf node with key value 19 and 23 is removed from the tree.
  • This results in a change in the second level node with value 29...