Exercise 1: Cost of n-Way Merge Sort
How many reads+writes to sort the following:
- r = 1048576 tuples (220)
- R = 62 bytes per tuple (fixed-size)
- B = 4096 bytes per page
- H = 96 bytes of header data per page
- D = 1 presence bit per tuple in page directory
- all pages are full
Consider for the cases:
- 9 total buffers, 8 input buffers, 1 output buffer
- 33 total buffers, 32 input buffers, 1 output buffer
- 257 total buffers, 256 input buffers, 1 output buffer
|
![[prev]](icon/prev.gif){kind=icon}
![[next]](icon/next.gif){kind=icon}