The Gateway to Computer Science Excellence
+4 votes
741 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 by Boss (21.5k points)
edited by | 741 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$

by Veteran (57.2k points)
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

by Boss (18.5k points)
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
by Active (4.5k points)
0
@bad_engineer,pls check my comment above..

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,741 questions
57,253 answers
198,062 comments
104,699 users