A file organization method using multiple keys
Michael L. O'Connell · 1971
The nature of mass storage hardware is such that each data record stored in a given file is given a unique identifier. That identifier, or key, may be the physical address of the record, either absolute or relative to some fixed point, or it may be a key which is made up of some combination of the record's characteristics, such as the contents of a specific field within the record. Thus, in a personnel file, the record of "John Smith" may be given the key of "19" (if it is the nineteenth record in the file), or "01230402" (if it is on device 01, cylinder 23, track 04, the second record), or "15216" (if John Smith's employee number is 15216). Regardless of the method used to assign the key, however, all keys for records in any one file must be unique, i.e., no two records may possess the same key value. The reason for this restriction is obvious: two records cannot share the same physical address because two records cannot share the same physical space, and two records sharing the same key would lead to ambiguity, i.e., a command containing the non-unique key would not be sufficient to enable the hardware to determine which of the several records containing that key was to be accessed.