Relative File Organization :: Free Essay Writer

Relative File Organization 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. Hashing Hashing 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 are termed 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 positions Prime-Number Division Remainder Prime number division remainder method works just like using the mod operator in Pascal or the % operator in C or C++. The key to a record is divided with a prime-number and the remainder from the division is used as the relative address for that record. Digit Extraction This method analyzes the key values to determine which digit positions in the key are more evenly distributed. The more evenly distributed digit positions are assigned from right to left, and the digit values are extracted and used as the relative address. For example, for a key value 546032178, the relative address could be 8134, from left to right the first, third, fifth, and eighth digit positions has been extracted.