1.1k views
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 $16$ $K$ 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?
edited | 1.1k views

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$
edited by
0
anything wrong with my approach ?
+4
No, you expanded the blocking factor while I didn't. I added this for clarity purpose.
0
detail explanation :)
+1

Why are not the entries equal to the number of records at first level of the index?

+2
@arjun sir, why is sparse index assumed here? why not dense index? Nothing is mentioned about it in question. Please explain.
0
@churchill because ISAM  is built on ordered data file.
0
@Manu, That is fine but how "No. of first level index entries = No. of Data Blocks needed for data file = 2 K" is considered here. I suppose No. of first level index entries should be 16K. Please clear my doubt.
0
nice explaination. thanx
0
+3

0

In the definition of ISAM, it is mentioned that

For each primary key, an index value is generated and mapped with the record.

then why are we considering sparse indexing?

0
I think here 16K records should mean 16*1000 records because K is taken as 1024 for data size only.For number of records 1K=1000, and 1M=$10^6$. Please correct me if I am wrong.

So, only in this case, the number of index blocks at first level should be 63 instead of 64.
0
@Ayush I think the same, it afterall number of records and not size.
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
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.
+1
This approach is right and easy to understand.
0

no of block for 1st level index = no of keys *key size / block size
= 2k * (14+2)/ 512

# = 63 block:P

0
Calculation mistake.It is 64 blocks.Please, recheck.
0

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

0
I find this one better because it's easily relatable to OS multilevel paging.
0
easy & simple
–1 vote
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.
0
what we assume for indexing  sparse or dense?
+1

@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

1
2