GATE CSE 2008 | Question: 70

Question

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

• A. $8$ and $0$
• B. $128$ and $6$
• C. $256$ and $4$
• D. $512$ and $5$

Comments

@arbpass ooh , i only knew about the simple implementation of secondary index.Thanks bro

---

@yoda very clever, representing the byte values given in question as powers of 2. makes it so easy to calculate. thanks for this technique.

---

visualization


 

Answer 1

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$

Comments

since the index is secondary index , each index entry should point a record, but as u said we did not use record size here because we have no need to calculate the number of data blocks in the file, but suppose if it was asked primary index , first we calculate number of data blocks and then we calculate number of blocks required for indexes to point each block of data(here each index points a data block, but in secondary each index points a record), so
for primary indexing
Given 16,384 records at 32 bytes each, with a block size of 1,024 bytes, each block holds 1024/32= 32 records. Thus, data blocks = 16384 /32=512. For primary indexing, each index entry is 16 bytes, so a block holds 1024/16= 64 entries. First-level index blocks = 512/64 = 8; a second-level index needs 1 block if multi-level indexing is used.

---

@Vineeth_Babu Bro here the size of the record is 16 bytes and not 32 bytes as you have mentioned. 

---

Read the question again bro

Answer 2

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

Answer 3

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

Comments

Thanks, for the clear explanation.

Answer 4

In the above example ID is a KEY and Car is a NON KEY, and as we can see that the RELATION is sorted on NON KEY Car, here the key and a very Obvious observation is that

at once the relation can be sorted with respect to any one attribute i.e, if the relation is sorted wrt to some non-key then not necessarily but obviously it won't be sorted wrt to other attributes

now why secondery indexing here ?

• first go and read the question very carefully now, the relation is sorted but on a non key which is car here but the indexing is done on the key of the relation which is ID here and that's why the file is unordered as the search key is undordered (whihc is id here)
• and whenever the file is unordered (with respect to our search key) we use secondary indexing so this is unordered + key as search key
• and as the search key is unordered we can't use sparse indexing, we can't have a block anchor here as we don't know in which block the search key lies (due to search key being unordered)

so we'll use dense indexing and in dense indexing we have 2 fields the search key and the block pointer

\[
\text{Index entry size} = \text{Key size} + \text{Block pointer size} = 6 + 10 = 16 \text{ bytes}
\]

\[
\begin{array}{|c|c|}
\hline
\textbf{Search Key (6 bytes)} & \textbf{Block Pointer (10 bytes)} \\
\hline
\end{array}
\]

so as we are using dense indexing, we'll have a index entry correspongind all 16384 records lets first find block factor for index entries

\[
\text{Block factor of index record} = \frac{\text{Block size}}{\text{Size of index record}}
= \frac{1024}{6 + 10} = 64
\]

so we can store 64 index records per disk block

so no. of index blocks we'll need to store indexes corresponding all 16384 records is

\[
\frac{16384 \,\,records}{64 \,\,index \,records/block} = 256 \text{ index blocks}
\]

now again a very important point

---

index file is always sorted

and as index file is always sorted we can apply sparse indexing on the index file for multilevel indexing, as we can apply binary search on index files for more efficiency.

so no. of blocks needed to store 256 index blocks is

\[
\frac{256\,\, records}{64\,\, records/block} = 4 \text{ blocks}
\]

256 records because, we'll have index entry for 1 record per index block for multilevel indexing

and here we have the asnwer c) 256,4

reference to : index files are always sorted page no. 661

if my answer helped consider a upvote to show appreciation !

Comments

As it was dense indexing,  shouldn't we need data/ record pointer size?

---

The question provides the block pointer size because using a block pointer is the standard and better design for this specific situation (a secondary index on a non-key field).

• If an index pointed to the exact location of a record (a record pointer), then every time a record inside a block was moved (to clean up space after a deletion, for example), the index would need to be updated. This would be very slow.

• By pointing to the block instead, the database system is free to reorganize the inside of that block as much as it wants without ever needing to change the index.

but if the question explicitly mentioned the record pointer size we would have used it instead

---

index files are always sorted, thats true

we can build a multilevel index with the fact that index files

Index File : nothing but collection of index entries which itself is just<search key, pointer(record pointer in case of unordered file or secondary index , block pointer in case of primary index,clustered index)>

but one must notice the fact that in cases like this one, where secondary index is build, we cannot proceed with just block pointer, because in the block we would not be able to search sequentially, for searching key within a leaf node,

 

 we will need to apply Search for each of the sequential key in order to arrive at its block pointer, and that too does not work as the block themselves dont contain searchkeys in a sequential order. 

---

Navanthe Reference,

therefor we are pretty much forced to use record pointer and hence the size of pointer will turn out to atleast 11 byte, thus the ans can be 272 and 5. and can be c.)256,4 depending on which implementation is used.

@coderatul  REALLY THANKS FOR THE NAVANTHE REFERENCE IT REALLY CLEARED A LOT OF THINGS

 

The lines given by Navanthe, may sound contradictory to his own statement, but this is what he means,

Answer 5

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 6

it's very simple..

Block size is 2¹⁰ bytes and if you see option C .. it's 256 and 4 which is 2⁸ and 2² 

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

Comments

is it any shortcut?

---

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?

---

Finally ,someone think , why block ptr is used in place of record ptr.

---

if block ptr or record ptr any of them is given then we have to consider it for both.