Analysis of design alternatives for virtual memory indexes

ABSTRACT

A class of index structures for use in a virtual memory environment is described. Design alternatives within this class of index structures are analyzed. These alternatives include a choice of search strategy, whether or not pages in the index are stuctured, and whether or not keys are compressed. The average cost of retrieving entries from these indexes is expressed as a weighted sum of the cost of a basis key comparison and the cost of crossing a page boundary in the index structure. Formulas for the retrieval costs possible combinations of design alternatives are given. These are used in numerical case studies which compare the retrieval costs of the alternatives. Qualitative comparisons of the maintenance costs (insertion, deletion, reorganization) of the design alternatives are also included.

REFERENCES

• 1: Adelson-Velskii, G.M. and Landis, E.M. An information organization algorithm. Doki. Akad. Nauk SSR 2, (1962).
• 2: Bayer, R. Binary B-trees for virtual memory. Proc. 1971 ACM-SIGFIDET Workshop on Data Description, Access and Control, pp. 219-235.
• 3: Bayer, R. and McCreight, E.M. Organization and maintenance of large ordered indices. Proc. 1970 ACM SIGFIDET Workshop on Data Description and Access, pp. 107-141.
• 4: Chang, H.K. Compressed indexing method. IBM Tech. Disclosure Bull. II, No. 11, April 1969.
• 5: Clark, W.A., Davies, C.T., Salmond, K.A., and Stafford, T.S. High-Level Index Factoring System. U.S. Patent No. 3,646,524, Feb. 29, 1972.
• 6: Clark, W.A., Salmond, K.A., and Stafford, T.S. Methods and Means for Generating Compressed Keys. U. S. Patent No. 3,593,309, Jan. 2, 1969.
• 7: Peter J. Denning, Virtual Memory, ACM Computing Surveys (CSUR), v.2 n.3, p.153-189, Sept. 1970 [doi>10.1145/356571.356573]
• 8: C. C. Foster, Information retrieval: information storage and retrieval using AVL trees, Proceedings of the 1965 20th national conference, p.192-205, August 24-26, 1965, Cleveland, Ohio, United States [doi>10.1145/800197.806043]
• 9: 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
• 10: Maruyama, K. and Smith, S.E. Analysis of design alternatives for virtual memory indexes. Rep. No. RC5087, IBM Res. Center, Yorktown Heights, N.Y., Oct. 1974.
• 11: Maruyama, K. Index structures for virtual memory--comparison between B-trees and M-trees. Rep. No. RC5258, IBM Res. Center, Yorktown Heights, N.Y., Feb. 1975.
• 12: Wagner, R.E. Indexing design considerations. IBM Systems J. 12, 4 (1973), 351-367.
• 13: S. R. Arora , W. T. Dent, Randomized binary search technique, Communications of the ACM, v.12 n.2, p.77-80, Feb. 1969 [doi>10.1145/362848.362856]
• 14: Wong, C.K., and Yue, P.C. Free-Space Utilization of a Disk File Organization Method. Proc. 7th Annual Princeton Conf. on Information Sci. and Systems, March 1973; also Rep. No. RC 3712, IBM Res. Center, Yorktown Heights, N.Y., Feb. 1972.
• 15: IBM System/360 Operating System Indexed Sequential Access Method. Order No. Y28-6618, IBM, White Plains, N.Y.
• 16: Introduction to Virtual Storage in System/370. Order No. Gr20-4260-1, IBM Corp., Poughkeepsie, New York.
• 17: Introduction to IBM Direct-Access Storage Devices and Organization Methods. Order No. GC20-1649-6, IBM Corp., Poughkeepsie, New York.
• 18: OS/VS Virtual Storage Access Method (VSAM) Planning Guide. Order No. GC26-3799, IBM Corp., White Plains, N.Y.

INDEX TERMS

Keywords:
files, index, index structure, key compression, maintenance, pages, retrieval, search strategy, virtual memory