File organisation and access

A file is a collection of records. Each record is a collection of fields, and every field holds a value. One field, the key field, holds a value that is unique to each record, so it can be used to identify and find the record.

There are three ways to organise the records in a file: as a serial file, a sequential file or a random file.

A serial file is a collection of records with no defined order. Records enter the file in chronological order: each new record is simply added to the end of the file. All the records have the same format so they can be input and output correctly.

A text file is an example of a serial file: characters are added one after another, in the order they are typed.

Serial files are often used to record transactions as they happen, ready for batch processing later. Records can be added quickly because they do not need to be sorted.

A sequential file stores its records in order of a key field. For the records to be sorted by key field, the key field must be unique and in order, but the values do not need to be consecutive.

A record can be found by reading the key fields one by one until you reach the one you want. Because the records are sorted, you can stop as soon as you pass the place where the key would be, and faster searches such as a binary search can be used.

A random file stores records in any available position. The location of a record is found by using a hashing algorithm on its key field.

Hashing is the process of turning the key value of a record into the address where the record is stored. A hash function works out the address by doing a simple calculation on the key, or on parts of the key.

A collision happens when the hashing algorithm gives the same address for two different keys. There are two ways to deal with it:

1. Store the record in the next free location after its home location.
2. Set up a separate overflow area and store the record in the next free space there.

Note Some books call these two methods open hashing and closed hashing, but other books use the names the other way round. In the exam, describe the method instead of only giving its name.

When a record is read using direct access, its address is calculated with the hashing algorithm and the record at that address is read. Before using it, its key field must be checked against the key you are looking for. If they do not match, the following records are read until a match is found, or the overflow area is searched.

The same hashing algorithm is used to write a record and to find it again, so a record can be read directly without searching the whole file. A good hashing algorithm is quick to calculate and spreads the records evenly, so there are few collisions.

Method 1, the remainder (MOD): divide the key by the number of storage locations and use the remainder as the address. With 7 locations, numbered 0 to 6:

Address ← Key MOD 7

Another way to deal with a collision is to put the record in a separate overflow area, which is searched in order.

Method 2, folding: split the key into equal parts, add the parts together, then take the remainder when the total is divided by the number of locations. For key 452831 and 100 locations: 45 + 28 + 31 = 104, and 104 MOD 100 = 4, so the address is 4.

The remainder method is the quickest, but keys that follow a pattern can clash. With 100 locations, Key MOD 100 only uses the last two digits, so 452831 and 993831 both go to address 31. Folding uses every part of the key (45 + 28 + 31 = 104 and 99 + 38 + 31 = 168), so these keys get different addresses (4 and 68).

There are two ways to reach a particular record in a file:

• Sequential access: each record is read, one by one, until the one you want is found. Serial and sequential files are read this way. In a sequential file you can stop once the key you have reached is greater than the one you want.
• Direct access: the program goes straight to the record. In a random file, the hashing algorithm gives the address of the record.

Direct access can also be used with a sequential file, by creating a separate index file. Each entry in the index has two fields: the key field value, and the position of that record in the main file.

Deleting and editing records. In a file that is accessed sequentially, deleting or editing a record means creating a new file: records are copied from the old file to the new one, with the change made on the way. In a direct-access file, a record can be edited or deleted in place, without making a new file.