Relative File Organization [Data Structures]

There should be some logic for placing a particular record at particular place. Using hashing the address generated can’t be physical address. You can’t pinup the record at particular place. Hence hashing does not generate absolute address due to following reasons.

1. The absolute address has to be some track number, sector number
2. If we succeed and pinup a record at a particular place then we won’t be able to defragment the file at any later point of time.

h(key) -> rid : rid is the relative position of the record in the file. If 5 records can fit on a block then all the 5 records fitting on a particular block will have same rid. Hence h(key) -> bid. This block number is given to the OS routine, which maps bid to (track no, sector no). The OS routine will not perform any calculation instead it will search the mapping in a table. This is because, if you do calculation (i.e. you do pinning) then the block can’t be moved but table provide flexibility of changing the place if required by just updating the corresponding bid -> (track no, sector no) mapping in the table. This whole scheme is called Direct Access Mode. Relative file organization of DS fits well with this mode. Once file grows you have to shift entire file, therefore there will be a lot of hassle.

Insertion

• Block is partially empty – use the space
• Block is not empty – use another (overflow) block

Deletion of records will be with a marker (X). Records will be physically present but marked deleted.