Suppose I have a relation Grades(student_id, assignment_id, score). I have 200 students and 20 assignments. I would grade all submissions of one assignment based on the submission order, and then insert the records. As a result, based on my insertion nature, the student_id is not sorted, but the assignment_id is. I choose heap file as my file organization. My page is quite small – it can only store 40 records, or 200 bytes in one page. The SearchKeySize is 2 bytes and PointerSize is 2 bytes. My buffer size is also small, 4 pages. If my most frequent query is to find individual students, such as select * from grades where student_id=‘3347’;
select * from grades where student_id=‘8462’;
A) What is the I/O cost (i. e., number of pages in reading and writing) for finding one student if I don’t build index for student_id? (note: student_id can appear as many as 20 times in this relation)
B) What is the I/O cost of multi-way merge sort if I sort the relation after I enter all records?
C) Suppose I decide to build B+ tree index instead of sorting. What is the smallest number of pages do you estimate the B+ tree will take?
D) What is the worst I/O cost for answering those queries with B+ tree index now?