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.