search
Log In
4 votes
803 views
Consider the following Node definitions of B Tree and B+ Tree
Order P for root node between 1 to 2P keys for other nodes between P to 2P keys If disk block size is of 2048B and key is  20B . Block pointer is 30B . Record Pointer is 25B . Difference between order of B tree with B+ Tree is _______
in Databases
edited by
803 views
1
@pc I think there is typo in block size.
0
since,normally when order = m then in b-trees atmose m-1 keys are stored in nodes and thre can be atmost m tree pointers and hence,formula is

m-1*(key value + record pointer ) + m*block pointer < block size.

but here,it is given that for order P,a nodecan have maximum 2P keys,

hence should it be 2P*(key value + record pointer ) + (2p+1)*block pointer < block size.//as there can be 2P keys,hence 2p+1 tree pointers

is this correct??

and for b+ trees,for internal node-

2P(key value) + 2P*(block pointer) <block sizze as internal nodes have no record pointers.

please correct me @pC
0
@Akriti. u are correct. Just follow the definition they give. If not given, then follow ur convention.

 

SO, your answer would be perfectly correct.
0
I have posted answr. Just see if you get the same.

3 Answers

7 votes
 
Best answer
  • Order definition in this QS: based on no of keys
  • Order will be based on maximum occupancy which is given as $2P$ keys
  • We need to compare P values with $B$ and $B+$ Tree

$\begin{align*} &\text{B Tree For any node }\rightarrow \\ &\left ( \text{no-of-keys} \right )*\left [ \text{key-size} + \text{record-ptr-size} \right ] + \left ( \text{no-of-keys+1} \right ) * \left [ \text{block-ptr-size} \right ] \leq 2048\\ &\Rightarrow 2P*\left [ 20+25 \right ] + \left ( 2P+1 \right )*\left [ 30 \right ] \leq 2048 \\ &\Rightarrow 90P+60P + 30 \leq 2048 \\ &\Rightarrow P = \left \lfloor \frac{2018}{150} \right \rfloor \\ &\Rightarrow P = 13 \\ \end{align*}$

$\begin{align*} \\ \hline \\ &\text{B+ Tree For Leaf node }\rightarrow \\ &\left ( \text{no-of-keys} \right )*\left [ \text{key-size} + \text{record-ptr-size} \right ] + 1 * \left [ \text{block-ptr-size} \right ] \leq 2048\\ &\Rightarrow 2P*\left [ 20+25 \right ] + 1*\left [ 30 \right ] \leq 2048 \\ &\Rightarrow 90P+ 30 \leq 2048 \\ &\Rightarrow P = \left \lfloor \frac{2018}{90} \right \rfloor \\ &\Rightarrow P = 22 \\ \end{align*}$

$\begin{align*}\\ \hline \\ &\text{B+ Tree For NON-Leaf node }\rightarrow \\ &\left ( \text{no-of-keys} \right )*\left [ \text{key-size} \right ] + \left ( \text{no-of-keys+1} \right ) * \left [ \text{block-ptr-size} \right ] \leq 2048\\ &\Rightarrow 2P*\left [ 20 \right ] + \left ( 2P+1 \right )*\left [ 30 \right ] \leq 2048 \\ &\Rightarrow 40P+60P+30 \leq 2048 \\ &\Rightarrow P = \left \lfloor \frac{2018}{100} \right \rfloor \\ &\Rightarrow P = 20 \\ \end{align*}$


In this question, they have given record pointer size and In $B+$ record pointers are there in only leaf nodes.

  • Considering leaf nodes of $B+$ 
  • Difference between order of B tree with B+ Tree is $-9$
  • Considering internal nodes of $B+$
  • Difference between order of B tree with B+ Tree is $-7$


edited by
0

@Debashish Explanation is perfect. However if considering the internal node ans should be -7. Difference is asked and not the absolute difference.

1
yes I have seen you last two comments .. then it would be $-7$ and $-9$
0
How do u convert the given order to equations ? Not able to undersand
0
thats the basic of structure of B+ and B trees. You can read from navathe. The block size is given and order definition is given in question. Just use that.
3 votes

B+-tree:

key size * #max keys in node +  block ptr size * #block ptrs <= block size

20*(2P) + 30(2P+1) <= 2048

P = 20

B tree:

key size* #max no of keys + block ptr size* # block ptrs + record ptr size*#record pointers <= block size

20(2P) + 30(2P+1) + 25(2P) <=2048

P = 13

Thus, difference = 20-13 = 7


edited by
0
small calculation mistak..:-P

for B+ tree ,it will be 20
0
Nop, checked again. It 13. Could you give your calculation? or point where I am wrong?
0
20*(2P) + 30(2P+1) <= 2048

40P +60P +30< =2048

100P<=2018

P<=20.18
0
Got it :P  Editing
0
Should this QS mention the type of B+ nodes for comparison or that is implicit (internal) ?
0
@Sushant, We dont include include Record pointer in the internal node in B+ Tree. Record pointers are included in the internal node of B Tree. Solution is correct but ans should be -7.
0
pC?/ what made easy says ? answer ?
1 vote
for B tree:30x + 45x-45 <=2048  x =27    2P+1 =26   P = 13

For B+ tree: 30x + 20x-20 <=2048   x =41    2P + 1 =41   P =20

20-13 = 7
0
@bad_engineer,pls check my comment above..

Related questions

3 votes
2 answers
1
0 votes
0 answers
2
197 views
According to me, since the B trees have a data pointer for each of the key values in their internal nodes, the I/O access for them should take less time since we do not need to traverse down all of the tree.
asked Dec 28, 2018 in Databases Harsh Kumar 197 views
0 votes
0 answers
3
150 views
By default take ROOT at level 1 or 0? and if asked for B tree then take all the levels but for B+ records only at leaf so only leaf level keys right?
asked Dec 18, 2018 in Databases Markzuck 150 views
0 votes
0 answers
4
163 views
The Following key values are inserted into B+ tree in which order of internal node is 4, and that of leaf node is 3, in the sequence given below.The Order of internal node is the maximum number of tree pointers in each node and the order of leaf node is the maximum ... empty 50,15,30,40,35,20,8,10,5 are inserted.The Maximum number of times nodes get spilt up as a result of these insertion ___
asked Nov 25, 2018 in Databases jatin khachane 1 163 views
...