The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+22 votes
3k views

Consider a file of 16384 records. Each record is 32 bytes long and its key field is of size 6 bytes. The file is ordered on a non-key field, and the file organization is unspanned. The file is stored in a file system with block size 1024 bytes, and the size of a block pointer is 10 bytes. If the secondary index is built on the key field of the  file, and a multi-level index scheme is used to store the secondary index, the  number  of  first-level  and second-level  blocks  in  the  multi-level  index  are respectively

  1. 8 and 0
  2. 128 and 6
  3. 256 and 4
  4. 512 and 5
asked in Databases by (133 points) | 3k views

could you please help me in this?

is it 10 ?

4 Answers

+36 votes
Best answer

Content of an index will be <key, block pointer> and so will have size 6 + 10 = 16.

In the first level, there will be an entry for each record of the file. So,total size of first-level index

= 16384 * 16

No. of blocks in the first-level = Size of first-level index / block size
= 16384 * 16 / 1024 
= 16 * 16 = 256

In the second-level there will be an entry for each block in the first level. So, total number of entries = 256 and total size of second-level index

= No. of entries * size of an entry
= 256 * 16

No. of blocks in second-level index = Size of second-level index / block size
= 256 * 16 / 1024

= 4
 

answered by Veteran (14.6k points)
selected by

please explain the meaning of the infos  given :

file is ordered by non key attribute ?

organisation is unspanned ?

 secondary index is built on the key field of the  file ?

multi-level index scheme is used to store the secondary index ?

Disk-block size might not be an exact multiple of record size. If we store the boundary record across two disk-block, the organization is called spanned. If no record is allowed to cross boundary, the organization is called unspanned.
secondary index is an index built on any key other than the primary key.

http://docs.oracle.com/cd/E17276_01/html/programmer_reference/am_second.html
"File is ordered on a non-key field " that is why the index became secondary index.

http://web.cs.ucdavis.edu/~green/courses/ecs165a-w11/7-indexes.pdf
Can you explain or refer any source to find the difference between Primary, Clustering, Secondary on key and Secondary on non-key indeces? Thanks.
An index is built by default on primary keys. Hence secondary index is built on non primary keys, since an index already exists for primary keys.
Here they have mentioned that each record is of size 32 Byte, so total size of file = 16384 *32

and total no of blocks needed are 16384*32/1024 = 16*32.

Now to store 16*32 blocks into index, we need 16*32 / 16 = 8 index block in first level index.

This is what i got. Please let me know if this is correct or not.

In your answer, you havent used "Record size of 32 B" anywhere.
Sir i think options are confusing beacuse second level blocks are 256 not 4(according to optins) and first level blocks 4. Correct me if i m wrong
study navathe all is there

@Arjun Sir,  to solve this question and this https://gateoverflow.in/2311/gate1993_14, approach is same?

As it is secondary indexing so dense index is there so no. of records in db file is same as in 1st level index so with key and record pointer calculate the block factor and then calculate the total no. of blocks in first level index same as for second level index .

Here they have mentioned that each record is of size 32 Byte, so total size of file = 16384 *32

and total no of blocks needed are 16384*32/1024 = 16*32.

Now to store 16*32 blocks into index, we need 16*32 / 16 = 8 index block in first level index.

This is what i got. Please let me know if this is correct or not.

In your answer, you havent used "Record size of 32 B" anywhere.

 

I am getting the same.

I am not getting one thing, why should the first level index entry point to every record in the file ? Shouldn't it point to the blocks containing the records in the file ? Such a thing isn't clarified in the question. It should be same like it is done in https://gateoverflow.in/2311/gate1993_14.

Is it because we are indexing on the key which does not signify the natural or original order of the file ? That is why it couldn't point to the blocks...

@pranavg189

In  https://gateoverflow.in/2311/gate1993_14 question it is ordered on the primary index of the file. In the primary indexing we don't have entry in the index table for every record, rather we will have 1 entry for each block. So no of index entries will be equal to the number of disk blocks.

In the question ordering is secondary index and so we will have index for every record.

"File is ordered on a non-key field " that is why the index became secondary index.

@Arjun sir if a file is ordered on a non-key field and the index is sorted on the same non-key field then it becomes a clustered index  and not secondary. Here they are explicitly mentioning it's a secondary index so we took secondary. Am I right sir? 

+2 votes

We need an entry for each record in the index table.

16384 records = 2^14

Now 2^14 * (10+6) B =  2^14 * 2^4 = 2^18 B

Block size is 2^10
This whole index table should fit into one block. It cant be. So number of blocks = 2^18 / 2^10 = 2^8 = 256

Now we need another index table to index these 256 index tables.
2^8 * 2^4 = 2^12B

This table also cant fit in one block. Number of blocks = 2^12 / 2^10 =2 ^2 = 4 blocks

We need another table to index these 4 blocks... that table size will be 4*16B which can easily sit in another 1024B block now.
Hence C is the answer.

answered by Boss (8.9k points)
+2 votes

Secondary Index is created on key field, which is dense index.

Since we have 16384 records in data file, index is created for every entry in 1st level index file.

In 1st level index file size of each record is 10+6 = 16B

1st level index contains 16384 records

No of records/block in 1st level index = 1024/16 = 64 records

No of blocks in 1st level index = 16384/64= 256 

Now, we have another 2nd level index which contains 256 records(1 record for each block in 1st level index) 

No of blocks in 2nd level index= 256/64= 4

Hence option c) is correct

answered by Boss (8.4k points)
–1 vote

it's very simple..

Block size is 210 bytes and if you see option C .. it's 256 and 4 which is 2and 22 

So only option C satisfies ​​​​​​​​​​​​​​​.

answered by (25 points)
is it any shortcut?


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,506 questions
39,217 answers
109,117 comments
36,599 users