The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+17 votes
968 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?
asked in Databases by Veteran (59.6k points)
edited by | 968 views

3 Answers

+32 votes
Best answer
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$
answered by Boss (34k points)
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
@arjun sir, why is sparse index assumed here? why not dense index? Nothing is mentioned about it in question. Please help.
+3

@shraddha fyi.

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?

please clarify 

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.
+16 votes
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.
answered by Veteran (55.4k points)
+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.
answered by (391 points)
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

Related questions



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

41,064 questions
47,662 answers
147,334 comments
62,381 users