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 _______

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 _______

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

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

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$

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