search
Log In
3 votes
775 views
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.
in Databases
retagged by
775 views

1 Answer

5 votes
 
Best answer

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


selected by
0
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
0
Sir Please Reply
0
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.
0
In B+ tree duplicate key are present . So levels are more as compaer to B tree.
0
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 ?
0

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

0
Have edited the same in the answer also. Read complete answer for better understanding.
0
Thank u so much sir

Related questions

0 votes
1 answer
1
599 views
Does values in Leaf nodes of B+ tree repeats or ever leaf node has an unique value?
asked Dec 15, 2017 in Databases iarnav 599 views
1 vote
1 answer
2
197 views
How to prove that if same size blocks are allocated to B trees and B+ trees then:- No. of index nodes in B tree >= No. Of index nodes in B+ tree
asked Oct 8, 2018 in Databases skywalker_19 197 views
20 votes
1 answer
3
2.5k views
Database file consists of $10,000$ records with record size of $100$ bytes, block size $512$ bytes. If sparse B+ tree index is built over given database file with search key size $22$ bytes and both block pointer and record pointer of size $12$ bytes each.Find out a)minimum index block required b)maximum index block required my answers a)$143$ b)$325$.
asked Oct 27, 2017 in Databases reena_kandari 2.5k views
5 votes
1 answer
4
483 views
Q : One basic doubt that is coming to my mind is whether number of splits in the process of insertion in B+ Tree indexing going to change if we consider left biasing and right biasing approach.Plz present any example to show if possible..
asked Oct 19, 2016 in Databases Habibkhan 483 views
...