Sample Solutions for Question 8: B+ Tree Page Fault Calculations
Version 1: 3 children of the root, 50,000 sailors, and 20 to look up
a) (2 marks) Either of these solutions is fine:
a. 1+3+20+20=44pagefaults
Note: If a student assumed (implicitly or being saying so) that the SailorID was the name, then it would be exactly 1 + 3 + 20 = 24 page faults. We’ll accept it as correct. However, in this case BOTH parts (a) and (b) must assume that the SailorID is the name.
b. Maybe the student thought we couldn’t use the index. That’s fine. Then they would skip the index altogether and simply read the whole table: 50,000 records / 80 records/page = 625 pages; so, 625 page faults (you can give 1 mark if they added some index pages to this—but they really don’t need to check the index in this case)
b) (1 mark) Minimum = 1 + 1 + 1 + 1 (to fetch the records from the data table) = 4 page faults.
Note: If a student assumed that Sailor ID was the name, then it would be 3 page
faults. We’ll accept it as correct. However, in this case BOTH parts (a) and (b) must assume that the SailorID is the name.
a) (2 marks) Either of these solutions is fine: a. 30+30=60pagefaults
i. Note: If a student assumed (implicitly or being saying so) that the SailorID was the name, then it would be exactly 30 page faults. We’ll accept it as correct. However, in this case BOTH parts (a) and (b) must assume that the SailorID is the name.
b. Maybe the student thought we couldn’t use the index. That’s fine. Then they would skip the index altogether and simply read the whole table: 50,000 records / 80 records/page = 625 pages; so, 625 page faults (you can give 1 mark if they added some index pages to this—but they really don’t need to check the index in this case)
b) (1 mark) In the best case, they can use the index. The first 2 levels are already in the buffer pool; therefore, the minimum = 1 + 1 (to fetch the records from the data table) = 2 page faults. i. Note: If a student assumed (implicitly or being saying so) that the SailorID was
the name, then it would be exactly 1 page fault. We’ll accept it as correct. However, in this case BOTH parts (a) and (b) must assume that the SailorID is the name.
Version 3: 12 children of the root, 120,000 sailors, 10 to look up, 4‐level index
a) (2 marks) Either of these solutions is fine:
a. 1+10(max.level‐1)+10+10+10=41pagefaults
i. Note: If a student assumed (implicitly or being saying so) that the SailorID was the name, then it would be exactly 1 + 10 + 10 + 10 = 31 page faults. We’ll
Version 2: 3 children of the root, 50,000 sailors, 30 to look up; but, the root and level‐1 pages are
already in the buffer pool
1
accept it as correct. However, in this case BOTH parts (a) and (b) must assume
that the SailorID is the name.
b. Maybe the student thought we couldn’t use the index. That’s fine. Then they would
skip the index altogether and simply read the whole table: 120,000 records / 80 records/page = 1,500 pages; so, 1,500 page faults (you can give 1 mark if they added some index pages—but they really don’t need to check the index in this case)
b) (1mark) Inthebestcase,theycanusetheindex. Therefore,theminimum=1+1+1+1+1(to fetch the records from the data table) = 5 page faults.
i. Note: If a student assumed (implicitly or being saying so) that the SailorID was thename,thenitwouldbeexactly1+1+1+1=4pagefaults. We’llacceptit as correct. However, in this case BOTH parts (a) and (b) must assume that the SailorID is the name. For example, 41 page faults for (a) and only 4 for (b) would be inconsistent. Similarly, 31 page faults for (a) and 5 for (b) would be inconsistent.
2