How records are arranged in a file decides how quickly one can be found. Serial and sequential files are read from the start; a random file uses a hashing algorithm on the key to jump straight to the right address.
File organisation is how records are arranged in a file. In a serial file records are stored in the order they arrive; in a sequential file they are stored in order of a key field; in a random file each record is stored at an address calculated from its key by a hashing algorithm. File access is how a record is reached: sequential access reads records one after another from the start (serial and sequential files), while direct access goes straight to the record (random files via the hash, sequential files via an index). When two keys hash to the same address there is a collision, handled by storing the record in the next free address or in an overflow area.
Fig. 1: the same five records in a serial, a sequential and a random file
Section 01
Three ways to organise a file.
The organisation is fixed when records are written. Each method suits a different pattern of use, so learn what it is, how a record is added and where it is used.
Organisation
How records are stored
Adding a record
Typical use
Serial
one after another in the order they arrive; no key order
append to the end of the file
transaction logs, audit trails, temporary files
Sequential
in ascending (or descending) order of a key field
copy records to a new file, inserting the new one in its place
master files processed in batches, e.g. payroll
Random
at an address calculated from the key by a hashing algorithm
hash the key and write the record at that address
records that must be found quickly one at a time, e.g. stock look-up at a till
Examiner trap
Serial and sequential are not the same. A serial file has no order; a sequential file is sorted on a key field. Say which key the file is ordered by to earn the mark.
Section 02
Sequential and direct access.
Organisation is how the records sit in the file; access is how the program reaches one. The syllabus pairs them like this.
Sequential access, serial file: read from the first record until the key is found or the file ends. On average half the records are read; a missing key means reading them all.
Sequential access, sequential file: read from the start, but stop as soon as a key greater than the target is passed, because the record cannot be later in the file.
Direct access, sequential file: an index of keys and positions is searched first, then the program jumps to that part of the file.
Direct access, random file: the hashing algorithm turns the key into an address and the record is read from there, with no searching.
Worked example Choose the organisation
An electricity company produces a bill for every customer once a month. Its call centre must also show any single customer's account within a second. Which organisation and access method suits each task?
Monthly billing processes almost every record (a high hit rate), in key order, in one batch run.
So a sequential file accessed sequentially suits billing: no time is wasted calculating addresses.
The call centre needs one record at a time, quickly, with a low hit rate per run.
So direct access suits it: a random file with a hash on the account number (or an indexed sequential file).
Answer: Billing: sequential file, sequential access. Look-up: random file (or indexed sequential), direct access.
Your turn
A school's door-entry system records every swipe card use with the time. The log is printed in full at the end of each week. Which file organisation is most suitable, and why?
Serial: records are simply appended in the order they happen, which is fast, and the whole file is read from the start when it is printed, so no key order or direct access is needed.
Stage 1 · Learn
Check what the sim just showed you
Four quick checks. Each correct answer earns XP and records this skill on your profile.
Quick check+10 XP
In which file organisation are records stored in the order they were added, with no key order?
Quick check+10 XP
Records are searched sequentially in a file sorted by key. The record with key 207 is wanted and key 214 has just been read. What should happen?
Quick check+10 XP
The hash is Key MOD 11. Which key collides with key 30?
Quick check+10 XP
When the next free address method is used, why must a search continue past the home address?
Section 03
Hashing and collisions.
A hashing algorithm is a calculation on the key field that produces the address where the record is stored. The same calculation finds the record again. Try it in the lab, which uses 11 addresses and the hash Key MOD 11.
Division (MOD): address = key MOD number of addresses. 45127 MOD 1000 = 127.
Folding: split the key into parts and add them, then MOD to fit: 314159 gives 31 + 41 + 59 = 131, and 131 MOD 100 = 31.
Collision: two keys give the same address, e.g. 45127 and 83127 both hash to 127.
Next free address: move on one address at a time (wrapping round at the end) until an empty one is found; searching must follow the same path.
Overflow area: store the clashing record in a separate area that is searched serially when the record is not at its home address.
// Customers.dat: addresses 0 to 999; an empty slot has CustomerID 0
// assumes the file is never completely full
PROCEDURE AddCustomer(NewCust : CustomerRecord)
DECLARE Address : INTEGER
DECLARE Current : CustomerRecord
Address ← NewCust.CustomerID MOD 1000
OPENFILE "Customers.dat" FOR RANDOM
SEEK "Customers.dat", Address
GETRECORD "Customers.dat", Current
WHILE Current.CustomerID <> 0
Address ← (Address + 1) MOD 1000
SEEK "Customers.dat", Address
GETRECORD "Customers.dat", Current
ENDWHILE
SEEK "Customers.dat", Address
PUTRECORD "Customers.dat", NewCust
CLOSEFILE "Customers.dat"
ENDPROCEDURE
Worked example Insert with collisions
A random file has addresses 0 to 10 and the hash Key MOD 11. Keys 25, 36, 15 and 30 are inserted in that order, using the next free address for collisions. Where is each stored?
25 MOD 11 = 3 (11 × 2 = 22, remainder 3): address 3 is free, store 25 there.
36 MOD 11 = 3: address 3 is taken by 25, so try 4, which is free. Store 36 at 4.
15 MOD 11 = 4: address 4 is taken by 36 (a record that itself collided), so try 5, which is free. Store 15 at 5.
30 MOD 11 = 8: free, store 30 at 8.
Answer: 25 at 3, 36 at 4, 15 at 5, 30 at 8
Your turn
Using the file above, how many addresses are read when searching for key 26, and what is the result?
26 MOD 11 = 4. Read 4 (36), then 5 (15), then 6, which is empty, so the search stops: 3 addresses read and 26 is not in the file.
Examiner trap
After hashing, always compare the key of the record found with the key wanted. The record at the home address may belong to a different key that collided there.
Stage 2 · Exam
Exam-style questions
Unlocks once the four checks above are done. Worth more XP, written to A Level Paper 3 and Paper 4 standard.
Finish the four checks above to unlock the exam questions
Exam style+20 XP
Which method of file access is used to read a record from a random file?
Exam style+20 XP
A payroll program processes every employee record once a month. Which organisation is most suitable?
Exam style+20 XP
A hashing algorithm sums pairs of digits and then takes MOD 100. What address does key 527319 give?
Exam style+20 XP
What is a collision in a random file?
Skill unlocked
File organisation, access and hashing, mastered.
This skill is now recorded on your profile. Keep the chain going.