Organisation des fichiers - Chapitre 1

Organisation des Fichiers

• Le chapitre vise à distinguer les différents types d'organisation de fichiers.
• Il cherche à identifier les caractéristiques de mise en œuvre de chaque type, ses limites et ses avantages.

Introduction

• L'organisation de fichiers se réfère à la manière dont les enregistrements d'un fichier sont physiquement stockés sur le support de stockage.
• L'organisation permet d'attribuer un emplacement physique pour chaque enregistrement logique du fichier.

Rappel (Niveau application)

• Un fichier est une suite d'enregistrements persistants, accessibles via des opérations spécifiques du langage de programmation (ex : en Pascal : read(f,e), write(f,e), reset(f)).
• Il existe des fichiers typés (suites d'enregistrements) et non typés (flux d'octets).

Rappel (Niveau système)

• Un fichier est une collection de blocs physiques contenant des octets non interprétés.
• Les données (enregistrements) sont stockées dans les blocs selon une organisation donnée.

Remarque

• Les opérations d'application passent par le système pour accéder physiquement aux blocs d'E/S.
• Le système maintient un cache (buffer cache) en mémoire centrale (MC) pour des accès plus rapides à certains blocs fréquemment utilisés.
• Le cache est transparent aux programmes d'application.

Organisation d'un fichier sur le disque

• Les programmes utilisent la mémoire centrale (MC) et le système de stockage (MS).
• Le buffer cache sert de mémoire tampon.
• Les blocs physiques sur le disque stockent les enregistrements.
• La taille des blocs dépend des caractéristiques du disque.

Organisation des fichiers & Méthodes d'accès

• Pour gérer un fichier, le système a besoin d'informations sur ses caractéristiques (blocs utilisés, organisation, droits d'accès).
• Une structure de fichier définit la façon d'organiser les données et les algorithmes pour manipuler les données.
• Les méthodes d'accès définissent comment localiser les articles dans le fichier.

Structures simples

• Les méthodes classiques d'organisation comprennent les structures simples, les méthodes d'index, les méthodes d'arbre et les méthodes de hachage.
• Les méthodes modernes incluent les méthodes LH, TH, MTH et RP*.

Organisation globale des blocs

• La mémoire de stockage (MS) est modélisée comme une zone contigüe de blocs numérotées, permettant un accès séquentiel.
• Les blocs sont des zones contiguës d'octets de même taille, contenant les données du fichier.
• Un fichier peut être vu comme un tableau ou une liste chaînée, les blocs étant contigus ou non.

Organisation globale des blocs (fichier vu comme une liste chaînée)

• Dans le cas d'un fichier non ordonné, les insertions se font à la fin ; l'accès est séquentiel.
• Pour les fichiers ordonnés, les insertions peuvent nécessiter des décalages, et l'accès peut être séquentiel ou dichotomique.
• Dans les deux cas, l'accès est généralement séquentiel.
• Des informations, comme le numéro du bloc suivant, sont nécessaires dans chaque bloc.

Organisation interne des blocs

• Les enregistrements peuvent avoir une longueur fixe ou variable.
• Pour les enregistrements de longueur fixe, chaque bloc contient un tableau d'enregistrements de même type.
• Pour les enregistrements de longueur variable, le bloc peut contenir une chaîne de caractères.

Enregistrements de longueur fixe

• Un enregistrement de longueur fixe prend une taille spécifique.
• L'effacement d'un enregistrement peut poser problème, nécessitant des réorganisations éventuelles.
• Il est possible d'utiliser une structure fichier avec en-tête et des pointeurs pour faciliter les insertions et suppressions.

Enregistrements de longueur variable

• Les enregistrements peuvent avoir des longueurs différentes.
• On peut les organiser en utilisant des espaces réservés ou des pointeurs pour gérer la variation de longueur.
• Dans la méthode par espaces réservés, la création occupe toute la taille maximale prévue.
• Dans la méthode par pointeurs, des enregistrements de longueur fixe contiennent des pointeurs vers les enregistrements de longueur variable.
• Il existe des inconvénients liés à la fragmentation et la dynamique de la taille.

Organisation des enregistrements par blocs

• Cette organisation regroupe les enregistrements liés dans des blocs.
• Il existe un bloc d'accrochage pour les premiers enregistrements et d'autres pour le débordement.
• Tous les enregistrements d'un bloc ont la même taille.
• Les accès disque sont gérés pour optimiser les performances.
• La taille des blocs varie, allant de 512 octets à plusieurs milliers d'octets.

Taxonomie des structures simples de fichiers

• Différentes combinaisons d'organisation globale (tableau/liste), d'ordre (ordonné/non ordonné), de format (fixe/variable) et de chevauchement (avec/sans) permettent de varier les structurations des fichiers.

Conclusion

• Le choix de l'organisation et du support de stockage influence grandement le mode d'accès aux données.
• Le temps d'accès, le facteur de chargement, la taille du fichier, les tailles des structures auxiliaires et le type d'accès (statique ou dynamique) sont des paramètres importants à considérer lors de la conception d'une méthode d'accès.