in Databases edited by
2,237 views
7 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 $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.

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

2 Comments

Can anyone please tell about the answers for part (c) ?
0

this is also a possible way .

0

Subscribe to GO Classes for GATE CSE 2022

2 Answers

4 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

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,

  1. Normal case: Average number of keys in each leaf node = $\left \lceil \frac{m-1}{2} \right \rceil$
  1. Insertion as in (b): Average number of keys in each leaf node = m.
1
yes, You’re right, actually, I explained taking $m$ as the total number of keys inserted, I should have to take $n$ instead.
1
1 vote

I AM DOING INSERTION WITH LEFT BIASING

1 comment

Wrong solution. Where is 5,6 ??

Correct Answer : 

4

Related questions