File organisation and access

Computer Science A2 · Data Representation. The idea in plain words, the rules to remember, the mistake to avoid and a worked example, written and checked by Mega Lecture.

Test this topic free All Computer Science A2 topics

The idea

File organisation is how the records are arranged in a file. In a serial file they are in the order they were added. In a sequential file they are in order of a key field. In a random file each record is placed at an address calculated from its record key.

File access is how a record is reached. Sequential access reads from the start, one record after another. Direct access goes straight to the record.

A hashing algorithm turns a key into an address. It is used to write a record to a random file and again, with the same key, to find it. Two keys can give the same address, which is a collision.

Rules to remember

Serial: new records are added at the end; good for logs and transaction files that are read once, start to end.
Sequential: records in key order; good for batch jobs that process every record, such as payroll. Adding a record usually means writing a new file to keep the order.
Random: address = hash of the key; good when any one record is needed at once, such as a booking system.
Access: serial and sequential files use sequential access; sequential files (with an index) and random files allow direct access.
A common hash: address = key MOD number of record positions, which gives addresses from 0 to (number of positions − 1).
Collision: two different keys hash to the same address. One fix is to use the next free position; another is an overflow area.
A good hashing algorithm spreads keys evenly, so there are few collisions. A random file may have unused positions, so it can take more space.

Common mistake

Students mix up serial and sequential. Serial means no order except the order of arrival; sequential means sorted by a key field. A search of a sequential file can stop as soon as a larger key is read, but a serial file must be read to the end.

Worked example

A random file has 13 record positions numbered 0 to 12. The hash function is Key MOD 13 and a collision is resolved by using the next free position. The file is empty. Records with keys 150 and 59 are stored in that order. Where is each one stored?

150 MOD 13: 13 × 11 = 143 and 150 − 143 = 7, so key 150 goes to position 7.
59 MOD 13: 13 × 4 = 52 and 59 − 52 = 7, so key 59 also hashes to position 7. This is a collision.
Position 7 is full, so the next position, 8, is tried. It is free.

Answer: Key 150 is in position 7 and key 59 is in position 8.

Ask about this

Type what you are stuck on. The helper finds the explanation, worked examples and the notes to read, free and instant.

Keep going

← User-defined data types Floating-point numbers, representation and manipulation →Take a Computer Science A2 test