Question

Suppose that a block can contain at most four data values and that all data values are integers. Using only B+ trees of degree 2, give examples of each of the following :

a. A B+ tree whose height changes from 2 to 3 when the value 42 is inserted. Show your structure before and after the insertion.

b. A B+ tree in which the deletion of the value 42 leads to a redistribution. Show your structure before and after the deletion

Answer 1

a.

Consider a B+ tree with the two data values which are less than 42 and some other two values which are greater than 42.

The B+ tree before insertion is as follows:

The height of the tree is initially 2.

Now, insert 42 in the above B+ tree.

The data 42 is inserted in the right child of the above tree.

While inserting 42, the property of the tree becomes violated. Since, the maximum capacity of data values is 4.

Therefore, after inserting 42, the tree becomes as follows:

The height of the tree becomes 3.

b.

The B+ tree before insertion is as follows:

The height of the tree is initially 3.

Tree after deletion 42 from the above tree.

The height of the tree remains same.

The nodes 47 and 49 are distributed. After 42 is deleted the redistribution takes place.