File organisation and access · 文件组织与访问
| English | 中文 | Pinyin · 拼音 |
|---|---|---|
| file organisation/faɪl ˌɔːɡənaɪˈzeɪʃn/ | 文件组织 | wén jiàn zǔ zhī |
| access method/ˈækses ˈmeθəd/ | 访问方式 | fǎng wèn fāng shì |
| serial file/ˈsɪərɪəl faɪl/ | 串行文件 | chuàn xíng wén jiàn |
| sequential file/siːˈkwenʃl faɪl/ | 顺序文件 | shùn xù wén jiàn |
| key field/kiː fiːld/ | 键字段 | jiàn zì duàn |
| direct access/daɪˈrekt ˈækses/ | 直接存取 | zhí jiē cún qǔ |
| sequential access/siːˈkwenʃl ˈækses/ | 顺序存取 | shùn xù cún qǔ |
| random file/ˈrændəm faɪl/ | 随机文件 | 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.
银行的夜间批处理为什么要跑一整夜
- 直到 1980 年代,银行的账户还住在磁带上。磁带只能从一头读到另一头,所以当天的交易要连夜排序,整个主文件从头到尾读一遍来应用它们。
- 下午在中途想查某位客户的余额,答案是:明天才有。决定银行能提供什么的,是文件的组织方式,而不是计算机的速度。
- 磁盘让另一种组织成为可能:根据记录的键算出它在哪里,然后跳过去。这就是取款机能在一秒内回答的原因。
- 这一课讲文件组织(file organisation)、两种访问方式(access method),以及怎样从程序主要做什么出发来选择。
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
三种组织方式
- 串行文件(serial file)按记录加入的顺序保存,不排序。追加很快;查找意味着从头读起。用于日志和审计轨迹。
- 顺序文件(sequential file)按键字段(key field)排序保存记录。查找更快,因为可以提前停止或二分查找;插入很慢,因为后面的记录必须移位。用于批量更新的主文件。
- 随机文件(random file,直接存取文件)把每条记录放在由它的记录键算出的位置上,通常用散列。按键查找非常快;按键顺序读取则不方便。用于大型查找表和客户账户。
串行:到达的顺序,别无其他
顺序:同样的记录,按键排列
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
两种访问方式
- 顺序存取(sequential access)从文件开头读到想要的记录。这是串行文件唯一允许的访问方式,也是顺序文件在批处理中被处理的方式。
- 直接存取(direct access)不读前面的内容,直接跳到已知位置。这是读随机文件的方式;当某个键的位置已知或已建索引时,顺序文件也可以被直接存取。
- 所以大纲的配对是:顺序存取用于串行和顺序文件;直接存取用于顺序和随机文件。
随机:键告诉你去哪里找
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.
例题:选择组织方式
- 一个工资程序每月按工号顺序把每条员工记录读一遍,生成工资单。用哪种组织和访问方式,为什么?
- 顺序组织加顺序存取:每条记录都要处理,所以到处跳没有任何好处;而按键顺序存储意味着工资单直接按顺序出来,不需要排序步骤。
- 取款机必须在一秒内按账号取出一个账户。 随机组织加直接存取:位置由账号算出,所以只需要恰好一次读取,而不是在几百万条中查找。
- 一台 Web 服务器每收到一个请求就往日志追加一行。 串行:只有追加要紧,而追加到末尾正是串行文件最快的事。
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.
例题:论证一次改动
- 一家图书馆的图书文件是串行的。查找一本书很慢。提出一项改动并论证。
- 重组为随机文件,把 ISBN 散列成地址,于是查找变成一次直接读取,而不是扫描整个文件。
- 如果图书馆还要按书名顺序打印目录,按书名的顺序组织能兼顾两者:目录不需要排序,查找也能提前停止或二分。
- 说出组织方式、说出访问方式,并把两者都与题目提到的某个操作绑定。
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
你掌握了
- 串行:按加入顺序、追加快、查找慢、用于日志 · 顺序:按键字段排序,适合批处理和按序输出 · 随机:位置由记录键算出,一次读取找到记录
- 顺序存取从开头读起;直接存取跳到某个位置
- 顺序存取服务于串行和顺序文件;直接存取服务于顺序和随机文件
- 从主导操作选择:处理全部、查一条,还是只追加