File organisation and access
Introduit| English | Sens |
|---|---|
| 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 séquentiel |
| sequential file/siːˈkwenʃl faɪl/ | fichier linéaire |
| 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 |
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.
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
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
Follow a file from storage to program and back safely.
A serial file stores records:
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
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.
Difficulté 2/5 · 140 pièces + un petit bonus lors de la première réussite aujourd'hui
Serial = arrival order; sequential = sorted; random = hashed position; indexed-sequential = sorted + an index.
A random (direct-access) file places each record:
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
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?
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
Order of arrival versus sorted by key. That single difference is what makes a sequential file searchable early and slow to insert into.
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.
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
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.
Difficulté 3/5 · 200 pièces + un petit bonus lors de la première réussite aujourd'hui
No searching happens at all: the key is turned into a position and read once. The final check catches a collision.
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.
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
Direct access suits looking up a single record.
Match each situation to the file organisation that suits it.
Difficulté 2/5 · 140 pièces + un petit bonus lors de la première réussite aujourd'hui
Append only, process everything in order, or look one record up: the dominant operation picks the organisation.
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:
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
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.
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
Every organisation is fast at something and slow at something else, so the operation done most often decides.
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 tout that apply.
Difficulté 2/5 · 140 pièces + un petit bonus lors de la première réussite aujourd'hui
Nothing is lost; a collision costs one extra read. It is unavoidable in principle, because there are always more possible keys than addresses.
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.
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