The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+19 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 (59.6k points)
edited by | 3.1k views

3 Answers

+34 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 pointer size is 4 bytes. Thus we can write

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

answered by Boss (34k points)
selected 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
+6 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 (7.5k points)
–5 votes
Degree =(disk block size)/((index ptr size)*(student name length))=16, option a.
answered by Active (3.3k points)

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

42,415 questions
48,473 answers
62,887 users