Analysis of index-sequential files with overflow chaining

ABSTRACT

The gradual performance deterioration caused by deletions from and insertions into an index-sequential file after loading is analyzed. The model developed assumes that overflow records are handled by chaining. Formulas for computing the expected number of overflow records and the expected number of additional accesses caused by the overflow records for both successful and unsuccessful searches are derived.

REFERENCES

• 1: BAYER, R., AND MCCREIGHT, E. Organization and maintenance of large ordered indexes. Acta Inf. 1 (1972), 173-183.
• 2: James A. Behymer , Robert A. Ogilive , Alan G. Merten, Analysis of indexed sequential and direct access file organizations, Proceedings of the 1974 ACM SIGFIDET (now SIGMOD) workshop on Data description, access and control, p.389-417, May 01-03, 1974, Ann Arbor, Michigan [doi>10.1145/800296.811522]
• 3: COLLMEYER, A.J., AND SHEMER, J.E. Analysis of retrieval performance for selected file organization techniques. In Proc. AFIPS 1970 Fall Jt. Computer Conf., vol. 37, AFIPS Press, Arlington, Va., pp. 201-210.
• 4: FELLER, W. An Introduction to Probability Theory and Its Applications, 2nd ed., vol. 1. Wiley, New York, 1957.
• 5: S. P. Ghosh , M. E. Senko, File Organization: On the Selection of Random Access Index Points for Sequential Files, Journal of the ACM (JACM), v.16 n.4, p.569-579, Oct. 1969 [doi>10.1145/321541.321546]
• 6: KEEHN, D.G., AND LACY, S.O. VSAM data set design parameters. IBM Syst. J. 13, 3 (1974), 186-212.
• 7: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 8: James K. Mullin, An improved index sequential access method using hashed overflow, Communications of the ACM, v.15 n.5, p.301-307, May 1972 [doi>10.1145/355602.361304]
• 9: NAKAMtJRA, T., AND MIZOGUCHI, T. An analysis of storage utilization in block split data structuring scheme. In Proc. 4th Int. Conf. Very Large Data Bases, S.B. Yao, Ed. West Berlin, Germany, 1978, pp. 489-495.
• 10: QuiTzow, K.H., AND I~LOPPROGGE, M.R. Space utilization and access path length in B-trees. Inf. Syst. 5, 1 (1980), 7-16.
• 11: RIORDAN, J. Stochastic Service Systems. Wiley, New York, 1962.
• 12: SENKO, M.E., LUM, V.Y., AND OW}~NS, P.V. A file organization evaluation model (FOREM). In Information Processing 68, A.V.H. Morrell, Ed. North-Holland, Amsterdam, 1969, pp. 514-519.
• 13: Gio C. Wiederhold, Database Design, McGraw-Hill, Inc., New York, NY, 1977
• 14: WONG, K.F., AND STRAUSS~ J.G. An analysis of ISAM performance improvement options. Manage. Datamat. 4, 3 (1975), 95-107.
• 15: YAO, A.C. On random 2-3 trees. Acta Inf. 9, 2 (1978), 159-170.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.2 Information Storage
          Subjects: File organization

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.2 Physical Design
          Subjects: Access methods

General Terms:
Algorithms, Design

Keywords:
ISAM, analysis of algorithms, analytic model, file organization, file structure, index sequential files, indexed sequential access method, overflow, overflow chaining, overflow handling, performance analysis