2.9k views

A $B^+$ - tree index is to be built on the Name attribute of the relation STUDENT. Assume that all the student names are of length $8$ bytes, disk blocks are of size $512$ bytes, and index pointers are of size $4$ bytes. Given the scenario, what would be the best choice of the degree (i.e. number of pointers per node) of the $B^+$ - tree?

1. $16$
2. $42$
3. $43$
4. $44$
edited | 2.9k views

In a $B^+$ tree we want en entire node content to be in a disk block. A node can contain up to $p$ pointers to child nodes and up to $p-1$ key values for a $B^+$ tree of order $p$. Here, key size is 8 bytes and pointer size is 4 bytes. Thus we can write

$8(p-1) + 4p \leq 512 \\ \implies 12p \leq 520 \\\implies p = 43.$

selected
0
Aren't they asking for degree,43 will be order- maximum no of children... Please clear the confusion
+3
they have defined the degree as the maximum no. of pointers.
0
when to use the ceil or the floor function?
0
Record size is given and record pointer size is not given. You are taking record size in place of record pointer?..is it correct?
+1
Why we didn't count $p_{leaf}$ ? Then answer would be 42.
0
What is the difference between degree and order of a b tree?
0
"best choice" would be to have as many children as possible for a node because increasing the number of children reduces the height of the tree ... Reducing the height of the tree will reduce the number of index block accesses as we access one block for every level of b+ tree...

Ans : C

Here we have to calculate P(non-leaf) not P(leaf) bcz in order to calculate P(leaf) we require record pointer which is not given in the question.

P(leaf)= n(K+Rp) + Bp <= Block size

where,

K= key field

Rp= Record pointer

Bp= Block pointer

Degree =(disk block size)/((index ptr size)*(student name length))=16, option a.