Algorithmic Studies in Mass Storage Systems

A major technological trend for large database systems has been the introduction of ever-larger mass storage systems. This allows computing centers and business data processing installations to maintain on line their program libraries, less frequently used data files, transaction logs and backup copies under unified system control. Tapes, disks and drums are classical examples of mass storage media. The more recent IBM 3851 Mass Storage Facility, part of the IBM 3850 Mass Storage System, represents a new direction in mass storage development, namely, it is two-dimensional. With the maturity of magnetic bubble technology, more sophisticated, massive, multi-trillion-bit storage systems are not far in the future. While large in capacity, mass storage systems have in general relatively long access times. Since record access probabilities are usually not uniform, various algorithms have been devised to position the records to decrease the average access time. The first two chapters of this book are devoted mainly to such algorithmic studies in linear and two-dimensional mass storage systems. In the third chapter, we view the bubble memory as more than a storage medium. In fact, we discuss different structures where routine operations, such as data rearrangement, sorting, searching, etc., can be done in the memory itself, freeing the CPU for more complicated tasks. The problems discussed in this book are combinatorial in nature.

1. Linear Storage.- 1.1. Introduction.- 1.2. Record arrangement to minimize head travel.- 1.3. Record partition and page arrangement to minimize head travel.- 1.4. Dynamic allocation of records to minimize head travel.- 1.5. Record arrangement to minimize head travel (unequal record size).- 1.6. Schedules to minimize head travel in a batched processing environment.- 1.7. Appendix.- 1.8. References.- 2. Two-Dimensional Storage.- 2.1. Introduction and basic model.- 2.2. Record arrangement to minimize head travel.- 2.3. Record arrangement to minimize head travel in bounded arrays.- 2.4. Head scheduling in a batched processing environment.- 2.5. Permutation of records using minimum head movement.- 2.6. Appendix.- 2.7. References.- 3. Magnetic Bubble Memory.- 3.1. Introduction and basic models.- 3.2. Optimal permutation algorithm in a simple model of bubble memory.- 3.3. Up-down bubble sorter.- 3.4. Tree searching in a major/minor loop bubble memory.- 3.5. Permutation algorithms in different models of bubble memories.- 3.6. Sorting algorithms in different models of bubble memories.- 3.7. Searching algorithms in different models of bubble memories.- 3.8. Appendix.- 3.9. References.