GATE CSE 2002 | Question: 2.23, UGCNET-June2012-II: 26
in Databases edited by
8,507 views
35 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$
in Databases edited by
8.5k views

Subscribe to GO Classes for GATE CSE 2022

4 Answers

49 votes
 
Best answer

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

21 Comments

Aren't they asking for degree,43 will be order- maximum no of children... Please clear the confusion
0
they have defined the degree as the maximum no. of pointers.
7
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?
0
Why we didn't count $p_{leaf}$ ? Then answer would be 42.
2
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...
0
Here Index pointer is given as 4B

Which is Record pointer not tree/node pointer

In above solution its equation for internal node of B+ tree

Are we taking Block pointer  = Record pointer here
2

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 ??

0

@

best choice of the degree (i.e. number of pointers per node) 

Moreover for leaf node you considered Record pointer  = Block pointer ?

0
Moreover for leaf node you considered Record pointer  = Block pointer

yes i did this
0
See now
0

 leaf node will have one sibling pointer in addition to maximum p−1 keys and p record pointers.

 i think i place of p-1 keys it should be p keys

0
No. Both should be $p-1$. I have corrected now.
1
this shows that https://gateoverflow.in/1261/gate2007-63-isro2016-59
in pace of p-1 both should be p in the leaf node
0

@ 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 

0

@Gurdeep Saini see how p is defined in both the questions.

@jatin khachane 1 corrected now. 

0

@ 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 ?

0

number of pointers per node

is it means

number of pointer in internal node=no. of pointer in leaf node 

0
I didnt understand
"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 "
1

For more clarity read the first paragraph of this link.

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

0
14 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

1 vote
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.

1 comment

why you are adding +4 in the solution.
0
0 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