#Test series

Question

Let R(A, B, C, D, E) be a relation which has 500000 records. Size of each record is 200 B. Size of attribute A is 16 B. Size of pointer is 4 B and size of the block is 2400 B (assume elements are stored in sorted order of key).
On the execution of the query,
                                            Select ∗ from R where A = ‘GATE’
The difference of the cost in term of number of block transfer from the disk when multilevel index used and when binary search applied without indexing is _______.

Comments

4 and  16

---

  cost in term of number of block transfer from the disk

bro what is the meaning of this line? 

---

it means when we have to transfer a block from disk than how many access will be done as it has used multi level indexing so cost is (K+1) k----> number of levels

---

if you are saying number of levels +1 then there are 4 levels, It becomes 5 but answer is given 4

---

I am getting 3levels with index factor =120

---

got it....3 levels.....then why to add +1??

---

its because once u reach the main table we can easily find values in O(1) time complexity as size of block is a constant value. so +1 for accesing it from main table.

---

how did you do, can you explain it ?

---

Size of each record=200B

Total number of records=500000

Size of block=2400B

Number of records in a block=floor(2400/200)= 12

Total number of blocks required to hold 500000 record= ceil(500000/12)=41667

Now when we use binary search= ceil(log 41667)=16   //Here base of log is 2 as you know it is binary search

Now in case of multilevel indexing, First level index is dense

size of index record= 20B

Number of index records present in each block= floor(2400/20)= 120

number of index blocks present at first level=ceil(500000/120)= 417

now index from 2nd level should be sparse

number of index blocks present at 2nd level=ceil(417/120)=4

number of index blocks present at 3rd level=ceil(4/120) = 1

cost in term of number of block transfer from the disk in multilevel index= 3+1=4

Question is asking the difference b/w the two so, 16-4= 12

---

ya thnx