Question

please step by step

Question V (B+ Trees) (16 pts] Consider the following B+ Tree where M=4 and L=5 2000 12|17| 271D I Show the B+ Tree after each one of the following operations (note that all operations are independent, that is, in b perform the operation on the original B+ Tree, not the one obtained after performing the operation in a). a) Delete(29) b) Insert(6), Insert(7), Insert(8) (show only the B+ Tree after all 3 operations)

Answer 1

We have been given the values of M and L which signify that:

• Internal Node of order M has maximum 'M' number of pointers and 'M-1' number of keys, minimum ⌈ M/2 ⌉ number of keys.
• Leaf Node of order L has maximum 'L' number of data elements and minimum ⌈ L/2 ⌉ number of values.

Thus for M = 4 and L = 5 we have,

• Maximum 4 pointers & 3 keys in Internal Nodes, minimum 2 pointers.
• Maximum 5 values and minimum 3 values in Leaf Nodes.

Lets, perform deletion first:

a) Delete(29):

After deleting 29, we'll have 2 elements in leaf node which violates the rules signified in the start which says that minimum 3 elements in leaf nodes.So, we need to merge in such a scenario.

201门 20 Delete 27 2 13 <3 27 29 33 20 27 20 12 Leat Nodis 2 22 18 14 33 5 22 26 20 o me r Merge with 20 20 22 hildren Bonrow 12 17 27 n inteanal Node 2.0 from 22 2.0 sialing 26 (So borw 22 20 27 trom Jyt sib) 27 33 33 Ans EE

b) Insert(6), Insert(7), Insert(8):

Insert elements one by one and whenever the above mentioned conditions get violated then move values to left or right sibling accordingly.

Given 20 20 Insert 62 23 12 27 27 212 18 27 20 1구 2 (2 20 29 22 2.9 2 2.2 14 14 33 26 19 33 2 16 19 gnsert 20 १त 23 give to ght 27uttir may node Value 20 2.0 27 12 29 im parent 12 22 23 33 2 26 /2 20 22 29 26 33 7 >S ks mal nada So