The Gateway to Computer Science Excellence
+3 votes
313 views
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 ?
in Databases by Loyal (7k points)
edited by | 313 views

1 Answer

+6 votes
Best answer

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$

by Boss (27.4k points)
selected by
0
Sir why for sparse you divided 500 by 10 but for dense you divided by 15 ?

Is it becasue in dense we need to store index block corresponding to every record hence every record will have a  (Search key,Block pointer) right sir?

And for sparse we know that practically we create one index per block so you first decided how many blcoks will be required for total number of records and then did the same approach ???
0

Sir why for sparse you divided 500 by 10 but for dense you divided by 15 ?

No. I did not @Na462. Check again. Your rest of the argument is correct.

0
ohk got it sir
0
Sir one more thing how this question is different from this below question :-

Let there is a Table named Stud_records  with 3000 records of fixed length , each record size is 50 Bytes and records are stored in a block of size 512 Bytes , If secondary index is built on the key field of size 10 Bytes and a block pointer of size 5 Bytes , then the number of first level index blocks are ______

Because sir since We are using secondary index that means we would be using Dense indexing so if we follow above approach since we have 3000 records so we need 3000 (Search key , Block Pointer) so at first level we should have (3000/15)ceil = 200

But this is wrong What's the difference sir ?
0

and records are stored in a block of size 512 Bytes , If secondary index is built on the key field of size 10 Bytes and a block pointer of size 5 Bytes

Each Block size is 512 Bytes. Hence, We can only store $\left \lfloor \frac{512}{15} \right \rfloor = 34$ (Search key, Pointer) pairs. And We have 3000 such pairs to store. So, We need $\left \lceil \frac{3000}{34} \right \rceil = 89$ Blocks to store at the first level of index.

What's the difference sir ?

Just Think logically in such questions.  First you need to find How much you can store in One block.

0
Sir,since in the question it was said that the secondary indexing is used which means Dense indexing. Suppose sparse indexing had been said then the result would have been :-

Since records = 3000

Size of record = 50B

Block Size = 50B

Number of records per block = (512 / 50)floor = 10.

Means i can store 10 records per block. So total Blocks Required for 3000 Records = 300.

Now we need to store 300 (Search Key,Record Pointer) = (300/34 ) ceil = 9 Blocks in 1st level.

 

Is it correct Sir ?
0

Sir,since in the question it was said that the secondary indexing is used which means Dense indexing. Suppose sparse indexing had been said then the result

I have answered for Sparse as well as Dense index at first level. Refer it. And After that if you have some doubt, Let me know.  

0

Since records = 3000

Size of record = 50B

Block Size = 50B

Number of records per block = (512 / 50)floor = 10.

Means i can store 10 records per block. So total Blocks Required for 3000 Records = 300.

Now we need to store 300 (Search Key,Record Pointer) = (300/34 ) ceil = 9 Blocks in 1st level.

 

Is it correct Sir ?

Which Question you have answered here ??  

0

Let there is a Table named Stud_records  with 3000 records of fixed length , each record size is 50 Bytes and records are stored in a block of size 512 Bytes , If secondary index is built on the key field of size 10 Bytes and a block pointer of size 5 Bytes , then the number of first level index blocks are ______
 

For this Question, The Question Says that  if  "secondary index is built on the key field" it means that they are using Dense indexing not sparse, because Secondary means unclustered and we can't use Sparse indexing here because of non matching order,so it means Dense indexing is Used. 

My point is that if say same question had been asked but with sparse indexing then is my above Solution Right sir ?

0

@Na462 https://gateoverflow.in/192287/indexing What should be the answer to this question !

Why did anu used 666/15 for number of blocks at second level and why not 667/15

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
50,737 questions
57,293 answers
198,233 comments
104,916 users