Optimal reorganization of distributed space disk files

ABSTRACT

In most database organizations, the cost of accessing the database will increase due to structural changes caused by updates and insertions. By reorganizing the database, the access costs can be reduced. A basic problem is to establish the proper tradeoff between performance, storage costs, and reorganization costs. This paper considers the optimum points at which to reorganize a database. A disk file organization which allows for distributed free space is described. A cost function describing the excess costs due to physical disorganization is defined, and this function is minimized to obtain the optimum reorganization points. Numerical examples based on the characteristics of existing disk storage devices are given.

REFERENCES

• 1: Eisen, M., and Leibowitz, M. Replacement of randomly deteriorating equipment. Management Sci. 9 (Jan. 1973), 263-276.
• 2: Ben Shneiderman, Optimum data base reorganization points, Communications of the ACM, v.16 n.6, p.362-365, June 1973 [doi>10.1145/362248.362267]
• 3: Maruyama, K., and Smith, S.E. Optimal reorganization of disk files. Ref. No. RC 4795, IBM Research Center, 1974.
• 4: IBM Component Summary--3830 Storage Control, 3330 Disk Storage, GA26-1592-0, Order No. GN20-0360, San Jose, Calif., June 1970.
• 5: Wong, C.K., and Yue, P.C. Free-space utilization of a disk file organization method. Proc. 7th Annual Princeton Conf. on Information Science and Systems, March 1973 (also Rep. No. RC3712, IBM Research Center, 1972).
• 6: IBM OS/VS Virtual Storage Access Method (VSAM) Planning Guide. GC26-3799-2, File No. $370-30, San Jose, Calif., 1973.
• 7: IBM System/360 Operating System Data Management Services. Order No. GC26-3746, IBM, White Plains, N.Y.

INDEX TERMS

Keywords:
deterioration, disk file, free space, insertion, reorganization, retrieval