edited by
14,022 views
42 votes
42 votes

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 by

6 Answers

Best answer
57 votes
57 votes

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.$

http://www.cburch.com/cs/340/reading/btree/index.html

edited by
16 votes
16 votes

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

3 votes
3 votes
(p-1)K+p*Bp<=Block Size

(p-1)8+ P*4=512

12p=520

p=43
3 votes
3 votes
I think the straightforward way to answer this question is as follows:

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.
Answer:

Related questions

45 votes
45 votes
4 answers
1
33 votes
33 votes
2 answers
2
Kathleen asked Sep 15, 2014
5,599 views
The following table refers to search items for a key in $B$-trees and $B^+$ trees.$$\begin{array}{|ll|ll|} \hline & \textbf {B-tree} & & \textbf {B}^+\text{-tree} \\\hl...