edited by
3,856 views
12 votes
12 votes

(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

  1.  after $6$ insertions, and
  2.  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,\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.

  1. in the normal case, and
  2. with the insertion as in (b).
edited by

2 Answers

12 votes
12 votes

A.i)

A.ii)


B)

The next 2 insertions weren’t asked in the question but will help you to understand part C of this question.


 

C.  Insert a LONG SEQUENCE of keys in INCREASING ORDER

  1. In normal case: Insertion always will be done at the rightmost leaf node, and all nodes will have exact $\lfloor \frac{m+1}{2} \rfloor $ keys expect this rightmost leaf ( no of keys can vary from $\lfloor \frac{m+1}{2} \rfloor $ to $m$ for rightmost leaf).

 

            For a long sequence, we can say the average is approximately $\lfloor \frac{m+1}{2} \rfloor $ (This is the answer).

            (There are two possible answers for this part, I left it on the reader to find out the second one)

            Because all nodes will have $\lfloor \frac{m+1}{2} \rfloor $ keys except $1$ rightmost node.

            we can also find the exact average in this case:

            Let there are $n$ keys in total ( inserted in increasing order),

            No of leaf nodes will be exactly $\left \lfloor \frac{n}{\left \lfloor \frac{m+1}{2} \right \rfloor} \right \rfloor$

            Average number of keys in leaf would be: $\frac{n}{\left \lfloor \frac{n}{\left \lfloor \frac{m+1}{2} \right \rfloor} \right \rfloor}$

 

  1. With insertion as in (B):  In this case, we can observe until the left sibling is full, we are shifting a key to the left leaf. As we insert more and more keys all leaf nodes are filled except the rightmost two leaves, the rightmost $2$ leaves can have any number of in $\lfloor \frac{m+1}{2} \rfloor $ to m each.

            For a long sequence, we can say the average is approximately $m$. ( Same reasoning as case i )

            we can find the actual average in this case as well, 

            Let there are $n$ keys in total ( inserted in increasing order),

            Number of leaf nodes in this case will be $\left \lceil \frac{n}{m} \right \rceil$,

            so average number of keys would be: $\frac{n}{\left \lceil \frac{n}{m} \right \rceil}$

edited by

Related questions

45 votes
45 votes
4 answers
1