edited by
23,234 views
44 votes
44 votes

The order of a leaf node in a $B^+$ - tree is the maximum number of (value, data record pointer) pairs it can hold. Given that the block size is $1K\;\text{bytes}$, data record pointer is $7\;\text{bytes}$ long, the value field is $9\;\text{bytes}$ long and a block pointer is $6 \;\text{bytes}$ long, what is the order of the leaf node?

  1. $63$
  2. $64$
  3. $67$
  4. $68$
edited by

6 Answers

Best answer
68 votes
68 votes

The answer is option A.

$B_{p} + P(R_{p} + \text{Key} ) \leq \text{BlockSize}$

$\implies 1\times 6 + n(7 + 9) \leq 1024$

$\implies n \leq$ $63.625$.

So, $63$ is the answer.

edited by
7 votes
7 votes

For leaf nodes order is-

n*(K+RP)+BP <= Block size

and for non-leaf nodes order is-

n*BP+(n-1)K <= Block size

Here question is about Leaf nodes so it would be

n*(K+RP)+BP <= Block size

Therefore, n*(9+7)+6 <= 1024

                  16n<=1018

                    n <= 63.6

So, n is 63. Hence option A is correct.

 

3 votes
3 votes

For tree of order p, leaf nodes can have max p-1 keys. Hence

$(p-1)(DP + V) + BP <= Block_Size$

(p-1)16 + 6 <= 1024

p = 64

Reference: https://en.wikipedia.org/wiki/B%2B_tree#Overview

Answer:

Related questions

64 votes
64 votes
15 answers
1
Arjun asked Jul 6, 2016
36,698 views
Consider the following segment of C-code:int j, n; j = 1; while (j <= n) j = j * 2;The number of comparisons made in the execution of the loop for any $n 0$ is:$\lceil \...
27 votes
27 votes
4 answers
2
Kathleen asked Sep 21, 2014
33,739 views
The message $11001001$ is to be transmitted using the CRC polynomial $x^3 +1$ to protect it from errors. The message that should be transmitted is:$11001001000$$110010010...
33 votes
33 votes
4 answers
3