edited by
2,061 views
4 votes
4 votes
A database relation has $5000$ records block can hold either $10$ records or $15$ keys and pointer pairs. If sparse index is used at $1^{st}$ level and multilevel indexing is used in system, then the number of disk block required to store relation and index is _______.

1. Please explain the approach used.

2. what had been the answer if instead of sparse it would have been dense indexing ?
edited by

1 Answer

Best answer
8 votes
8 votes

1. When Sparse index is used at $1^{st}$ level :

Database relation has 5000 records. And block can hold 10 records. Hence we need $5000/10 = 500$ Blocks to store the Relation records.

Now, Coming to making an index... At $1^{st}$ level, Sparse index has been used. So, In Index, at 1st level, For each Block, We will  have One $(Search Key, Block Pointer)$ pair. Hence, At first level we will have $500$ such pairs (Because relation has 500 Blocks).. And it is given that  block can hold 15 keys and pointer pairs. Hence, To store $500$ such Pairs, We need $\left \lceil \frac{500}{15} \right \rceil = 34$ Blcoks.

So, Now at 1st level of Index, We have $34$ Blocks, So, At second level, we will have $34$ $(Search Key, Block Pointer)$ pairs. And  it is given that a  block can hold 15 keys and pointer pairs. Hence, To store $34$ such Pairs, We need $\left \lceil \frac{34}{15} \right \rceil = 3$ Blocks at 2nd level. (NOTE that in Any kind of Indexing, Only 1st level can be either Sparse or Dense, Rest of the levels are Always Sparse... So, 2nd level will always be Sparse)

So, Now at 2nd level of Index, We have $3$ Blocks, So, At third level, we will have $3$ $(Search Key, Block Pointer)$ pairs. And And it is given that a  block can hold 15 keys and pointer pairs. Hence, To store $3$ such Pairs, We need $1$ Block at third level. (NOTE that in Any kind of Indexing, Only 1st level can be either Sparse or Dense, Rest of the levels are Always Sparse... So, 2nd level will always be Sparse)

So, Total number of Blocks required to store relation and Index = $500 (for \,\, relation) + 34 (at \,\,1st\,\,level) + 3 (at \,\,3nd,\,level) + 1 (at \,\,3rd\,\,level)  = 538 \,\,Blocks$


what had been the answer if instead of sparse it would have been dense indexing ?

We can make the 1st level of Index as Dense index..But rest of the levels will always be Sparse (Why?)
So, If we make 1st level as Dense index then we will have to store $5000$  $(Search Key, Block Pointer)$ pairs in 1st level and  it is given that a  block can hold 15 keys and pointer pairs. So, We need $\left \lceil \frac{5000}{15} \right \rceil = 334$ Blocks at 1st level of index. 

So, Now at 1st level of Index, We have $334$ Blocks, So, At second level, we will have $334$ $(Search Key, Block Pointer)$ pairs. And  it is given that a  block can hold 15 keys and pointer pairs. Hence, To store $334$ such Pairs, We need $\left \lceil \frac{334}{15} \right \rceil = 23$ Blocks at 2nd level. (NOTE that in Any kind of Indexing, Only 1st level can be either Sparse or Dense, Rest of the levels are Always Sparse... So, 2nd level will always be Sparse)

So, Now at 2nd level of Index, We have $23$ Blocks, So, At third level, we will have $23$ $(Search Key, Block Pointer)$ pairs. And it is given that a  block can hold 15 keys and pointer pairs. Hence, To store $23$ such Pairs, We need $2$ Blocks at third level. (NOTE that in Any kind of Indexing, Only 1st level can be either Sparse or Dense, Rest of the levels are Always Sparse... So, 2nd level will always be Sparse)

So, Now at 3rd level of Index, We have $2$ Blocks, So, At Fourth level, we will have $2$ $(Search Key, Block Pointer)$ pairs. And it is given that a  block can hold 15 keys and pointer pairs. Hence, To store $2$ such Pairs, We need $1$ Blocks at fourth level. (NOTE that in Any kind of Indexing, Only 1st level can be either Sparse or Dense, Rest of the levels are Always Sparse... So, 2nd level will always be Sparse)

So, Total number of Blocks required to store relation and Index = $500 (for \,\, relation) + 334 (at \,\,1st\,\,level) + 23 (at \,\,3nd,\,level) + 2 (at \,\,3rd\,\,level) + 1 (at \,\,4th\,\,level)  = 860 \,\,Blocks$

selected by

Related questions

0 votes
0 votes
0 answers
1
2 votes
2 votes
1 answer
3
3 votes
3 votes
1 answer
4
Na462 asked Jan 26, 2019
1,813 views