SLIDE 1
CSZone.co.uk
Click to advance · Arrow keys also work
CAIE 9618 · Paper 3 · Topic 3.1.2

File Organisation
& Access

Serial · Sequential · Random (Direct) Access · Index Files

CSZone Cambridge International AS & A Level Computer Science 9618
Serial File Organisation

Records in Arrival Order — Unordered

STRUCTURE
Records written in the order they arrive — no sorting
New records always appended at the end
Must read from beginning to find a specific record
Works on any storage medium (including tape)
USE CASES
Log files, transaction logs, audit trails — where records are added in real time and batch-processed later.
ADVANTAGES & DISADVANTAGES
Simple to implement and write to
No wasted space — records fill continuously
Searching is O(n) — must read all previous records
Cannot update a record in place (must rewrite whole file)
Sequential File Organisation

Records Ordered by Key Field

STRUCTURE
Records stored in order of a key field (e.g. student ID, surname)
Must read from the beginning but can stop early once key passed
Adding a record requires rewriting the file to maintain order
Can use binary search if stored on random-access medium
USE CASES
Batch processing (e.g. weekly payroll): master file sorted by employee ID is updated by sorted transaction file in a single sequential pass.
MASTER FILE UPDATE
Old master + sorted transactions → new master. Three-generation backup: grandfather–father–son.
Random (Direct) Access

Jump Directly to Any Record

HOW IT WORKS
Each record stored at a physical address calculated from its key
Hashing algorithm: address = hash(key)
Read/write head can jump directly to the address (disk)
O(1) access time — no searching required
COLLISIONS
Two keys hashing to same address — handled by overflow areas or chaining (linked list of overflow records).
ADVANTAGES & DISADVANTAGES
Fast retrieval — O(1) average case
Can update individual records without rewriting file
Suitable for online, real-time systems
Wasted space (empty slots) — load factor must be managed
Collisions degrade performance
Only works on random-access devices (disk, SSD)
Index Sequential Files

Best of Both Worlds

Index sequential combines sequential storage with a separate index to allow both sequential processing and fast direct access.
STRUCTURE
Data file: records stored in key order on disk
Index file: stores key + disk address pairs (much smaller)
To find record: look up key in index → get address → jump directly
Can also traverse sequentially through data file
BENEFITS
Supports both batch processing (sequential scan) and real-time queries (index lookup). Used in databases and large file systems. Binary search on index makes lookups O(log n).
OVERHEAD
Extra storage for index file. Index must be maintained when records added/deleted.
Comparison Table

Serial vs Sequential vs Random vs Index

FeatureSerialSequentialRandomIndex Sequential
OrderArrival orderKey orderHash-basedKey order + index
Search speedO(n)O(n) or O(log n)O(1) avgO(log n)
Insert new recordAppend (fast)Rewrite fileDirect addressUpdate data + index
Batch processingGoodGoodPoorGood
Real-time accessPoorOK (binary search)ExcellentExcellent
Storage mediumAny (incl. tape)AnyDisk/SSD onlyDisk/SSD only
Space efficiencyHighHighLow (empty slots)Medium (index overhead)
Exam Practice

Cambridge-style questions

Question 1
A bank processes overnight payroll transactions for 50,000 employees. The employee master file is already stored in employee ID order, and the transaction file is also sorted by employee ID. State the most appropriate file organisation method and explain why. [3]
1
Sequential file organisation.
1
Both the master file and transaction file are already sorted by employee ID — a single sequential pass can process all transactions efficiently without jumping around the disk.
1
Batch processing of all 50,000 records at once overnight is exactly what sequential access is designed for — it is more efficient than random access for bulk operations.
Common Mistakes

Don't lose easy marks

1
Confusing serial and sequential — serial = unordered, arrival order. Sequential = ordered by key. Students often say "sequential" when they mean "serial". In an exam, "the file is in arrival order with no sorting" = serial.
2
Saying "random access is always best" — for batch processing of many records, sequential access is faster (one sweep through both files vs many individual disk seeks). Always match the method to the use case.
3
Forgetting the grandfather-father-son backup scheme used with sequential files — when updating a master file, keep three generations. If new master is corrupted, restore from old master + transactions.
Topic Summary — 3.1.2

What You Need to Know

SERIAL
Unordered, arrival order. Simple, append-only. O(n) search. Used for transaction logs.
SEQUENTIAL
Ordered by key. Good for batch processing. Must rewrite on insert. Grandfather-father-son backup.
RANDOM (DIRECT)
Hash key → address. O(1) access. Collisions handled via overflow/chaining. Real-time systems. Wasted space.
INDEX SEQUENTIAL
Key-ordered data file + index of key→address mappings. Supports both batch and real-time access. O(log n) via index.
CSZone

Next Video

3.1.3
Floating Point Representation
Mantissa · Exponent · Normalisation · Precision vs Range
Head to CSZone.co.uk for the complete worksheet, quiz, and interactive tools