File organisation and access
| English | Chinese | Pinyin |
|---|---|---|
| file organisation | 文件组织 | wén jiàn zǔ zhī |
| access method | 访问方式 | fǎng wèn fāng shì |
| serial file | 串行文件 | chuàn xíng wén jiàn |
| sequential file | 顺序文件 | shùn xù wén jiàn |
| key field | 键字段 | jiàn zì duàn |
| direct access | 直接存取 | zhí jiē cún qǔ |
| sequential access | 顺序存取 | shùn xù cún qǔ |
| random file | 随机文件 | suí jī wén jiàn |
Why the bank's night job took all night
- Into the 1980s a bank's accounts lived on magnetic tape. A tape can only be read from one end to the other, so the day's transactions were sorted overnight and the whole master file was read start to finish, once, to apply them.
- Ask for one customer's balance in the middle of the afternoon and the answer was: not until tomorrow. The organisation of the file, not the speed of the computer, decided what the bank could offer.
- Disks made a different organisation possible: compute where a record is from its key and jump there. That is what lets a cash machine answer in a second.
- This lesson is file organisation 文件组织, the two access methods 访问方式, and how to choose from what the program mostly does.
Three organisations
- A serial file 串行文件 holds records in the order they were added, with no sorting. Appending is fast; searching means reading from the start. Used for logs and audit trails.
- A sequential file 顺序文件 holds records sorted by a key field 键字段. Searching is faster, because you can stop early or binary-search; inserting is slow, because later records must shift. Used for master files updated in batch.
- A random, or direct-access, file 随机文件 holds each record at a position computed from its record key, usually by a hash. Lookup by key is very fast; reading in key order is awkward. Used for large lookup tables and customer accounts.
Serial: order of arrival, nothing more
Sequential: the same records, in key order
The two access methods
- Sequential access 顺序存取 reads from the start of the file to the record wanted. It is the only access a serial file allows, and it is how a sequential file is processed in a batch.
- Direct access 直接存取 jumps straight to a known position without reading what comes before. It is how a random file is read, and a sequential file can also be read directly when the position of a key is known or indexed.
- So the syllabus pairing is: sequential access for serial and sequential files; direct access for sequential and random files.
Random: the key tells you where to look
File access route
Follow a file from storage to program and back safely.
A serial file stores records:
Serial files keep records in arrival order — fast to append, slow to search. Sequential files are sorted by key.
Match each file organisation to how it stores records.
Serial = arrival order; sequential = sorted; random = hashed position; indexed-sequential = sorted + an index.
A random (direct-access) file places each record:
A key is converted (often by a hash) to a position, so a single-key lookup is very fast.
What is the difference between a serial file and a sequential file?
Order of arrival versus sorted by key. That single difference is what makes a sequential file searchable early and slow to insert into.
Worked example: choose the organisation
- A payroll program reads every employee record once a month, in employee-number order, to produce payslips. Which organisation and access, and why?
- Sequential organisation with sequential access: every record is processed, so there is nothing to gain from jumping about, and storing them in key order means the payslips come out in order with no sorting step.
- A cash machine must fetch one account by its number in under a second. Random organisation with direct access: the position is computed from the account number, so exactly one read is needed instead of a search through millions.
- A web server appends one line per request to a log. Serial: only appending matters, and appending to the end is the fastest thing a serial file does.
A sequential file can be read by sequential access and also by direct access.
Sequential access serves serial and sequential files; direct access serves sequential and random files. Only a serial file is limited to one method.
Put the steps of fetching one account from a random file in order.
No searching happens at all: the key is turned into a position and read once. The final check catches a collision.
The trade-offs, side by side
| serial | sequential | random | |
|---|---|---|---|
| order of records | as added | sorted by key | computed from key |
| adding a record | fast, append | slow, records shift | fast, if the slot is free |
| finding one record | slow, read all | faster, can stop early | fastest, one read |
| reading in key order | needs a sort | natural | needs a sort |
- The right answer is always argued from the dominant operation: what does this program do most?
Sequential file organisation is well suited to processing every record in turn.
Direct access suits looking up a single record.
Match each situation to the file organisation that suits it.
Append only, process everything in order, or look one record up: the dominant operation picks the organisation.
Worked example: justify a change
- A library's book file is serial. Searching for one title is slow. Suggest a change and justify it.
- Reorganise as a random file, hashing the ISBN to an address, so a search becomes one direct read instead of a scan of the whole file.
- If the library also prints a catalogue in title order, a sequential organisation by title serves both reasonably: the catalogue needs no sort and a search can stop early or binary-search.
- Name the organisation, name the access method, and tie both to an operation the question mentions.
To produce reports in key order, the best file organisation is:
A sequential file is already in key order, so reading it sequentially gives an in-order report.
A file organisation is chosen by looking at the program's ____ operation.
Every organisation is fast at something and slow at something else, so the operation done most often decides.
What the key has to be, and why hashing breaks
- Direct access needs a key, and the key must be unique to one record. A surname is not a key; a customer number is.
- Hashing turns that key into a record address in one calculation, so a single read reaches the record however large the file is.
- Two different keys can hash to the same address. That is a collision, and it is not a fault in the algorithm: it is unavoidable once there are more possible keys than addresses.
- The fix named in the mark scheme is an overflow area, or storing a pointer at the address to a chain of records that share it. A collision therefore costs one extra read, not a lost record.
- So the honest comparison is: hashing gives near-constant access until the file fills up, and its performance degrades as collisions build. Sequential access never degrades but was never fast.
Two records hash to the same address. Which are true? Select all that apply.
Nothing is lost; a collision costs one extra read. It is unavoidable in principle, because there are always more possible keys than addresses.
Marks that slip away
- Serial is order of arrival; sequential is sorted by a key. They are not synonyms, and the exam tests exactly that difference.
- Organisation is how the records are laid out; access is how the program reaches one. A question names one or the other.
- A sequential file supports both access methods; a serial file supports only sequential access.
- Justify from the dominant operation, not from "it is faster". Say faster at what, and why.
You've got it
- serial: order added, append fast, search slow, used for logs · sequential: sorted by a key field, good for batch processing and in-order output · random: position computed from the record key, one read to find a record
- sequential access reads from the start; direct access jumps to a position
- sequential access serves serial and sequential files; direct access serves sequential and random files
- choose from the dominant operation: process everything, look one up, or only append