The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+20 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$
asked in Databases by Veteran (52k points)
edited by | 3.9k views

3 Answers

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

answered by Boss (33.8k points)
edited by
Aren't they asking for degree,43 will be order- maximum no of children... Please clear the confusion
they have defined the degree as the maximum no. of pointers.
when to use the ceil or the floor function?
Record size is given and record pointer size is not given. You are taking record size in place of record pointer? it correct?
Why we didn't count $p_{leaf}$ ? Then answer would be 42.
What is the difference between degree and order of a b tree?
"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...
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

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



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

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

Moreover for leaf node you considered Record pointer  = Block pointer

yes i did this
See now

 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

No. Both should be $p-1$. I have corrected now.
this shows that
in pace of p-1 both should be p in the leaf node

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


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

@jatin khachane 1 corrected now. 


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


number of pointers per node

is it means

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

+9 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


K= key field

Rp= Record pointer

Bp= Block pointer

answered by Loyal (6.9k points)
+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.

answered by (125 points)
why you are adding +4 in the solution.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,535 questions
54,120 answers
71,034 users