edited by
2,133 views
4 votes
4 votes
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 _______
edited by

3 Answers

Best answer
10 votes
10 votes
  • 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
3 votes
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
1 votes
1 votes
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

Related questions

4 votes
4 votes
2 answers
1
target2017 asked Jan 30, 2017
2,025 views
Please explain how they merged.(Modified)
5 votes
5 votes
2 answers
3
3 votes
3 votes
1 answer
4