(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,.....10 are inserted, in order, into the tree. Show the tree pictorially
- after 6 insertions, and
- after all 10 insertions
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,......, 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).