Primary indexing

Question

Suppose that we have an ordered file of 30,000 records and these records are stored on a disk and block size is 1024 bytes files records of fixed length and unspanned of size 100 byte and suppose that we have created a primary index on key field of size 9 bytes and a block pointer of size 6 bytes then find the average number of block access required with or without index?

Comments

number of records in one block = floor(1024/100) = 10

Hence number of blocks for 30000 records = 3000.

Hence without indexing we need (log3000) = 12 

With primary indexing, it is done on each block of a file.

Hence number of records in one block while PI = floor(1024/9+6) = 68

Total index records = 3000.

Hence number of blocks required = ceil(3000/68) = 45

Hence avg number of access with indexing = log45 + 1(for goto) = 7

---

But without indexing its log(3000)=3.47 ,not 12.  Even log base 2( 3000) = 8.006

Answer 1

Block size=1024B

Record Size=100B

No of records per block= 1024/100=10.24 but we can store only 10 records at max

No of blocks required to store 30000 records=30000/10= 3000

Without Primary Index: No of block accesses= log(3000)= 12

Size of a Index record= 9+6=15B

No of index record per block= 1024/15= 68 (unspanned)

we have already calculated no of blocks needed to store all records= 3000

so total no of index records =3000

Since, 68 index records are present in 1 block.

3000 index records will be present in 3000/68= 45 blocks.

With primary index: total no of block accesses =ceil(log(45))+1=6+1=7