ファイル組織化とアクセス

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

Worked example: choose the organisation

The trade-offs, side by side

• The right answer is always argued from the dominant operation: what does this program do most?

Worked example: justify a change

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.

Marks that slip away

You've got it