680 views
1 votes
1 votes

Consider a block of a size such that it can hold:
• either 5 records of a relation R, or
• be used as a B+ tree internal node with degree 11, or
• B+ tree leaf node with degree 10.
If R has 1000 records, then the smallest number of blocks that could be used to store R and a
sparse B+ tree index on key of R is ________.

2 Answers

4 votes
4 votes
A block can hold either 5 data records, or 11 block pointers(for internal node) or 10 record pointers(for leaf node)

Blocking factor(number of records per block)= total number of records/number of records per block  = 1000/5= 200

So 200 blocks are needed to store the data records.

now first level index blocks= ceil(200/10)=20 (since each record pointer in the leaf points to one data block as sparse indexing is used)

Second level index blocks= ceil(20/11)=2

Third level index blocks=ceil(2/11)=1

SO number of blocks needed= 200(for data file)+20(first level index)+2(second level index)+1(third level index i.e.root)=223

hence 223 blocks are required in total.
0 votes
0 votes
one block can store 11 block pointers. (internal node)

one block can store 10 keys (leaf node)

one block can store 5 records.

R has 1000 records.

------------------------------------------------------------------------------------------

therefore number of blocks for storing relation is (1000/5) = 200

---------------------------------------------------------------------------------------------

For Index file :

an index file contains tuples of (key + block pointer)

we need 200 pointers in an index file.

------------------------------------------------------------------

so 1block - 11pointers

then 18.18 (= 19)blocks - 200pointers

------------------------------------------------------

1block - 10keys

20blocks - 200keys

-----------------------------------------------------

therefore we need minimum,

200(storing relation) + 19(for block pointers in index file) + 20(for keys in index file) = 239 Blocks
edited by

Related questions

0 votes
0 votes
1 answer
1
pranjalgennext asked Jan 13, 2017
303 views
Assume a B-plus tree as:Size of search key=15BSize of block=512BSize of record pointer=9BSize of block pointer=8BWhat is the maximum number of nodes that can be accomodat...
0 votes
0 votes
1 answer
2
pranjalgennext asked Dec 27, 2016
260 views
What is the maximum number of nodes if a B+ tree has order 4 and number of levels as 6?
0 votes
0 votes
2 answers
3
pranjalgennext asked Dec 27, 2016
1,174 views
What is the maximum number of records that can be indexed for a B+ tree of 4 levels with order 10 and root at level 1?
0 votes
0 votes
1 answer
4