Copyright © 1998 T. H. Merrett 308-420A Secondary Storage Algorithms and Data Structures Week 6 Multipage Search and Insert (Algorithm MSI) Various algorithms can be assembled from the following criteria. (Note typing conventions for the symbols pi, alpha, subscript ni and Vi.) Split Criteria 1. (pi) If pi > pi0 then split 2. (alpha) Split unless alpha < alpha0 Direction criteria 3. (Shape) Increase ni for the axis, i, for which Vi/ni is largest (in order to equalize all Vi/ni, as far as possible). 4. (pi) Split in the direction so that pi is minimized. 5. (alpha) Increase ni for the axis, i, for which ni is largest (to create least number, n/ni, of new pages and so decrease alpha the least). Shift criteria 6. (pi) If pi > pi0 and shifting a boundary will make pi <= pi0, shift in the direction so that pi is minimized. Algorithms Try to shift first: A. 6, 1, 3, 4, 5 emphasizes pi B. 6, 1, 3, 5, 4 pi, then alpha C. 6, 2, 3, 5, 4 split emphasizes alpha D. 6, 2, 3, 4, 5 split using alpha, then pi No shift: A', B', C', D' like their counterparts, but without 6 Note that shape and alpha criteria are easy to calculate. The pi criteria must be tested by doing or simulating the shifts or splits, and so are much more expensive. However, they deal directly with what is usually the important consideration, namely keeping the probe factor down.