5,200 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 $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?

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$

No. of index records should be calculated as:

Index entry size = Search_key_size + record_pointer_size

No. of index records per block = $\frac{blockSize}{search\_key\_size+record\_pointer\_size}=\frac{512}{14+2}=32$

@adeebafatima1, In Index Sequential access Method (ISAM), records are stored in order of primary key. This primary key is then used to sort the records. It is efficient to use primary indexing.

For each primary key of the block also called block anchor, an index entry is created in the index record.

@Ayush... Coming to the bandwidth and other metrics..it takes 10 powers... But for computer programs size should be in powers of 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
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.

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

I find this one better because it's easily relatable to OS multilevel paging.
easy & simple
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.

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
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}