edited by
23,529 views
67 votes
67 votes

Consider a file of $16384$ records. Each record is $32\;\text{bytes}$ long and its key field is of size $6\;\text{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\;\text{bytes}$, and the size of a block pointer is $10\;\text{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$
edited by

5 Answers

Best answer
91 votes
91 votes
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 \ast 16$

No. of blocks in the first-level $=$ Size of first-level index $/$ block size

$= 16384 \ast 16 / 1024$

$= 16 \ast 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 $\ast$ size of an entry

$= 256 \ast 16$

No. of blocks in second-level index $=$ Size of second-level index $/$ block size

$= 256 \ast 16 / 1024$

$= 4$

Correct Answer: $C$
edited by
27 votes
27 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

7 votes
7 votes

No. of records = 16384, record size = 32 B

Key Field size = 6 B, Block Size = 1024 B, Block Pointer Size = 10 B

Secondary Indexing: Index is created for each record in the file (dense indexing).

No. of index entries per block = $\frac{Block\_Size}{keySize+Block Address Size}=\frac{1024}{6+10}=64$

First level index entries = $\frac{No\_of\_records}{Blocking\_factor\_for\_indexing}=\frac{16384}{64}=256$

Second level index entries = $\frac{First\_level\_entries}{Blocking\_factor\_for\_indexing}=\frac{256}{64}=4$

Hence, Answer is (C).

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

Answer:

Related questions

33 votes
33 votes
4 answers
1
Kathleen asked Sep 11, 2014
13,856 views
A clustering index is defined on the fields which are of typenon-key and orderingnon-key and non-orderingkey and orderingkey and non-ordering