An indirect chaining method for addressing on secondary keys

ABSTRACT

Methods for entering random-access files on the basis of one key are briefly surveyed. The widely used chaining method, based on a pseudo-random key transformation, is reviewed in more detail. An efficient generalization of the chaining method which permits recovery on additional keys is then presented.

REFERENCES

• 1: IVERSON, K. E. AND BROOKS, F. P., JR. Automatic Data Processing. John Wiley & Sons (in preparation).
• 2: A. Newell , J. C. Shaw, Programming the logic theory machine, Papers presented at the February 26-28, 1957, western joint computer conference: Techniques for reliability, p.230-240, February 26-28, 1957, Los Angeles, California [doi>10.1145/1455567.1455606]
• 3: PETERSON, W. W. Addressing for random-access storage. IBM J. Res. Dev. 1, No. 2 (Apr. 1957), 130-146.
• 4: FELLER, W. An Introduction to Probability Theory and its A pplications, Vol. I. John Wiley & Sons, New York, 1950.
• 5: HEISING, W. P. Some mathematical notes on random addressing. IBM internal memorandum, Nov. 1957.
• 6: The chaining method of disk storage addressing for the IBM RAMAC 305. IBM Form No. J28-2008-1, 1958 and 1960; also: The chaining method for the 650 RAMAC System, IBM Form No. J28-4002, 1958. These curves are also reproduced in C. C. Gotlieb, General-purpose programming for business applications, Advances in Computers, Vol. 1, (Editor, Franz L. Alt), Academic Press, 1960, but without sufficient mention of the assumptions on which the curves are based.
• 7: MOLINA, E. C. Poisson's Exponential Binomial Limit. D. Van Nostrand Co., New York, 1942.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS

General Terms:
Performance