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?

- $16$
- $42$
- $43$
- $44$

## 4 Answers

Answer: C

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 index pointer size is 4 bytes. Now a $ B^+$ tree has different structure for internal node and leaf nodes. While internal nodes can have upto $p-1$ key values and $p$ child pointers, leaf node will have one sibling pointer in addition to maximum $p-1$ keys and $p-1$ record pointers. Since our key is Name attribute which is not assumed to be unique it must be a secondary index and hence the record pointer must be an index pointer to primary index. This will ensure size of a leaf node is same as the size of a non-leaf node. Hence for a maximum sized node we can write

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

### 21 Comments

what @jatin khachane 1 is saying is correct

now i am taking p is the order of leaf node

so p(8+4)+4<=512

==> 12p<=508

==> p<=42.34

so p=42

so B is the option

now tell me what is wrong in my explanation ??

in pace of p-1 both should be p in the leaf node

@Arjun sir,

If record pointer = block pointer (in terms of size)

Then No of overall pointers will be same in Both internal node and leaf node ..am i right ?..Here in answer leaf node is considered as one which will give max no of pointers ..does it means record pointer size < block pointer size here

@Arjun sir,

But if we consider secondary indexing in index node we have pointer to record instead block ..doesn't this says record pointer is greater that block pointer ? hence less pointer in leaf ?

For more clarity read the first paragraph of this link.

https://docs.oracle.com/cd/E17275_01/html/programmer_reference/am_second.html

Size of 1 record = 8 + 4 = 12 Let the order be N. No. of index values per block = N - 1 (N - 1) 12 + 4 = 512 12N - 12 + 4 = 512 16N = 1009 N = 43.3333

Based on Geeksofgeeks solution.

The first thing to notice is that they have mentioned the degree as = number of any kind of pointer.

In a B+ tree we always have $number\: of \: pointers = number\: of \: keys\: +1$

i.e. in case of internal nodes, we know that we have one more pointer than keys. And in leaf nodes we have equal number of key-record pointer pairs and one extra pointer for next block pointer is also present.

Since they have mentioned the size of index pointer, i am taking internal nodes. We’ll have

$(n*Pointer)+(n-1)*key = 512$

$\Rightarrow (4n)+(n-1)*8 = 512$

$\Rightarrow n = \frac{520}{12}$

Obviously we’ll take floor, since we can’t exceed block size and hence the answer is 43.