GATE CSE 2001 | Question: 22

Question

We wish to construct a $B^+$ tree with fan-out (the number of pointers per node) equal to $3$ for the following set of key values:

$80, 50, 10, 70, 30, 100, 90$

Assume that the tree is initially empty and the values are added in the order given.

1. Show the tree after insertion of $10$, after insertion of $30$, and after insertion of $90$. Intermediate trees need not be shown.
2. The key values $30$ and $10$ are now deleted from the tree in that order show the tree after each deletion.

Comments

Same like btree

---

B+ tree with fan-out?

What does that mean.

Anyway its always fan-out only.

---

vijaycs i agree, although overflow at the internal node is at >2, overflow at leaf should be >3.

Answer 1

$(a) \ B^{+}$ tree insertion: $80,50,10,70,30,100,90$

Order of $B^{+} = p =3$

• Overflow: When number of key values exceed $p-1=3-1 = 2$

Tree after insertion of  $10:$

Tree after insertion of  $30:$

Tree after insertion of  $90:$

$(b)$

• Underflow: if leaf node contain $\left \lceil \frac{p}{2}\right \rceil - 1 = 2-1 = 1$ key values.

Deletion of key-value $30:$

Deletion of key-value $10:$

Here when we delete the key-value $10$ then underflow happened, so we can merge this node with the right sibling.

When we merge two nodes then the parent node one value needs to come down i.e. $50$ here.

Now if we try to bring $50$ down then that node will again suffer from underflow as it will become empty.

so we will try to merge this node it with its right sibling i.e. the node which contains $70$

Again, When we merge two nodes(nodes in the 2nd level that contain 50 and 70) then one value of the parent node (i.e. node having $50,70$) needs to come down

So we will bring $70$ down and merge it with $50$ since bringing $70$ down will not cause underflow as $80$ is present in the parent node.

Try it out: https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html

Comments

Here, while adding 100, 70 will become the root node and as it's a B+ tree we don't save copy of 70 at internal node, rather 70 directly becomes the root node. Here, 70 is present as internal node in subquestion (a) is incorrect. Please check.

Answer by @jaswanth431 is the best answer.

yes corrected now

---

Now fine right?

---

Yes, it’s perfect now. :) Thank you.

Answer 2

While splitting an internal node we push the middle element to parent and we don’t maintain a copy of that in child internal node.

But while spitting a leaf node we push the middle one to parent and we keep a copy in leaf node as well.

a) 

We don’t keep a copy of 70 in child internal  node when inserting 100

 

b)After deleting 30 and 10 relsuting tree is

 

Play with this tool for better understanding 

https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html

Comments

This should be the correct answer.

---

BEST answer.

---

@Shashwat Pandey or @jaswanth431 could anyone of you please mention the steps too

Answer 3

in the B+ tree order of internal node and order of leaf node are different 

order of internal node is maximum no of children 

order of leaf node is maximum no of key-value pair in the leaf 

in the question, it is given that 

B+ tree with fan-out (the number of pointers per node) equal to 3

so from this, we can easily conclude that the order of the internal node is 3

and order of leaf node is 2   ( just think about it why it is 2 ?? you will get the answer )

for internal node 

since order = 3, so we can have 2 key elements in a node this is  not a problem but when we have 3 key then we have to split them

for leaf node

since order = 2, so we can have 2 key elements in a node with no problem but when we have 3 key then we have to split them

correction in the diagram: every leaf node will point to the next leaf node, by doing this we can observe the fanout of each node is 3

 

 ( now I am giving the answer of question which I had asked earlier  )

Q: why the order of leaf node is 2?

it is because given fan-out (the number of pointers per node) equal to 3 

one pointer point to next leaf and two-pointer point to the record means there are maximum  two record pointer 

and order of leaf node is the maximum number of key-value pair 

so it is 2

Comments

Few doubts:

1. After inserting 100 and splitting the nodes, the node containing 70,80 is pointing to 2 child nodes. Is it correct. Which  pointer will be NULL?

2. In final tree, Root node is having 2 elements. But in Root node there should be only one element. So to split this node so that root contains one element

---

Here, while adding 100, 70 will become the root node and as it's a B+ tree we don't save copy of 70 at internal node, rather 70 directly becomes the root node. Here, 70 is present as internal node in subquestion (a) is incorrect. Please check @Gurdeep Saini Sir.

 

---

@Gurdeep Saini  one thing to keep in mind that in $B^{+}$ tree internal nodes can’t repeat so while splitting at 70,80  , 70 will be on top 80 will be in its right node