Q21

(a) Suppose you are given an empty $B^+$ tree where each node (leaf and internal) can store up to $5$ key values. Suppose values $1, 2,\ldots 10$ are inserted, in order, into the tree. Show the tree pictorially Do NOT show intermediate stages. (b) Suppose instead of splitting a node when it is full, we try to move a value to the left sibling. If there is no left sibling, or the left sibling is full, we split the node. Show the tree after values $1, 2,\ldots , 9$ have been inserted. Assume, as in (a) that each node can hold up to $5$ keys. (c) In general, suppose a $B^+$ tree node can hold a maximum of $m$ keys,and you insert a long sequence of keys in increasing order. Then what approximately is the average number of keys in each leaf level node. in the normal case, and with the insertion as in (b).