(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

- 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,\ldots , 9$ have been inserted. Assume, as in (a) that each node can hold up to $54 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).

## 2 Answers

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**

__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}$

__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}$

### 2 Comments

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.

Why have you taken ‘m’ as the number of keys inserted?

Also, it is asking for in general case.

I think the solution for c) is simple.

As a long sequence of keys is inserted.

In normal case, whenever overflow occurs each leaf node will be split into $\left \lceil \frac{m-1}{2} \right \rceil$ keys in the left node and each node will have this many keys except the rightmost node.

In insertion as in (b), same as you said each leaf node except the right-most two leaf nodes will have maximum keys, which is m.

Therefore,

- Normal case: Average number of keys in each leaf node = $\left \lceil \frac{m-1}{2} \right \rceil$

- Insertion as in (b): Average number of keys in each leaf node = m.