Incremental file reorganization schemes
Edward R. Omiecinski · SMARTech Repository (Georgia Institute of Technology) · 1985
For many files, reorganization is essential during their lifetime in order to maintain an adequate performance level for users. File reorganization can be defined as the process of changing the physical structure of the file. In this paper we are mainly concerned with changes in the placement of records of a file on pages in secondary storage. We model the problem of file reorganization in terms of a hypergraph and show that this problem is NP-hard. We present two heuristics which can be classified as incremental reorganization schemes. Both algorithms incorporate a heuristic for the traveling salesman problem. The objective of our approach is the minimization of the number of pages swapped in and out of the main memory buffer area during the reorganization process. Synthetic experiments have been performed to compare our heuristics with alternative strategies.