Marking Scheme:
Sample Solutions for B+ Tree Calculations
a) 1 mark – deduct 0.5 if they used the ceiling instead of the floor, or wrote their answer with decimal places (like 227.56) instead of an integer
b) 1.5 marks for computing the number of leaf pages (deduct 0.5 if they didn’t take the ceiling, but just deduct this once for part (b))
1 mark for the correct number of level‐1 pages 0.5 marks for the rest
Deduct 1 mark if they did not show any work and just wrote down the answers. We asked them to show brief work.
Version 1: 2 attributes in a composite search key
a) floor( 4,096 (bytes/index page) / (4 + 4 + 10) bytes/DE ) = 227 DE/leaf page
b) ceiling( 750,000 data entries / 227 (DE/leaf page) ) = 3,304 leaf pages
ceiling( 3,304 leaf pages / (227 + 1) (leaf pages / parent page ) ) = 15 level‐1 pages ceiling( 15 level‐1 pages / (227 + 1) (level‐1 pages / parent page ) ) = 1 root page (This means the B+ tree index has 3 levels.)
Version 2: 3 attributes in a composite search key
a) floor( 4,096 (bytes/index page) / (4 + 4 + 4 + 10) bytes/DE ) = 186 DE/leaf page
b) ceiling( 700,000 data entries / 186 (DE/leaf page) ) = 3,764 leaf pages
ceiling( 3,764 leaf pages / (186 + 1) (leaf pages / parent page ) ) = 21 level‐1 pages ceiling( 21 level‐1 pages / (186 + 1) (level‐1 pages / parent page ) ) = 1 root page (This means the B+ tree index has 3 levels.)
Version 3: 4 attributes in a composite search key
a) floor( 4,096 (bytes/index page) / (4 + 4 + 4 + 2 + 10) bytes/DE ) = 170 DE/leaf page
1
b) ceiling( 550,000 data entries / 170 (DE/leaf page) ) = 3,236 leaf pages
ceiling( 3,236 leaf pages / (170 + 1) (leaf pages / parent page ) ) = 19 level‐1 pages ceiling( 19 level‐1 pages / (170 + 1) (level‐1 pages / parent page ) ) = 1 root page (This means the B+ tree index has 3 levels.)
2