The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+15 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 (68.8k points) | 1.9k views

3 Answers

+32 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 Veteran (35.8k 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...
+4 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 Boss (7.4k points)
–4 votes
Degree =(disk block size)/((index ptr size)*(student name length))=16, option a.
answered by Loyal (3.2k points)

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

32,443 questions
39,188 answers
36,563 users