File organisation and access · Organisation et accès aux fichiers
| English | Français |
|---|---|
| file organisation/faɪl ˌɔːɡənaɪˈzeɪʃn/ | organisation de fichiers |
| access method/ˈækses ˈmeθəd/ | méthode d'accès |
| serial file/ˈsɪərɪəl faɪl/ | fichier serial |
| sequential file/siːˈkwenʃl faɪl/ | fichier séquentiel |
| key field/kiː fiːld/ | champ clé |
| direct access/daɪˈrekt ˈækses/ | accès direct |
| sequential access/siːˈkwenʃl ˈækses/ | accès séquentiel |
| random file/ˈrændəm faɪl/ | fichier aléatoire |
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.
Pourquoi le travail de nuit de la banque a pris toute la nuit
- Jusqu'aux années 1980, les comptes bancaires vivaient sur bande magnétique. Une bande ne peut être lue que d'une extrémité à l'autre, donc les transactions de la journée étaient triées pendant la nuit et tout le fichier maître était lu de bout en bout, une seule fois, pour les appliquer.
- Demander le solde d'un client au milieu de l'après-midi et la réponse était : pas avant demain. L'organisation du fichier, pas la vitesse de l'ordinateur, décidait ce que la banque pouvait offrir.
- Les disques ont rendu possible une organisation différente : calculer l'emplacement d'un enregistrement à partir de sa clé et sauter dessus. C'est ce qui permet à un distributeur automatique de répondre en une seconde.
- Cette leçon porte sur l'organisation des fichiers 文件组织, les deux modes d'accès 访问方式, et comment choisir selon ce que fait principalement le programme.
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
Trois organisations
- Un fichier séquentiel 串行 file contient des enregistrements dans l'ordre d'ajout, sans tri. L'ajout est rapide ; la recherche signifie lire depuis le début. Utilisé pour les journaux et les traces d'audit.
- Un fichier séquence 顺序文件 contient des enregistrements triés par un champ clé 键字段. La recherche est plus rapide, car on peut s'arrêter tôt ou faire une recherche binaire ; l'insertion est lente, car les enregistrements ultérieurs doivent bouger. Utilisé pour les fichiers maîtres mis à jour par lots.
- Un fichier aléatoire 随机文件, ou direct-access, contient chaque enregistrement à une position calculée à partir de sa clé d'enregistrement, généralement par une fonction de hachage. La recherche par clé est très rapide ; la lecture dans l'ordre des clés est malaisée. Utilisé pour les grandes tables de recherche et les comptes clients.
*Séquentiel : ordre d'arrivée, rien de plus
*Séquence : les mêmes enregistrements, dans l'ordre des clés
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
Les deux modes d'accès
- L'accès séquentiel 顺序存取 lit depuis le début du fichier jusqu'à l'enregistrement souhaité. C'est le seul accès qu'un fichier séquentiel 串行 file autorise, et c'est ainsi qu'un fichier séquence 顺序file est traité en lot.
- L'accès direct 直接存取 saute directement à une position connue sans lire ce qui précède. C'est ainsi qu'un fichier aléatoire 随机file est lu, et un fichier séquence 顺序file peut aussi être lu directement lorsque l'emplacement d'une clé est connu ou indexé.
- Donc l'association du programme officiel est : accès séquentiel pour les fichiers série et séquence ; accès direct pour les fichiers séquence et aléatoires.
*Aléatoire : la clé vous dit où chercher
File access route · Voie d'accès au fichier
Follow a file from storage to program and back safely. · Suivre un fichier depuis le stockage jusqu'au programme et retour en toute sécurité.
A serial file stores records: · Un fichier séquentiel stocke les enregistrements :
Serial files keep records in arrival order — fast to append, slow to search. Sequential files are sorted by key. · Les fichiers séquentiels conservent les enregistrements dans l'ordre d'arrivée — rapide pour l'ajout, lent pour la recherche. Les fichiers séquentiels (sequential) sont triés par clé.
Match each file organisation to how it stores records. · Reliez chaque organisation de fichier à la manière dont elle stocke les enregistrements.
Serial = arrival order; sequential = sorted; random = hashed position; indexed-sequential = sorted + an index. · Série = ordre d'arrivée ; séquentiel = trié ; aléatoire = position hachée ; indexé-séquentiel = trié + un index.
A random (direct-access) file places each record: · Un fichier aléatoire (accès direct) place chaque enregistrement :
A key is converted (often by a hash) to a position, so a single-key lookup is very fast. · Une clé est convertie (souvent par un hachage) en une position, donc une recherche par clé unique est très rapide.
What is the difference between a serial file and a sequential file? · Quelle est la différence entre un fichier série et un fichier séquentiel ?
Order of arrival versus sorted by key. That single difference is what makes a sequential file searchable early and slow to insert into. · Ordre d'arrivée versus trié par clé. Cette seule différence rend un fichier séquentiel recherchable précocement et lent à insérer dedans.
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.
Exemple résolu : choisir l'organisation
- Un programme de paie lit tous les enregistrements de personnel une fois par mois, dans l'ordre du numéro de personnel, pour produire les bulletins de paie. Quelle organisation et quel accès, et pourquoi ?
- Organisation séquence avec accès séquentiel : tous les enregistrements sont traités, donc il n'y a aucun avantage à sauter çà et là, et les stocker dans l'ordre des clés signifie que les bulletins sortent dans l'ordre sans étape de tri.
- Un distributeur automatique doit récupérer un compte par son numéro en moins d'une seconde. Organisation aléatoire avec accès direct : l'emplacement est calculé à partir du numéro de compte, donc exactement une lecture est nécessaire au lieu d'une recherche parmi des millions.
- Un serveur web ajoute une ligne par requête à un journal. Série : seul l'ajout compte, et ajouter à la fin est la chose la plus rapide qu'un fichier série puisse faire.
A sequential file can be read by sequential access and also by direct access. · Un fichier séquentiel peut être lu par accès séquentiel et aussi par accès direct.
Sequential access serves serial and sequential files; direct access serves sequential and random files. Only a serial file is limited to one method. · L'accès séquentiel sert les fichiers séries et séquentiels ; l'accès direct sert les fichiers séquentiels et aléatoires. Seul un fichier série est limité à une seule méthode.
Put the steps of fetching one account from a random file in order. · Placez les étapes de récupération d'un compte depuis un fichier aléatoire dans l'ordre.
No searching happens at all: the key is turned into a position and read once. The final check catches a collision. · Aucune recherche n'a lieu : la clé est transformée en position et lue une seule fois. La vérification finale attrape une 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?
Les compromis, côte à côte
| série | séquence | aléatoire | |
|---|---|---|---|
| ordre des enregistrements | tel que ajouté | trié par clé | calculé à partir de la clé |
| ajouter un enregistrement | rapide, ajout | lent, les enregistrements bougent | rapide, si la case est libre |
| trouver un enregistrement | lent, lire tout | plus rapide, peut s'arrêter tôt | le plus rapide, une lecture |
| lire dans l'ordre des clés | nécessite un tri | naturel | nécessite un tri |
- La bonne réponse est toujours argumentée à partir de l'opération dominante : que fait ce programme le plus souvent ?
Sequential file organisation is well suited to processing every record in turn. · L'organisation de fichier séquentiel est bien adaptée au traitement de chaque enregistrement à tour de rôle.
Direct access suits looking up a single record. · L'accès direct convient pour rechercher un seul enregistrement.
Match each situation to the file organisation that suits it. · Reliez chaque situation à l'organisation de fichier qui lui convient.
Append only, process everything in order, or look one record up: the dominant operation picks the organisation. · Ajouter uniquement, traiter tout dans l'ordre, ou chercher un enregistrement unique : l'opération dominante détermine l'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.
Exemple résolu : justifier un changement
- Le fichier de livres d'une bibliothèque est série. Rechercher un titre est lent. Suggérer un changement et le justifier.
- Réorganiser en tant que fichier aléatoire, en hachant l'ISBN vers une adresse, de sorte qu'une recherche devient une lecture directe unique au lieu d'une analyse de tout le fichier.
- Si la bibliothèque imprime aussi un catalogue dans l'ordre des titres, une organisation séquence par titre sert raisonnablement les deux : le catalogue n'a pas besoin de tri et une recherche peut s'arrêter tôt ou faire une recherche binaire.
- Nommez l'organisation, nommez la méthode d'accès et liez-les toutes deux à une opération mentionnée dans la question.
To produce reports in key order, the best file organisation is: · Pour produire des rapports dans l'ordre des clés, la meilleure organisation de fichier est :
A sequential file is already in key order, so reading it sequentially gives an in-order report. · Un fichier séquentiel est déjà dans l'ordre des clés, donc sa lecture séquentielle donne un rapport en ordre croissant.
A file organisation is chosen by looking at the program's ____ operation. · Une organisation de fichier est choisie en regardant l'opération ____ du programme.
Every organisation is fast at something and slow at something else, so the operation done most often decides. · Chaque organisation est rapide à quelque chose et lente à autre chose, donc c'est l'opération réalisée le plus souvent qui décide.
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.
Ce que doit être la clé et pourquoi le hachage s'effondre
- L'accès direct nécessite une clé, et cette clé doit être unique pour un seul enregistrement. Un nom de famille n'est pas une clé ; un numéro de client l'est.
- Le hachage transforme cette clé en une adresse d'enregistrement en un seul calcul, de sorte qu'une seule lecture atteint l'enregistrement peu importe la taille du fichier.
- Deux clés différentes peuvent hacher vers la même adresse. C'est une collision, et ce n'est pas une faute de l'algorithme : c'est inévitable dès lors qu'il y a plus de clés possibles que d'adresses.
- La solution mentionnée dans la grille d'évaluation est une zone de débordement, ou le stockage d'un pointeur à l'adresse pointant vers une chaîne d'enregistrements qui la partagent. Une collision coûte donc une lecture supplémentaire, pas la perte d'un enregistrement.
- Ainsi, la comparaison honnête est : le hachage offre un accès quasi constant jusqu'à ce que le fichier soit plein, et ses performances se dégradent à mesure que les collisions s'accumulent. L'accès séquentiel ne se dégrade jamais mais n'a jamais été rapide.
Two records hash to the same address. Which are true? Select all · tout that apply. · Deux enregistrements hachent vers la même adresse. Quelles affirmations sont vraies ? Sélectionnez toutes celles qui s'appliquent.
Nothing is lost; a collision costs one extra read. It is unavoidable in principle, because there are always more possible keys than addresses. · Rien n'est perdu ; une collision coûte une lecture supplémentaire. Elle est inévitable en principe, car il y a toujours plus de clés possibles que d'adresses.
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.
Pièges qui font perdre des points
- Série (Serial) désigne l'ordre d'arrivée ; séquentiel désigne trié par une clé. Ce ne sont pas des synonymes, et l'examen teste exactement cette différence.
- Organisation désigne la façon dont les enregistrements sont disposés ; accès désigne comment le programme accède à l'un d'eux. Une question nomme l'un ou l'autre.
- Un fichier séquentiel supporte les deux méthodes d'accès ; un fichier série ne supporte que l'accès séquentiel.
- Justifiez depuis l'opération dominante, et non simplement parce que « c'est plus rapide ». Dites plus rapide pour quoi, et pourquoi.
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
Vous avez compris
- série : ordre d'ajout, ajout rapide, recherche lente, utilisé pour les journaux · séquentiel : trié par un champ clé, bon pour le traitement par lots et la sortie dans l'ordre · aléatoire : position calculée à partir de la clé d'enregistrement, une lecture pour trouver un enregistrement
- l'accès séquentiel lit depuis le début ; l'accès direct saute à une position
- l'accès séquentiel sert les fichiers séries et séquentiels ; l'accès direct sert les fichiers séquentiels et aléatoires
- choisissez selon l'opération dominante : traiter tout, chercher un seul, ou seulement ajouter