GATE CSE 1993 | Question: 14

Question

An $\text{ISAM}$ (indexed sequential) file consists of records of size $64$ bytes each, including key field of size $14$ bytes. An address of a disk block takes $2$ bytes. If the disk block size is $512$ bytes and there are $16K$ records, compute the size of the data and index areas in terms of number blocks. How many levels of $\text{tree}$ do you have for the index?

Comments

took me a while to catch that "address of a disk block" is basically the "record pointer" .
thus size of index entry = record pointer + key size = 2 + 14 = 16 B.
after that simple solution

Answer 1

Answer: $3$

Size of each index entry = $14$ + $2$ = $16$ $B$

Blocking factor of record file = $\frac{\text{Block size}}{\text{Record size}}$ = $512$ B/$64$ B = $8$

Blocking factor of index file = $\frac{\text{Block size}}{\text{Index entry size}}$ = $512$ B/$16$ B = $32$

No. of Blocks needed for data file = $\frac{\text{No. of Records}}{\text{Blocking factor of record file}}$ = $16$ K/$8$ = $2$ K

No. of first level index entries = No. of Data Blocks needed for data file = $2$ K

No. of first level index blocks = $\lceil \frac {\text{No. of first level index entries}}{\text{Blocking factor of index file}} \rceil$ = $\lceil \frac{2 K}{32} \rceil$  = $64$

No. of second level index entries = No. of first level index blocks = $64$

No. of second level index blocks = $\lceil \frac {\text{No. of second level index entries}}{\text{Blocking factor of index file}}\rceil$ = $\lceil \frac{64}{32} \rceil$ = $2$

No. of third level index entries = No. of second level index blocks = $2$

No. of third level index blocks = $\lceil \frac {\text{No. of third level index entries}}{\text{Blocking factor of index file}} \rceil$ = $\lceil \frac{2}{32} \rceil$ = $1$

Comments

@harshitraj12 k here doesn't mean 1024 bytes simply put 16000 records are divided by 8 which tells blocking factor of the data file (records/block in data file) 64 was taken for ease of calculation.

---

@Rajarshi Sarkar
SUPER! 

---

Here $16K$ records $= 16000$ records
Total size of data file $= 2000$ blocks
Total size of index $= 63 + 2+ 1 = 66$ blocks

Answer 2

record size = 64B
no of records = 16k
total size of records = 64*16k
no of block to store records = 64*16k/512 = 2k

key size = 14B
Address size = 2B
no of block for 1st level index = no of keys *key size / block size
                                                      = 2k * (14+2)/ 512
                                                      = 64 block
no block for second level index = 64*16/512
                                                         = 2
no ofof block for 3rd level index = 2*16/512
                                                          = 1 block

total 3 level indexing.

Comments

Ohh! My Mistake, I was taken 2K as 2000, but it is 2¹¹

---

I find this one better because it's easily relatable to OS multilevel paging.

---

easy & simple

Answer 3

NO. of blocks = (16K * 64)/512 = 2K

key size = 14 bytes, pointer size = 2 bytes

no. of record in 1 index block = 512/16  = 32.

so. no of block at 1 st index = 2k/32 = 64.

no. of block at second level index = 64/32 = 2

no. of block at 3rd level index = 1.

Comments

what we assume for indexing  sparse or dense?

---

@set20a8 your question is valid, i too have the same doubt, what if it was multilevel secondary indexig?

https://gateoverflow.in/162912/database-multilevel-indexing

---

• ISAM means multilevel primary/clustering indexing + Sequential file ordered by key ( it was used in early IBM systems)
   
• By default we take primary indexing.
   
• Means at every level there would be primary indexing.
   
• Also wkt in Primary index 1st level is primary indexed rest all levels are sparse implementation. 

Answer 4

Given:

• Record size = 64 bytes
• Key size = 14 bytes
• Block size = 512 bytes
• Address size = 2 bytes
• Number of records = 16K = 16 × 1024 = 16384

1. Data Area

Records per block:

⌊512 / 64⌋ = 8

Therefore,

Data blocks = 16384 / 8 = 2048 blocks

2. Index Area

Each index entry contains:

Key + Address = 14 + 2 = 16 bytes

Index entries per block:

512 / 16 = 32

Level 1:

⌈2048 / 32⌉ = 64 blocks

Level 2:

⌈64 / 32⌉ = 2 blocks

Level 3:

⌈2 / 32⌉ = 1 block

Level-wise Summary

Data area = 2048 blocks

Index Level 1 = 64 blocks

Index Level 2 = 2 blocks

Index Level 3 = 1 block

Total index blocks = 64 + 2 + 1 = 67 blocks

Therefore:

Data area = 2048 blocks

Index area = 67 blocks

Number of index levels = 3