TAOCP 5.4.9 Exercise 2
Working
Section 5.4.9: Disks and Drums
Exercise 2. [M30] [M30] (A. G. Konheim.) The purpose of this problem is to investigate how far the access arm of a disk must move while merging files that are allocated “orthogonally” to the cylinders. Suppose there are P files, each containing L blocks of records, and assume that the first block of each file appears on cylinder 1, the second on cylinder 2, etc. The relative order of the last keys in each block governs the access arm motion during the merge, hence we may represent the situation in the following mathematically tractable way: Consider a set of PL ordered pairs
(a11, 1) (a21, 1) wee (api, 1) (a12, 2) (a22, 2) wae (apo, 2) (aiz,L) (a2z,L) ... (apr,L)
where the set {ai; | 1 » 4. [M21] Consider a modified form of the square root buffer allocation scheme, in which all P of the input buffers have equal length, but the output buffer size should be chosen so as to minimize seek time. a) Derive a formula corresponding to (2), for the running time of an L-character P-way merge. b) Show that the construction in Theorem K can be modified in order to obtain a merge pattern that is optimal according to your formula from part (a).
5.4.9 DISKS AND DRUMS 377
Verified: no
Solve time: 4m43s
Working