File Organisation and Access Methods
FILE ORGANISATION
Serial File Organisation Method
● Records are stored in the file in the same order as they are added.
● Any new record is stored at the end of the file.
Sequential File Organisation Method
● Records (in the file) are ordered
● …based on the key field
● A new version (of the file) has to be created to update the file
Random File Organisation Method
● Records are stored in no particular order within the file // There is no sequencing in the
placement of the records
● There is a relationship between the key (field) of the record and the record’s location
within the file // a hashing algorithm is used to find the location of the record
● Updates to the file can be carried out directly.
Real-life use of Serial File Organisation
● Creating unsorted / temporary transaction files
● Creating data logging files
FILE ACCESS
Sequential Method of File Access
● Sequential access method searches for records one after the other
● … from the physical start of the file until the record is found/the end of file
How the sequential method of file access is applied to files with serial organisation
● records are stored in chronological order
● … every record needs to be checked until the record is found, or all records have been
checked.
How the sequential method of file access is applied to files with sequential organisation
● For sequential files, records are stored in order of a key field/index, and it is the key
field/index that is compared.
● … every record is checked until the record is found, or the key field of the current record
is greater than the key field of the target record.
Direct access as a method of File Access
● Direct access allows a record to be found in a file without other records being read.
● Records are found by using the key field of the target record // the location of the record
is found using a hashing algorithm
How direct access is used to locate a specific record in sequential files
● An index of all key fields is kept
● The index is searched for the address of the file location where the target record is
stored.
How direct access is used to locate a specific record in random files
● A hashing algorithm is used on the key field of the record
● … to calculate the address of the memory location where the target record is expected to
be stored.
● Method to find a record if it is not at the expected location e.g. linear probing, search
overflow area etc.
HASHING ALGORITHM AND COLLISION
Hashing Algorithm
● A hashing algorithm is used in direct access methods on random and sequential files
● It is a mathematical formula
● … used to perform a calculation applied to the key field of the record being searched /
stored
● The result of the calculation gives the address where the record should be found /
stored.
Collision
● A collision is when the two values / data items in the key field for two records (pass
through a hashing algorithm and) result in the same hash value
● …so the location identified (by the hashing algorithm) may already be in use // two
records cannot occupy the same address.
Methods for Overcoming Collisions
There are 3 methods that can be used for overcoming collisions:
1. The record is stored in the next free memory space after the one identified by the
hashing algorithm // Use linear progression
2. An overflow area is set up and the record is stored in the next free memory space in the
overflow area.
3. Each storage space holds a reference to a collection / chain of items which can be
searched individually. The data item is stored in the first available space in this chain
What happens if a collision occurs during retrieval of a record in a file using random file
organisation?
● search the overflow area linearly (open hash) until the matching record key is found
● or search linearly from where you are (closed hash) until the matching record key is
found
● If not found record is not in file
