edited by
10,827 views
31 votes
31 votes
In a B+ Tree , if the search-key value is $8$ bytes long , the block size is $512$ bytes and the pointer size is $2\;\text{B}$ , then the maximum order of the B+ Tree is ____
edited by

5 Answers

Best answer
57 votes
57 votes

Let order of $B+$ tree is p then maximum number of child pointers $= p$ and maximum number of keys $= p-1$.

To accommodate all child pointers and search key, total size of these together can not exceed $512\;\text{bytes}$.

$2(p)+8(p-1) \leq 512$

$\implies p \leq52$

Therefore, maximum order must be 52.

edited by
4 votes
4 votes
Let the Order of the tree to be p. Every b+ tree node contains p children and p-1 data items where record pointer are not present in the internal nodes. So

p(Block pointer size)+(p-1)Key size<=Block size

p(2)+(p-1)8<=512

p=52.
0 votes
0 votes

B+ Tree internal node structure  Contain N-1 keys and N block pointers

(Where N is order of B+ tree)

N(Block Pointer Size) + N-1(Key size) <= Block size

N(2) + N-1(8) <= 512

By solving this equation we will get N = 52   

Answer:

Related questions

62 votes
62 votes
6 answers
1
Madhav asked Feb 14, 2017
18,239 views
Consider the following tables $T1$ and $T2.$$$\overset{T1}{\begin{array}{|c|c|c|} \hline \textbf {P} & \textbf {Q} \\\hline \text {2} & \text{2 }\\\hline \text{3} & \te...
44 votes
44 votes
3 answers
3
Arjun asked Feb 14, 2017
16,033 views
Consider the following database table named $\text{top_scorer}$.$$\overset{\text{top_scorer}}{\begin{array}{|c|c|c|}\hline\\\textbf{player}& \textbf{country}& \textbf...