B+ tree indexing

Question

Which of the following statements true for $B$ tree and $B^+$ tree index?

A. $B$ tree index faster for range queries compare to $B^+$ tree index.

B. If disk block allocated for $B^+$  tree index and same size disk block allocated for $B$ tree index then number of index blocks and I/O cost of $B^+$  tree index less than or equal to B tree index for given distinct keys.

C. If disk block allocated for $B^+$  tree index and same size disk block allocated for $B$ tree index. Then $B$ tree index access cost less than or equal to $B^+$  tree index for given distinct keys.

D. If number of keys that can store in $B$ tree and $B^+$  tree index is same then I/O cost of $B^+$  tree index less than equal to I/O cost of $B$ tree index for random access of same key from set of distinct keys.

Comments

For option B, since the disk block is the same, the order will be higher in B+ trees which means fewer levels. So on average, the I/O cost of B+ tree is lesser than B tree since the level is decreased.

I don't know about the option D

Answer 1

Answer : B 

Let's check each Option :

Option A  : Range Queries mean  sequential access of records. Range Queries are like this :  $20 \leq P \leq 50$ Hence, Sequential Access.  And $B^+$ Trees are more suitable for  sequential access of records since they have All the keys at the bottom level as well while each Bottom level Node pointing to the next bottom level node. Hence, Option A is False.

Option D : Correction in Option D... " If number of keys that can store in B tree and B⁺ tree index node is same"

You have already asked a Question completely based on Option D before. Refer here : https://gateoverflow.in/216456/b-tree  

In this above link, I had stopped at "Order is same  is One Basis of Comparison between B and $B^+$ Tress. There are other situations in which you would get better results for B⁺ Tree Like When the Node/Block Size is same etc." Now, Let's see How.

Option B and C :  If disk block allocated for B⁺ tree index is same size as disk block allocated for B tree index then We can put more number of keys in $B^+$ tree node as Unlike B tree, We do not need to store Record pointers along with every key in $B^+$ tree node. So, Because of not having to store Record pointers in the Internal nodes in $B^+$ tree, We get less number of levels in $B^+$ tree index for large number of keys than B tree index. Hence,  number of index blocks and I/O cost of B⁺ tree index less than or equal to B tree index for given distinct keys.

---

Let's keep it simple. You know that whatever is the Situation/basis of comparison between B and B+ trees..... The Performance will depend on "Number of Levels". So, Now what we have to do it check the Number of levels in both tress (But for Large number of keys...As happens in practical life)

1. When Disk Block Size is same :

Disk block means Node. So, Node size is same. So, We have advantage in B+ tree because In B+ tree we do not need to store Record pointers in the internal nodes, Hence we can store More number of keys in One node. Which leads to less number of levels. 

Now, You must be thinking that in B+ tree, we have All the Internal keys repeated at bottom level as well which is not the case in B tree and which might bring disadvantage to B+ tree. Yes, It will surely bring disadvantage to B+ tree But that would not have much impact when large number of keys are stored. Let me explain How!!

Take a case and analyze. Will give your more intuition about it. Either take some Previous GATE question data or consider this..Say, Block size is 1024 Bits, Key size is 10 bits, Pointer size (Record and Node pointer both) = 6 bits.. Now, Try and see. Apply this data for both B+ tree and B tree, Because it is given that here Block size is same (Not tht Order is same) You will find that Because we don't need to store record pointers in the internal nodes in B+ tree, You can store 63 Keys per internal node whereas in B tree you can only store 43 keys per internal node. That's huge difference when large number of keys will be stored. Even if you have to repeat all the internal keys in the bottom level, You would have less number of levels in B+ tree than in B tree.

Practically also, This same thing happens. Disk Block size is same and we have advantage in B+ tree.

---

2 .When Order is same :

Here also Disk block size is same but it's effect/advantage on B+ tree is finished because We have to keep the Order same. Now, We cannot store more number of keys in One node in B+ tree. So, Here the fact that Keys repeat in B+ tree brings disadvantage to B+ tree.

Refer my answer here : https://gateoverflow.in/216456/b-tree

Comments

Sir hold on i didn't understand, in my previous question there was not said anything like disk blocks for b tree and b plus trees are same only order was specified there u used different reasoning that the keys repeats in b plus tree so more number of levels but here when the disk blocks are same a different thinking used.

Why please highlight on this sir

---

Sir Please Reply

---

And sir why we aren't considering that the keys in b+tree repeats like as sir u did in previous mine asked question.

And sir which notion to follow as default.

---

In B+ tree duplicate key are present . So levels are more as compaer to B tree.

---

Yes sir but above for option C We considered block size not number of keys and gave different notion using block size why is it so ?

---

Hi @Na462

Sorry for the delay.

Let's keep it simple. You know that whatever is the Situation/basis of comparison between B and B+ trees..... The Performance will depend on "Number of Levels". So, Now what we have to do it check the Number of levels in both tress (But for Large number of keys...As happens in practical life)

1. When Disk Block Size is same :

Disk block means Node. So, Node size is same. So, We have advantage in B+ tree because In B+ tree we do not need to store Record pointers in the internal nodes, Hence we can store More number of keys in One node. Which leads to less number of levels. 

Now, You must be thinking that in B+ tree, we have All the Internal keys repeated at bottom level as well which is not the case in B tree and which might bring disadvantage to B+ tree. Yes, It will surely bring disadvantage to B+ tree But that would not have much impact when large number of keys are stored. Let me explain How!!

Take a case and analyze. Will give your more intuition about it. Either take some Previous GATE question data or consider this..Say, Block size is 1024 Bits, Key size is 10 bits, Pointer size (Record and Node pointer both) = 6 bits.. Now, Try and see. Apply this data for both B+ tree and B tree, Because it is given that here Block size is same (Not tht Order is same) You will find that Because we don't need to store record pointers in the internal nodes in B+ tree, You can store 63 Keys per internal node whereas in B tree you can only store 43 keys per internal node. That's huge difference when large number of keys will be stored. Even if you have to repeat all the internal keys in the bottom level, You would have less number of levels in B+ tree than in B tree.

Practically also, This same thing happens. Disk Block size is same and we have advantage in B+ tree.

---

2 .When Order is same :

Here also Disk block size is same but it's effect/advantage on B+ tree is finished because We have to keep the Order same. Now, We cannot store more number of keys in One node in B+ tree. So, Here the fact that Keys repeat in B+ tree brings disadvantage to B+ tree.

Refer my answer here : https://gateoverflow.in/216456/b-tree

---

Have edited the same in the answer also. Read complete answer for better understanding.

---

Thank u so much sir

---

sir,is it possible to exceed  key in a node?.

---

Sir, In B tree record pointers are present in every node and in B+ tree only in leaf nodes. So when CPU requests for a record whose search key is at root node in B tree then it does not need to traverse to leaf node to get its record pointer but in B+ tree it needs to traverse to leaf node to get record pointer. So in this case I/O time for B tree will be less than B+ tree right? This makes option B also false.

Please correct me if I am getting it wrong.

---

@Ayushak you are only considering the best case but I think when we need to check a statement we should check it in a more generalised way considering general  posssiblities.