95 views

https://gateoverflow.in/147564/test-by-bikram-2017-database-systems-test-2-26

Assume that a data file contains 2000 records that are ordered by a key attribute K , and a primary index on attribute K is built.

The size of key is 5B and block pointer is 5B. Each block of the system is of size 105B, out of which 100B can be used to store data (and 5B is reserved for storing meta data).

The total number of disk accesses required to fetch the record using the index (in average case) is  _____.

initial number of blocks in database file = 100,

So $1^{st}$ level of index file contains 100 records which will be divided into 10 blocks

Now $2^{nd}$ level of index file contains 10 records which will be divided into 1 block

Last level will contain only 1 record

So total number of access = 1(access for record in database file) + 3(accesses in indexes)

| 95 views
0
U mean $\log10$ not required?
0
Yes, it should not be used. But if it has been used than we get 3.219 when $log_210$ is considered

so the answer has been considered as $\textbf{\{ceil(3.219) + 1\} ={4+1 = 5}}$
0
but whatever u r telling, is it for multilevel indexing or primary indexing?
0
primary indexing, but there can be multiple levels of indexes just like a normal b-tree
0

@!KARAN

Such indexing not exists. Actually whatever u r doing is multilevel index using primary indexing. See this u could understand https://gateoverflow.in/259/gate2008-70 Same thing with secondary indexing.

Here question asking "for total number of disk accesses". right?? not number of blocks in 1st or 2nd level. ok??

Number of record in data file $=2000$

Block size $105B$

Blocking factor$=\left \lfloor \frac{105}{10} \right \rfloor=10$

Number of blocks in 1st level index$=\left \lceil \frac{2000}{10} \right \rceil=200$

Number of blocks in 2nd level index$=\left \lceil \frac{200}{10} \right \rceil=20$

Number of blocks in 3rd level index$=\left \lceil \frac{20}{10} \right \rceil=2$

Number of blocks in 4th level index$=\left \lceil \frac{2}{10} \right \rceil=1$

So, total block access=index block access+data block access=$=4+1=5$

Hope ur doubt clear now
by (817 points)
selected by