Organisation des fichiers PDF

ORGANISATION DES FICHIERS Objectifs du chapitre : Distinguer les différentes types d’organisation. Identifier les caractéristiques de mise en œuvre de chaque type d’ organisation, ses limites et ses avantages. Introduction On désigne par organisation, la manière dont sont organisés...

ORGANISATION DES FICHIERS Objectifs du chapitre : Distinguer les différentes types d’organisation. Identifier les caractéristiques de mise en œuvre de chaque type d’ organisation, ses limites et ses avantages. Introduction On désigne par organisation, la manière dont sont organisés physiquement les enregistrement du fichier sur le support. L’organisation permet d’attribuer un emplacement sur le support physique pour tout enregistrement logique du fichier. Rappel Un fichier est le concept à travers lequel, un programme ou une application stocke des données en mémoire externe. Les fichiers sont utilisés à différents niveaux d'abstraction avec des sémantiques différentes. Au niveau Au niveau Application Système (niveau (ou langage de physique) programmation de haut niveau)  Rappel  Niveau application (ou langage de programmation de haut niveau) Un fichier est : une suite d'enregistrements (ou articles) persistants. l'accès aux enregistrements, à travers le langage de programmation considéré, se fait via des opérations spéciales pour les fichiers (ex en Pascal : read(f,e), write(f,e), reset(f), …). => Fichier typé. une suite d'octets, on parle alors de flux (exp : les streams de la librairie standard du langage C : FILE * ). => Fichier non typé  Rappel  Niveau Système (niveau physique) Un fichier est : un ensemble de blocs en MS, renfermant une suite d'octets non interprétés. Les données (par exemple les enregistrements) du fichier sont stockés à l'intérieur des blocs selon une certaine organisation. Remarque : Toutes les opérations du niveau 'application' passent par le système qui les traduit en opérations de bas niveau pour accéder physiquement aux blocs d'E/S de la MS. Comme les opérations d'E/S sont coûteuses (en temps), le système maintient en MC une zone spéciale de taille limitée (la zone tampon ou "buffer cache") lui permettant de garder en MC les copies de quelques blocs physiques choisis selon certaines stratégies (par exemple les plus utilisés). Cette zone tampon est totalement transparentes aux programmes d'application qui utilisent les fichiers Organisation d’un fichier sur le disque : Même si la dimension des blocs dépend des caractéristiques de l'unité Exemple de disque : et Si du unesystème d'exploitation, application demande la la lecture taille des enregistrements d'un enregistrementvarie elle le donné, aussi. système vérifie d'abord si le bloc concerné ne se trouve pas déjà en MC (dans la zone tampon). S'il y est, l'enregistrement cherché sera Il existe 2 modes directement de découpage transmis des données à l'application, enyenregistrements: sans qu'il ait de lecture physique.  Organisation des fichiers & Méthodes d'accès Pour que le système puisse gérer un fichier, il a besoin de connaître les informations sur ses caractéristiques : les blocs utilisés par le fichier, l'organisation du fichier, les droit d'accès associés,... Une structure de fichier consiste à définir et concevoir des structures de données et algorithmes associés, pour organiser les blocs d'un fichier sur MS et implémenter certaines opérations d'accès pour la manipulation des données du fichier. Structure du fichier Organisation du fichier : Méthode d'accès du fichier : Comment distinguer un Approche utilisée pour localiser article d'un autre un article dans le fichier. Organisation des fichiers & Méthodes d'accès Objectifs Combiner l'organisation du fichier et la méthode d'accès Étudier les opérations de base : Recherche, Insertion, Suppression, …. sous différentes méthodes d'accès :  les méthodes classiques ( Structures simples, méthodes d’index, méthodes d’arbre, méthode de hachage )  les nouvelles ( LH, TH, MTH, RP*, …) STRUCTURES SIMPLES  I. Organisation globale des blocs Afin d'étudier les méthodes d'accès aux fichiers dans un cadre général, on modélise la MS par une zone contigüe de blocs numérotés séquentiellement (adresses de blocs). Les blocs sont des zones contigües d'octets de même taille, renfermant les données (enregistrements) des fichiers. Dans un premier temps, on étudiera deux possibilités distinctes d'organiser les blocs au sein d'un fichier:  soit le fichier est vu comme un tableau : tous les blocs qui le forment sont contigus  soit le fichier est vu comme une liste chaînée : les blocs ne sont pas forcément contigus, mais sont chaînés entre eux. I. Organisation globale des blocs  Fichier vu comme une liste linéaire chaînée un tableau Le fichier peut être est un vu comme ensemble de Mune listecontigus blocs linéaire sur chaînée de blocs, le disque. C'estc'est par à dire constitué conséquent deun M tableau. blocs non contigus sur le disque. Le fichier peut être ordonné ou pas. S'il n'est pas ordonné, les ajouts d'articles se font à la fin du fichier. L'accès est alors séquentiel. S'il est ordonné, les ajouts d'articles causent des insertions de nouveaux blocs (allocation dynamique). S'il est ordonné, les ajouts d'articles causent des décalages. L'accès est alors soit dichotomique soit séquentiel. Dans les deux cas, l'accès est exclusivement séquentiel. I. Organisation globale des blocs Dans le schéma suivant, la MS contient 3 fichiers E, F et G Le fichier E est formé de 4 blocs contigus le fichier F est formé de 7 blocs contigus le fichier G est une liste de blocs. Remarque 2 1 Parmi Pour les un caractéristiques fichier vu commenécessaires liste, il suffirait pour par manipuler contre de un connaître fichier vu le numéro comme du premier tableau, bloc (la tête de la liste), car dans chaque bloc, il y a le numéro on pourra du prochain bloc (comme le champ suivant dans une liste). avoir par exemple : Dans le dernier bloc, le numéro du prochain bloc pourra être mis à une valeur spéciale - Le numéro (pardu exemple premier -1)bloc, pour indiquer la fin de la liste. - Le numéro du dernier bloc (ou alors le nombre de blocs utilisés)..  II.Organisation interne des blocs Les blocs sont censés contenir les enregistrements d'un fichier. Ces derniers peuvent être de longueur fixe ou variable. Si on est intéressé par des enregistrements de longueur fixe, chaque bloc pourra alors contenir un tableau d'enregistrements de même type.. Si on opte pour des enregistrements de tailles variables, chaque enregistrement sera vu comme étant une chaîne de cararactère (de longueur variable).  Les enregistrements seront de longueur variable, car par exemple, il y a un ou plusieurs champs ayant des tailles variables, ou alors le nombre de champs varie d'un enregistrement à un autre.  Pour séparer les champs entre eux (à l'intérieur de l'enregistrement), on pourra soit utiliser un caractère spécial ('#') ne pouvant pas être utilisé comme valeur légale, ou alors préfixer le début des champs par leur taille (sur un nombre fixe de positions). II.1 Enregistrements de longueur fixe Exemple: Soit des enregistrements de la base de données bancaire: struct Dépôt { char agence; Un total de 52 int n° compte; octets par char client ; enregistrement float solde; Dépôt }; struct Client { Un total de 60 char client; octets char rue; par enregistrement char localité; Client }; un caractère occupe 1 octet (8 bits), un entier occupe 4 octets, un réel en consomme 8. II.1 Enregistrements de longueur fixe Fichier garni avec les enregistrements de Dépôt : Cette structure semble très simple puisque tous les enregistrements de la relation Dépôt et Client auront la même longueur. Problèmes:  l’effacement d'un enregistrement est difficile: il y a le problème de remplacement de l'information avec des enregistrements de longueurs différentes. (ex: Client (60 octets) != Dépôt (52 octets));  un enregistrement peut être à cheval entre deux blocs; ex: si un bloc comporte 512 octets, Pour la relation Dépôt qui comporte 52 octets * 10 enregistrements = 520 octets, le dixième enregistrement sera donc à cheval sur deux blocs. II.1 Enregistrements de longueur fixe Solution 2: 1: Remplacer l'enregistrement Décaler d'un effacé avec le dernier rang tous les enregistrements lors d’un enregistrement. effacement. Comparaison des solutions: La dernière solution est meilleure que la première, mais n'est pas très souhaitable, car les insertions sont généralement plus  nécessite de remuer fréquentes que lesbeaucoup d'enregistreme suppressions.  Il serait préférable de laisser l'emplacement vide disponible pour une insertion ultérieure. MAIS… comment se souvenir des emplacements disponibles??? Nouvelle solution: Une structure avec en-tête de fichier et pointeurs aux enregistrements effacés. II.1 Enregistrements de longueur fixe Fichier avec en-tête et pointeurs À l'insertion, il faut copier l'adresse du 2e vide (enregistrement 4) dans l'en-tête et l'enregistrement à insérer prend la place du premier vide. Ce mécanisme demande une programmation soignée ! Avantages : Insertion ou suppression très facile.  les dimensions des espaces sont connues à l'avance (longueur fixe). II.2 Enregistrements de longueur Variable Ces types d’enregistrements sont très fréquents. Types: des enregistrements à champs variables, des enregistrements à champs répétitifs. Ex: Soit des enregistrements d’une BD bancaire. Une agence peut superviser plusieurs clients. struct Dépôt { char agence ; info-compte est un tableau dont le struct info-compte { nombre Longueur int n°compte; d‘enregistrements variable Longueur fixe char client ; est arbitraire. float solde; struct info-compte *suivant; }; II.2 Enregistrements de longueur Variable Ex: Enregistrement de longueur variable au moyen de chaîne d’enregistrements de longueur fixe. La longueur d'un enregistrement Dépôt n’est limité que par un indicateur de fin d'enregistrement ( ). Inconvénients :  difficulté de réutilisation des espaces effacés; (ex: effacer le client Williams) multiplication des fragments d'espaces disques éparpillés;  augmentation difficile de la taille des enregistrements: il faut alors déplacer tout l'enregistrement II.2 Enregistrements de longueur Variable Deux façons de traiter les enregistrements de longueur variable:  Par espaces réservés: 1. On détermine la longueur maximale de l’enregistrement à longueur variable. 2. À sa création, l’enregistrement est créé à sa longueur maximale. 3. Les espaces non utilisés sont remplis de symboles spéciaux.  Par pointeurs : 1. Dans le fichier, on ajoute un nouveau champ contenant des pointeurs aux enregistrements. 2. À sa création, l'enregistrement de longueur variable est représenté par une liste enregistrements de longueur fixe. 3. Les enregistrements appartenant à une même agence sont chaînés. II.2 Enregistrements de longueur Variable Exemple de fichier organisé suivant la méthode :  Par espaces réservés: Utile lorsque tous les enregistrements environ de la même longueur (ex: tout agences ont approximativement le même nombre de client), … sinon gaspillage de l'espace disq  Par pointeurs : perte d'emplacement mémoire dans tous les enregistrements, sauf les premiers de la chaî II.3 Organisation des enregistrements par blocs Nouvelle solution: Répartition en blocs  bloc d'accrochage: contient les premiers enregistrements des chaînes,  blocs de débordement: contient les autres enregistrements. Tous les enregistrements d'un bloc auront la même longueur bien que ces enregistrements soient de longueur variable. Cette structure est la plus intéressante et la plus utilisée. La lecture et l’écriture des fichiers de données sont effectuées par groupes de blocs de longueur fixe. Les échanges se font entre l'unité centrale et le disque. La dimension d’un bloc varie de 512 octets à plusieurs milliers d'octets; II.3 Organisation des enregistrements par blocs Plusieurs approches permettent d'optimiser la vitesse de transfert entre le disque et la mémoire centrale:  Méthode simple : inscrire les données sur le disque dans l'ordre même où elles seront appelées lors de leur exploitation… mais c'est presque impossible à réaliser;  Approche par l'optimisation des temps d'accès: découpage approprié des données en blocs. Problème: Les accès disque sont le point d'embouteillage permanent de l'exploitation des Enregistrements. Solution: Il faut organiser les accès disque de sorte que la lecture d'un bloc soit optimale en appliquant les deux techniques suivantes: II.3 Organisation des enregistrements par blocs 1. Grouper les enregistrements fortement liés. Un bloc devrait réunir les enregistrements fortement liés : Utilisation des structures à groupage de blocs. 2. Lors d’un débordement d'un bloc, il faut essayer de grouper les blocs qui ont un rapport entre eux par pistes et par cylindres:  III.Taxonomie des structures simples de fichiers En combinant entre l'organisation globale des fichiers (tableau ou liste) et celle interne aux blocs (format fixe ou variable des enregistrements), on peut définir une classe de méthodes d'accès (dites « simples ») pour organiser des données sur disque. Si de plus on prend en compte la possibilité de garder le fichier ordonné ou non, suivant les valeurs d'un champ clé particulier, on doublera le nombre de méthodes dans cette classe de structures simples de fichiers.  Tableau Liste Vue globale Structures simples de fichiers Ordre Sans Ordre Vue microscopique Fixe Variable Chevauchement Sans Chevauchement Structures de fichier simples III. Taxonomie des structures simples de fichiers Utilisons la notation suivante: T : pour fichier vu comme tableau, L : pour fichier vu comme liste O : pour fichier ordonné, O : pour fichier non ordonné F : pour format fixe des enregistrements, V : pour format variable C : avec chevauchement des enregistrements entre blocs, C : sans chevauchement. Les feuilles de l'arbre suivant, représentent les 12 méthodes d'accès simples: III.Taxonomie des structures simples de fichiers Exemple 1 : Par exemple la méthode T O V C représente l'organisation d'un fichier vu comme tableau (T), non ordonné (O), avec des enregistrements de taille variables (V) et acceptant les chevauchements entre blocs (C). La recherche est séquentielle, l'insertion en fin de fichier et la suppression est logique. III.Taxonomie des structures simples de fichiers Exemple 2 : Dans le cas d'un fichier LOF (fichier vu comme liste, ordonné avec enregistrements à taille fixe), chaque bloc pourra contenir par exemple, un tableau d'enregistrements (tab), un entier indiquant le nombre d'enregistrements dans le tableau (nb) et un entier pour garder la trace du bloc suivant dans la liste (suiv) : La recherche est séquentielle, l'insertion provoque des décalages intra-blocs (pour garder l'ordre des enregistrements) et la suppression peut être logique ou physique. III.Taxonomie des structures simples de fichiers Exemple complet: fichier de type « TOF » : (fichier vu comme tableau, ordonné avec enregistrements à taille fixe) La recherche d'un enregistrement est dichotomique (rapide). L'insertion peut provoquer des décalages intra et inter-blocs (coûteuse). La suppression peut être réalisée par des décalages inverses (suppression physique coûteuse) ou alors juste par un indicateur booléen (suppression logique beaucoup plus rapide). Optons pour cette dernière alternative. L'opération du chargement initial consiste à construire un fichier ordonné avec n enregistrements initiaux, en laissant un peut de vide dans chaque bloc. Ce qui permettra de minimiser les décalages pouvant être provoqués par les futures insertions. Avec le temps, le facteur de chargement du fichier (nombre d'insertions / nombre de places disponibles dans le fichier) augmente à cause des insertions futures, de plus les suppressions logiques ne libèrent pas de places. Donc les performances tendent à se dégrader avec le temps. Il est alors conseillé de réorganiser le fichier en procédant à un nouveau chargement initial. C'est Conclusion Le type d’organisation choisi ,le support de stockage utilisé, permettent de déterminer le mode d’ accès aux données stockées Les principaux paramètres à prendre en considération, lors de l'élaboration d'une méthode d'accès sont:  Le temps d'accès des opérations de base (recherche, insertion,...)  Le facteur de chargement (pourcentage de remplissage de l'espace alloué au fichier)  La taille du fichier en MS La taille des structures auxiliaires de la méthode en MC et en MS Le type d'accès: fichier statique – peu ou pas d'insertions/suppressions fichier dynamique – en constante évolution.