This topic discusses different types of indexing techniques that allows the location of records in a file relatively fast with fewer accesses. The techniques that will be addressed deals with random access file organization only. As this is the best file organization that allows records to be stored randomly rather than sequentially or in a contiguous manner. By using direct addressing, a predictable relationship between a key of a record and the location of that record on an external file is established.Two different forms of addressing can be used to establish this relationship: 1.Absolute Addressing 2.Relative Addressing Absolute addressing make use of the storage devices to determine the relationship, and therefore it is machine dependent, e.g., cylinder-number, surface-number, and record-number if we are using cylinder addressing or sector-number and record-number if sector addressing is being used.HashingHashing is the application of a function to the key value of a record that results in mapping the range of possible key values into a smaller range of relative addresses. For example, if a company is to maintain data of 10,000 employees by using the employee’s social security number, which ranges from 1 to 999999999, into 10,000 relative positions. The hash function to be applied to the social security number must be able to match each 10,000 social security number into each relative address available. However, collisions do occur. Collisions occurs when two different keys, in this case two social security numbers, hash into the same relative address. These two different keys aretermed synonyms.The relationship between the file space and the number of keys is described as the load factor. Load factor is the ratio of the number of key values to be stored versus the number of file positions:Load Factor = number of key values / number of file positionsPrime-Number Division RemainderPrime number division remainder method...
