The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+23 votes
3.7k 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 (113 points)
edited by | 3.7k views
+2

could you please help me in this?

0
is it 10 ?
0
How can we decide whether level is from left hand side or rhs as in OS in multilevel paging first level means 0th level?

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 Boss (18k points)
edited by
0

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 ?

+8
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.
+1
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
+2
"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
0
Can you explain or refer any source to find the difference between Primary, Clustering, Secondary on key and Secondary on non-key indeces? Thanks.
0
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.
+1
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.
0
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
0
study navathe all is there
0
0

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

+2
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 .
0

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...

0

@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.

0
"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? 

0
I have one doubt, why are you using block pointer to refer to every record in first level. Instead record pointer is used for this purpose. But since record pointer is not mentioned here , can we simply use block pointer in its place.
+5 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 (11.4k points)
+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 (10.5k points)
0 votes

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 (35 points)
+1
is it any shortcut?
0
As it is dense index, we need to use record pointer. But in the question block pointer is given ie 10B. Why are using block pointer here when we should be using record pointer?


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

36,194 questions
43,647 answers
124,088 comments
42,928 users