Indexes Calculate the number of disk accesses required in the worst case for dif
ID: 647097 • Letter: I
Question
Indexes
Calculate the number of disk accesses required in the worst case for different index organizations. Lets assume that the database keeps track of our current class and we store four attributes regarding students:
Name 50 bytes
ID_Num 10 bytes Primary Key
Address 60 bytes
Grade 10 bytes
There are 3,000 students in our CS622B table. Each data block can store 1000 bytes of information. A block pointer requires 12 bytes. The file is sorted (clustered) on the primary key. The student name is the secondary key.
How many disk accesses are required if:
Access is through ID_Num and there is no index.
Access is through ID_Num and there is a primary index on student name (Similar to index some in appendix figure B). Lets also assume that the ENTIRE index is already in RAM.
Access is through ID_Num and there is a primary index on ID_Num (Similar to index in appendix figure B). Lets also assume that the ENTIRE index has to be kept on disk.
Access is through ID_Num and there is a 2-level primary index on student name (Similar to index in appendix figure C) in which the second level of the index is in RAM while the first level of the index is on DISK. Please note the difference from this and the figure C.
Explanation / Answer
This solution is based on the information provided above (as figure B, Figure C mentioned in question are not provided).
The size of a student record=50+10+60+10=130 Bytes.
Total number of students = 3000.
So total size of Space required for Tables= 3000*130 =390000 Bytes.
Data block size=1000 Bytes.
So, number of Data Blocks required= 390000/1000 =390 Data Blocks.
Index: (a). Based on Student Name
size of index= number of students * (size of Name + Size of Block Pointer) =3000*(50+12)=186000
Number of Data Blocks Required =size of index/size of data blocks=186000/1000=186 Data blocks.
(b). Index Based on ID_Num
size of index=size of index = number of students * (size of ID_Num + Size of Block Pointer)
= 3000*(10+12) = 66000 Bytes,
Number of Data Blocks Required= 66000/1000=66 Data Blocks.
Ans(i). Access is through ID_Num and there is no index.
In this we have to access all Data Blocks (containing students record) in worst case as we don’t know the record we want access is residing in which Data Block.
So number of Disk Access in worst case= Total number of Data Blocks(containing students record) = 390.
Ans.(ii). Access is through ID_Num and there is a primary index on student name. Let’s also assume that the ENTIRE index is already in RAM.
As we want to access student record using ID_Num but the Index we have is primary index on student name. So as we can not predict which ID_Num belongs to which Student Name. So we can not use the primary index on student name to access record using ID_Num.
So here also,
the number of Disk Access required= Total number of Data Blocks(containing students record) =390.
Ans.(iii). Access is through ID_Num and there is a primary index on ID_Num. Lets also assume that the ENTIRE index has to be kept on disk.
So, here we can use primary index on ID_Num. In this case we have to access all primary index data blocks in worst case. And when we found the ID_Num in a Index Data Block then we need to access only Data Block (containing students record).
So, The Number of Disk Accesses required = Number of Index Data Blocks + One Data Block (containing students record) = 66+1 = 67.
Ans.(iv). Access is through ID_Num and there is a 2-level primary index on student name in which the second level of the index is in RAM while the first level of the index is on DISK.
As we want to access student record using ID_Num but the Index we have is primary index on student name. So as we can not predict which ID_Num belongs to which Student Name. So we can not use the primary index on student name to access record using ID_Num.
So, the number of Disk Access required= Total number of Data Blocks(containing students record) =390.