II.1 - INTRODUCTION : LA GESTION DES FICHIERS DANS LES SYSTEMES OPERATOIRES.
Avant de traiter des systèmes de gestion de bases de données, nous allons aborder l'étude des systèmes de gestion de fichiers, qui peuvent être vus comme l'outil de gestion de données minimum offert par un système d'exploitation. La plupart du temps, le système de bases de données repose sur un système de fichiers évolués.
Pour aborder l'étude des systèmes de fichiers, il est utile de rappeler la structure d'un calculateur. Le cœur d'un calculateur est le processeur central. Celui-ci est connecté par un bus à une mémoire centrale dans laquelle il puise les instructions qu'il exécute. Les instructions d'entrée-sortie sont généralement sous-traitées à une unité spécifique qui effectue en parallèle les transferts de données depuis la mémoire centrale vers les périphériques (sortie) ou dans l'autre sens (entrée) . La figure II.1 illustre la structure d'un calculateur.
LC : Lecteur de Cartes TE : Terminaux
DM : Disques Magnétiques IM : Imprimante
Figure II.1 - Structure d'un calculateur.
Un calculateur, tel que celui représenté figure II.1 offre d'abord à l'utilisateur un système d'exploitation . Les fonctions essentielles assurées par les systèmes d'exploitation sont (cf. fig. II.2) :
P. AP. : Programme d'Application
G. PR. : Gestion des Programmes
G. FI. : Gestion des Fichiers
G. CO. : Gestion des Communications
G. ES. : Gestion des Entrées - Sorties
G. ME. : Gestion de la Mémoire
G. PU. : Gestion des Processus
D. M. : Disques Magnétiques
L. C. : Lecteur de Cartes
M. D. : Modem
I. M. : Imprimante
L.T : Ligne de Télécommunication
Figure II.2 Composants d'un système d'exploitation
- La Gestion de la Mémoire qui permet le partage de la mémoire entre les programmes ;
- la Gestion des Processus qui permet l'exécution de plusieurs programmes usagers et systèmes simultanément, au moins en apparence ;
- la Gestion des Entrées-Sorties physiques qui assure l'échange de données entre les unités périphériques et l'unité centrale ;
- la Gestion des Communications qui effectue le transport de données vers, où en provenance, d'autres unités ou processus ;
- la Gestion des Programmes usagers qui assure leur transformation en programmes exécutables et le contrôle de leur exécution sous forme de processus ;
- la Gestion des Fichiers qui permet le stockage de données sur mémoires secondaire.
Nous allons dans ce chapitre, étudier plus spécifiquement la gestion des fichiers. Un fichier est un récipient de données identifié par un nom et contenant des données. La gestion des fichiers est une des fonctions essentielles offertes par les systèmes. C'est, en effet, grâce à cette fonction qu'il est possible de traiter et conserver des quantités importantes de données et de partager ces données entre plusieurs programmes. De plus, elle sert, en général, de base aux systèmes de Gestion de Bases de Données que nous allons étudier dans les chapitres suivants. Dans ce chapitre, les objectifs de gestion des fichiers sont introduits. Puis les fonctions accomplies par le noyau d'un gestionnaire de fichiers sont étudiées. Enfin, et c'est l'objet essentiel du chapitre, les principales organisations et méthodes d'accès des fichiers sont présentées.
II.2.- OBJECTIFS DE LA GESTION DES FICHIERS ET NOTIONS DE BASE
II.2.1. - Possibilités d'informatiser la gestion d'une grande entreprise.
Un gestionnaire de fichiers doit permettre le traitement par l'informatique de la gestion d'une entreprise. Les données descriptives des objets gérés par l'entreprise, ainsi que les données spécifiant les traitements appliqués aux objets, doivent pouvoir être stockées dans les mémoires d'un calculateur. Les traitements de ces données peuvent être exécutés par lots, en fin de mois par exemple, ou en fin de semaine…, mais aussi (et c'est en général plus difficile) à l'unité dès que survient un évènement dans le monde réel : on parle alors de traitement transactionnel.
A titre d'illustration, un gestionnaire de fichiers devrait par exemple permettre de traiter l'application comptabilité d'une société de livraison. Cette application est représentée figure II.3. Elle gère les comptes des clients et édite les factures correspondant aux livraisons. Pour calculer les montants à facturer et à déduire des comptes clients, un catalogue des prix est utilisé. Les traitements peuvent être effectués en traitement par lots, en fin de mois ; dans ce cas, les bordereaux de livraisons du mois sont traités ensemble, par exemple à partir d'un fichier de saisie. Le traitement d'une livraison peut être effectué en transactionnel ; dans ce cas, la description de la livraison est tapée en direct sur un terminal et les traitements associés sont immédiatement exécutés.
Figure II.3. - Un exemple d'application.
II.2.2. - Utilisation de disques magnétiques.
L'informatisation de la gestion d'une grande entreprise nécessite le stockage de volumes de données importants, par exemple quelques centaines de millions voire plusieurs milliards d'octets . Il n'est pas possible de stocker de tels volumes de données en mémoires centrale. On est par la suite conduit à introduire des mémoires secondaires.
Notion II.1 : Mémoire secondaire (External Storage)
Mémoire non directement adressable par les instructions du processeur central, mais par des instructions d'Entrées-Sortie spécialisées et dont les temps d'accès sont très supérieurs à ceux de la mémoire centrale.
Un cas particulier de mémoire secondaire est le disque magnétique (IBM78). La capacité des disques s'est accrue depuis les années 1955 pour atteindre quelques 100 millions voire quelques milliard d'octets aujourd'hui. Les temps d'accès se sont également améliorés pour avoisiner aujourd'hui 25 ms en moyenne. Noter qu'ils sont environ 20 000 fois plus élevés que ceux des mémoires centrales.
Pour traiter correctement de grandes applications, il est nécessaire de disposer d'une capacité infinie de mémoire secondaire. Dans ce but, on utilise des piles de disques amovibles appelés volumes.
Notion II.2 : Volume (Disk Pack).
Unité de mémoire secondaire amovible.
Un volume disque est monté sur un tourne-disque. Un contrôleur de disque contrôle en général plusieurs tourne-disques. Les volumes sont montés et démontés par les opérateurs, en général sur un ordre du système. La notion de volume s'applique également aux bandes magnétiques où un volume est une bande. Une unité peut alors comporter un ou plusieurs dérouleurs.
Un volume ainsi que l'équipement de lecture-écriture associé à un tourne-disques est représenté figure II.4. Un volume se compose de p disques (par exemple 9), ce qui correspond à 2p-2 surfaces magnétisées car les deux faces externes ne le sont pas. Les disques à têtes mobiles comportent une tête de lecture-écriture par surface. Cette tête est accrochée à un bras qui se déplace horizontalement de manière à couvrir toute la surface du disque. Un disque est divisé en piste concentriques numérotés de 0 à n (par exemple n = 512). Les bras permettant de lire/écrire les pistes d'un volume sont solidaires ce qui force leur déplacement simultané. Les disques tournent continuement à une vitesse de quelques dizaines de tours par seconde. L'ensemble des pistes, décrit quand les bras sont positionnés, est appelé cylindre. Il existe également des diques à têtes fixes qui comportent une tête de lecture/écriture par piste.
Chaque piste d'un disque supporte plusieurs enregistrements physiques appelés secteurs, de tailles constantes ou variables selon le type de disque. Le temps d'accès à un secteur est une des caractéristiques essentielles des disques. Il se compose :
- du temps nécessaire au mouvement de bras pour sélectionner le bon cylindre (quelques milisecondes à des dizaines de millisecondes selon l'amplititude du déplacement du bras et le type de disque) ;
- du temps de rotation du disque nécessaire pour que l'enregistrement physique désiré passe devant les têtes de lectures/écritures ; ce temps est appelée temps de latence ; il est de quelques millisecondes, selon la position de l'enregistrement par rapport aux têtes et selon la vitesse de rotation des disques.
Figure II.4. - Volume amovible à têtes mobiles et équipement de lecture/écriture.
Au total, les disques ont un temps d'accès variable selon la distance qui sépare l'enregistrement à accéder de la position des têtes de lecture/écriture. La tendance aujourd'hui est de réduire cette variance avec des moteurs à accélération constante pour commander les mouvements de bras, et avec des quantités d'informations enregistrés par cylindres de plus en plus importantes.
II.2.3. - Indépendance entre les programmes d'applications et les mémoires secondaires.
Les disques magnétiques et plus généralement les mémoires secondaires doivent bien sûr pouvoir être utilisés par plusieurs programmes d'applications. En conséquence, il faut pouvoir partager l'espace mémoire secondaire entre les données des diverses applications. Une gestion de cet espace est nécessaire. Les adresses utilisées directement par les programmes doivent être indépendants de l'emplacement des données sur disques.
D'un autre coté, les progrès technologiques ne cessent d'améliorer le rapport performance/prix des mémoires secondaires. La densité des disques magnétiques (nombre de bits enregistré/cm2) double approximativement tous les deux ans, ce qui permet d'accroître les capacités de stockage et les performances. Un bon système doit permettre aux utilisateurs de profiter des avancées technologiques, par exemple en achetant des disques plus performants, et ceci, sans avoir à modifier les programmes. En effet, la reprogrammation coûte très cher en moyens humains. En résumé, il est possible de définir simplement l'indépendance des programmes d'applications par rapport aux mémoires secondaires comme suit.
Notion II.3. : Indépendace entre les programmes et les mémoires sécondaires (Program-Storage device independance).
Possibilité de changer les données de mémoire secondaire sans changer les programmes.
Afin de réaliser cette indépendance, on introduit des objets intermédiaires entre les programmes d'applications et la mémoire secondaire appelés fichiers.
Notion II.4. : Fichier(File)
Récipient d'informations constituant une mémoire secondaire idéale caractérisé par un nom permettant d'écrire des programmes d'applications indépendants des mémoires secondaires.
Ainsi, les programmes d'applications ne connaissent pas les mémoires secondaires mais les fichiers qui peuvent être implantés sur diverses mémoires.
Un programme d'application ne manipule pas globalement un fichier mais lit/écrit et traite des portions successives, correspondant en général à un objet du monde réel, par exemple un client, un compte, une facture. Une telle portion est appelée article.
Notion II.5. : Article (Record)
Elément composant d'un fichier correspondant à l'unité de traitement par les programmes d'applications.
Les articles sont reliés entre eux pour composer un fichier. Les structures des liaisons constituent l'organisation du fichier.
Notion II.6. : Organisation de fichier (File organization)
Nature des liaisons entre articles pour composer un fichier.
Les programmes d'applications peuvent choisir les articles dans un fichier de différentes manières, par exemple l'un après l'autre à partir du premier, ou en attribuant un nom à chaque article, selon la méthode d'accès choisie.
Notion II.7. : Méthode d'accès (Acces Method)
Méthode d'exploitation du fichier utilisée par les programmes d'applications pour sélectionner des articles.
Ces différentes notions vont permettre de réaliser l'indépendance désirée entre mémoire secondaires et programmes d'applications.
II.2.4. - Utilisation de langages hôtes.
Le système de gestion de fichiers doit être utilisable par un programme dont le code objet résulte d'une compilation d'un langage de haut niveau (COBOL, PL/1, PASCAL,…). De plus, il doit être possible d'utiliser les fichiers dans le langage choisi d'une manière aussi intégrée que possible, par exemple en décrivant les données du fichier comme des types dans le langage. On appelle langage hôte le langage de programmation qui intègre les verbes de manipulation de fichiers.
Notion II.8. : Langage hôte(Host language)
Langage de programmation accueillant les verbes de manipulation de fichiers et la définition des données des fichiers.
Il est utile de rappeler le cheminement d'un programme en machine. Celui-ci est donc écrit à l'aide d'un langage de programmation hôte et de verbes de manipulation de fichiers. Il est pris en charge par le compilateur du langage. Ce dernier génère du code machine translatable incluant des appels au système, en particulier au gestionnaire de fichiers. Le chargeur-éditeur de liens doit ensuite amener en bonne place en mémoire les différents modules composants du programme, en particulier, les translations d'adresse doivent être effectuées à ce niveau. On obtient alors du code exécutable. La figure II.5 illustre ces étapes.
Figure II.5. -Cheminement d'un programme
II.2.5. - Possibilités d'accès séquentiel et sélectif.
Afin de caractériser le comportement des programmes d'applications vis-à-vis des fichiers, il est possible d'utiliser deux mesures. Le taux de consultation (TC) est le quotient du nombre d'articles utilement lus par un programme sur le nombre d'articles total du fichier. Le taux de mouvements (TM) est le quotient du nombre d'articles modifiés par un programme sur le nombre d'articles total du fichier. On est ainsi conduit à introduire deux types de méthodes d'accès.
Notion II.9. : Méthode d'accès séquentielles (Sequential Acces Method).
Méthode d'accès consistant à lire successivement tous les articles d'un fichier, depuis le premier jusqu'au dernier désiré
Une telle méthode est adaptée dans le cas ou TC ou TC+TM sont de l'ordre de 1. Elle sera essentiellement utilisée en traitement par lots.
Notion II.10. : Méthodes d'accès sélectives (Key acces methods).
Ensemble de méthodes d'accès permettant de lire/écrire tout article au moyen de quelques accès disques (moins de 5, idéalement 1), y compris pour de très gros fichiers.
De telles méthodes seront utilisées quand TC, ou TC+TM pour un programme modifiant, sera petit. Elles sont donc particulièrement adaptées au transactionnel.
Un gestionnaire de fichiers doit à la fois supporter des méthodes d'accès séquentielles et sélectives, ceci afin de permettre à la fois les traitements par lots et le travail en transactionnel.
Afin de mettre en oeuvre une méthode d'accès sélective, il faut bien sûr pouvoir identifier de manière unique un article. Alors, une méthode d'accès sélective permet à partir de l'identifiant d'un article de déterminer l'adresse d'un article (adresse début) et de lire l'article en moins de 5 E/S. L'identifiant d'un article est appelé clé (que l'on qualifie parfois de primaire).
Notion II.11. : Clé d'article (Record Key)
Identifiant d'un article permettant de sélectionner un article unique dans un fichier.
La clé peut ou non figurer comme une donnée de l'article.
Exemple : ETUDIANT (N°, Nom, Prénom, Ville, date d'inscription, résultats) est un fichier dont chaque article contient les données écrites entre parenthèses. La clé est N° ; c'est une donnée de l'article. A partir de cette clé, c'est-à-dire d'un N° d'étudiant, une méthode d'accès sélective doit permettre de déterminer l'adresse de l'article dans le fichier.
Comme déjà dit, il existe différents types d'organisations sélectives (et méthodes d'accès associées). Nous allons ci-dessous étudier les principales. Elles peuvent être divisées en deux classes :
- Les méthodes d'accès par hachage utilisent des fonctions de calcul pour déterminer l'adresse d'un article dans un fichier à partir de sa clé ;
- Les méthodes d'accès par index utilisent des tables généralement stockées sur disques pour mémoriser l'association clé article-adresse article.
Nous étudierons ci-dessous ces deux types de méthodes d'accès.
II.2.6 - Possibilité d'utilisateurs multiples.
Dans les machines modernes, l'éxécution d'une instruction d'entrée-sortie ne bloque pas le processeur central : celui-ci peut continuer à exécuter des instructions machines en parallèle à l'exécution de l'entrée-sortie. Afin d'utiliser ces possibilités, le système exécute plusieurs programmes usagers simultanément, ce qui conduit à une simultanéité inter-usagers.
Notion II.12. : Simultanéité inter-usagers (Inter-user parallelism)
Type de simultanéité consistant à exécuter un programme d'application en processeur central pendant qu'un autre programme effectue des entrées-sorties.
Un bon système de fichiers doit permettre le partage des fichiers par différents programmes d'applications sans que ceux-ci s'en aperçoivent. Le partage peut être simultané, mais aussi plus simplement réparti dans le temps. Nous étudierons plus en détails les problèmes de partage dans le contexte des bases de données où ils se posent avec plus d'acuité.
II.2.7. - Sécurité et protection des fichiers
L'objectif sécurité des fichiers contre les accès mal intentionnés, ou plus simplement non autorisés, découle directement du besoin de partager les fichiers. En effet, lorsque les fichiers sont partagés, le propriétaire désire contrôler les accès, les autoriser à certains, les interdire à d'autres. C'est là une des fonctions que doit rendre un bon service de gestion de fichiers. Ces mécanismes sont généralement réalisés à l'aide de noms composés et de clés de protection associés à chaque fichier, voire à chaque article ; l'usager doit fournir ces noms et ces clés pour accéder au fichier ou à l'article. Nous étudierons les solutions dans le cadre des bases de données où le problème devient plus aigu.
Le gestionnaire de fichiers doit aussi garantir la conservation des fichiers en cas de panne du matériel ou du logiciel. En conséquence, il doit être prévu de pouvoir repartir après panne avec des fichiers corrects. On considère en général deux types de pannes : les pannes simples avec seulement perte du contenu de la mémoire secondaire peut être détruit. Ainsi, il est nécessaire d'incorporer des procédures de reprise après pannes simples et catastrophiques. Nous étudierons ces procédures dans le cadre des bases de données où elles sont généralement plus complètes.
II.3. - STRUCTURES ET FONCTIONS D'UN GESTIONNAIRE DE FICHIERS
II.3.1. Structure d'un gestionnaire de fichiers.
Un gestionnaire de fichiers est généralement structuré autour d'un noyau qui assure les fonctions de base, à savoir la création/destruction des fichiers, l'allocation de la mémoire secondaire, la localisation et la recherche des fichiers sur les volumes, la gestion des zones de mémoires intermédiaires appelées tampons. Les méthodes d'accès sont des modules spécifiques qui constituent une couche plus externe et qui utilisent les fonctions du noyau. La figure II.6 représente les différents modules d'un gestionnaire de fichiers typiques.
Figure II.6. - Organisation d'un gestionnaire de fichiers.
- Le noyau d'un gestionnaire de fichiers accède en général aux mémoires secondaires par l'intermédiaire du gestionnaire d'entrées-sorties. Celui-ci, qui n'appartient pas à proprement parler au système de fichiers, gère les entrées-sorties physiques : il permet la lecture et l'écriture de blocs physiques de données sur tous les périphériques, gère les particularités de chacun, ainsi que les files d'attentes d'entrées-sorties.
- Chaque module méthode d'accès est à la fois chargé de l'organisation des articles dans le fichier et de la recherche des articles à partir d'un identifiant. Un bon système de fichiers doit offrir une grande variété de méthodes d'accès.
II.3.2. - Fonctions du noyau d'un gestionnaire de fichiers
II.3.2.1. - Manipulation des fichiers
Le programmeur travaillant au niveau du langage machine, ainsi que les modules méthodes d'accès, accèdent au noyau du gestionnaire de fichiers à l'aide d'un ensemble d'instructions de manipulation de fichiers. Tout d'abord, deux instructions perlettent de créer et détruire un fichier. Puis, de lire ou écrire des données dans un fichier, il faut contrôler son identité ainsi qu'ouvrir un chemin pour les données entre le programme effectuant les lectures-écritures et la mémoire secondaire. Ceci est généralement effectué par une instruction d'ouverture : ouvrir. L'opération inverse est exécutée lorsque le programme se désintéresse du fichier par une instruction de fermeture : fermer .
II.3.2.2. - Adressage relatif
Un fichier étant généralement discontinu sur mémoire secondaire, il est utile de pouvoir adresser son contenu à l'aide d'une adresse continue de 0 à n appelée adresse relative . Cela présente l'intérêt de disposer d'un repérage indépendant de la localisation du fichier sur mémoire secondaire (en cas de recopie du fichier, l'adresse relative ne change pas) et de pouvoir assurer que l'on travaille bien à l'intérieur d'un fichier sans risque d'atteindre un autre fichier (il suffit de contrôler que l'adresse relative ne dépasse pas la taille du fichier).
Notion II.13. : Adresse relative(Relative address)
Numéro d'unité d'adressage dans un fichier (autrement dit : déplacement par rapport au début du fichier)
Pour réaliser l'adressage relatif, on divise généralement le fichier en page (on trouve également selon les constructeurs les termes de bloc, groupe, paquet, intervalle, bucket) : une adresse relative octet se compose alors d'un numéro de page suivi d'un numéro d'octet dans la page. Pour éviter un nombre trop important d'entrées-sorties, la taille de la page est généralement un nombre entier d'enregistrements physiques et des tampons d'une page sont utilisés. La taille de la page, fixée dans le système ou lors de la création du fichier, est le plus souvent de l'ordre de quelques K octets. Elle dépend parfois de l'organisation du fichier. Ainsi, le premier niveau de logiciel composant un service de gestion de fichiers offre généralement la possibilité d'accéder à une ou plusieurs pages d'adresse relative (numéro de page) donnée dans un fichier. Il se compose essentiellement d'algorithmes d'allocation de mémoire secondaires et de conversion d'adresse relative page en adresse réelle de l'enregistrement physique, et réciproquement. Finalement, il permet de banaliser toutes les mémoires secondaires, avec quelques restrictions cependant : il est, par exemple, interdit d'accéder autrement qu'en séquentiel à une bande magnétique.
Les articles de l'usager sont alors implantés dans les pages par les méthodes d'accès selon l'organisation choisie. Si plusieurs articles sont implantés dans une même page, on dit qu'il y a blocage. Dans le cas où les articles sont implantés consécutivement sans trou à la suite les uns des autres, on dit qu'il y a compactage : aucune place n'est alors perdue sur la mémoire secondaire, mais des articles peuvent être à cheval sur plusieurs pages.
II.3.2.3. - Allocation de la place sur mémoires secondaires
La taille d'un fichier est fixée soit de manière statique lors de sa création, soit de manière dynamique au fur et à mesure des besoins. Des solutions intermédiaires sont possibles avec une taille initiale extensible par paliers. Dans tous les cas, il est nécessaire de réserver des zones de mémoires secondaires continues pour le fichier. Ces zones sont appelées régions.
Notion II.14. : Région (Allocation area)
Ensemble de zones de mémoires secondaires (pistes) adjacentes allouées en une seule fois à un fichier.
Comme les fichiers vivent et sont de tailles différentes, les régions allouées à un fichier ne sont généralement pas contiguës sur une mémoire secondaire. Le gestionnaire de fichiers doit pouvoir retrouver les régions composant un fichier. Pour cela il peut, soit garder la liste des régions allouées à un fichier dans une table, soit les chaîner, c'est-à-dire mettre dans une entrée d'une table correspondant à chaque région l'adresse de la région suivante.
La taille d'une région peut varier à partir d'un seuil minimal appelé granule (par exemple une piste, etc …).
Notion II.15. : Granule d'allocation(Allocation granule)
Unité de mémoire secondaire allouable à un fichier.
Lorsqu'un fichier est détruit ou rétréci, les régions qui lui étaient allouées (ou partie) sont libérées. Nous allons étudier plus en détails ci-dessous quelques algorithmes d'allocation des régions aux fichiers.
II.3.2.4. - Localisation des fichiers sur les volumes
Il est nécessaire de pouvoir identifier un volume. En effet, lorsqu'un volume n'est pas actif il est en général rangé en armoire. Il faut donc une intervention manuelle pour montrer/démonter un volume sur un tourne-disque. Cette opération est exécutée par un opérateur. Celui-ci reconnaît un volume grâce à un numéro (ou nom) attribué à chaque volume. Pour pouvoir contrôler les opérateurs lors des montages/démontages de volume et éviter les erreurs ce numéro est écrit sur le volume.
Notion II.16. : Label de volume(Label)
Premier secteur d'un volume permettant d'identifier ce volume et contenant en particulier son numéro.
Lorsqu'on a retrouvé et monté le volume supportant un fichier, il faut retrouver le fichier sur le volume. Pour cela, chaque fichier possède un ensemble d'informations descriptives (nom, adresse, début, …) regroupées dans un descripteur du fichier.
Notion II.17. : Descripteur de fichier (Directory entry)
Ensemble des informations permettant de retrouver les caractéristiques d'un fichier, contenant en particulier le nom du fichier, sa localisation sur disques …
Il est important que l'ensemble des descripteurs de fichiers contenu sur un volume définisse tous les fichiers d'un volume. On obtient ainsi des volumes auto-documentés, donc portables d'une installation à une autre. Pour cela, les descripteurs de fichiers d'un volume sont regroupés dans une table des matières du volume appelée catalogue.
Notion II.18. : Catalogue(Directory)
Table (ou fichier) située sur un volume et contenant les descripteurs des fichiers du volume.
Le catalogue est, soit localisé en un point conventionnel du volume (par exemple, à partir du secteur1), soit écrit dans un fichier spécial de nom standard. Le descripteur de ce premier fichier peut alors être contenu dans le label du volume. En résumé, la figure II.7 illustre l'organisation des informations étudiées jusqu'à présent sur un volume.
Figure II.7. -Schéma représentant l'organisation d'un volume.
II.3.2.5. - Classification des fichiers en hiérarchie.
Quand le nombre de fichiers d'une installation devient élevé, on est conduit à classer les descripteurs de fichiers dans plusieurs catalogues, par exemple un par usager. Les descripteurs des fichiers catalogues peuvent alors être maintenus dans un catalogue de niveau plus élevé. On aboutit ainsi à des catalogues hiérarchisés qui sont implantés dans de nombreux systèmes. [Daley65].
Notion II.19. : Catalogue hiérarchisé (Hierarchical directory)
Catalogue constitué d'une hiérarchie de fichiers, chaque fichier contenant les descripteurs des fichiers immédiatement inférieurs dans la hiérarchie.
Dans un système à catalogues hiérarchisés, chaque niveau de catalogue est généralement spécialisé. Par exemple, le niveau 1 contient un descripteur de fichier catalogue par usager. Pour chaque usager, le niveau 2 peut contenir un descripteur de fichier par application. Enfin, pour chaque couple <usager-application> le niveau 3 peut contenir la liste des descripteurs de fichiers de données. La figure II.8 illustre un exemple de catalogue hiéarchisé. Le descripteur du catalogue de niveau 1 est appelé racine.
La présence de catalogue hiérarchisé conduit à introduire des noms de fichiers composés. Pour atteindre le descripteur d'un fichier, il faut en effet indiquer le nom du chemin qui mène à ce descripteur. Des noms de fichiers possibles sont par exemple, avec le catalogue représenté figure II.8 :
> PIERRE
> PIERRE > BASES-DE-DONNEES
> PIERRE > BASES-DE-DONNES > MODELES
Afin d'éviter un cloisonnement trop strict des fichiers, les systèmes à catalogues hiérarchisés permettent en général l'introduction de liens. Un lien est simplement un descripteur qui contient un pointeur logique sur un autre descripteur, éventuellement dans une autre branche de la hiérarchie . Par exemple, le descripteur de nom :
> LIONEL > BASES-DE-DONNEES > LANGAGES
pourra être un descripteur de type lien indiquant qu'il est un synonyme du descripteur :
> PIERRE > BASES-DE-DONNEES > LANGAGES. Les noms d'usagers étant généralement fournis par le système, des descripteurs de type lien permettent le partage des fichiers entre usagers.
Pour simplifier la nomination des fichiers, les systèmes à catalogue hiérarchisés gèrent bien souvent la notion de catalogue de base, encore appelé catalogue courant. Lors du début de session (login), le système positionne le catalogue courant par exemple sur les applications de l'usager. Celui-ci peut alors se déplacer par rapport à ce catalogue courant. Par exemple, Pierre passera au catalogue bases-de-données par le nom :
> Bases-de-données
Celui-ci deviendra alors son catalogue courant.
L'accès au fichier se fera alors par le nom :
> Modèles
Le retour au catalogue courant initial s'effectuera par :
>Bases de données< Pierre.
Figure II.8. - Exemple de catalogue hiérarchisé.
II.3.2.6. - Contrôle des fichiers.
Le noyau d'un gestionnaire de fichiers inclut également des fonctions de contrôle des fichiers : partage des fichiers, résistances aux pannes, sécurité et confidentialité des données. Nous n'étudions pas ici ces problèmes qui font l'objet de nombreux développements dans le contexte des bases de données, et donc dans les chapitres suivants.
II.3.3 - Stratégie d'allocation de la mémoire secondaire
II.3.3.1. Objectifs d'une stratégie.
Il existe différentes stratégies d'allocation de la mémoire secondaire aux fichiers. Une bonne stratégie doit chercher :
(1) à minimiser le nombre de régions à allouer à un fichier de sorte à réduire d'une part les déplacements des bras des disques lors des lectures en séquentiel et d'autre part le nombre de descripteurs de région associés à un fichier ;
(2) à minimiser la distance qui sépare les régions successives d'un fichier de sorte à réduire les déplacements de bras en amplitude.
Les stratégies peuvent être plus ou moins complexes. La classe la plus simple de stratégies alloue des régions de taille fixe égale à un granule, si bien que les notions de granule et région sont confondues. Un classe plus performante alloue des régions de tailles variables, composées de plusieurs granules successifs. Nous allons approfondir ces deux classes ci-dessous.
Auparavant, il est nécessaire de dire que toutes les méthodes conservent une table des granules alloués à aucun fichier, c'est-à-dire une table des granules libres ; une copie de cette table doit être stockée sur disque pour des raisons de fiabilité. La table elle-même peut être organisée selon différentes méthodes :
- Liste des granules ou régions libres, ordonnée ou non ; l'allocation d'une région consiste alors à enlever la région choisie de cette liste pour l'associer au descripteur du fichier ;
- Table de bits dans laquelle chaque bit correspond à un granule ; l'allocation d'un granule consiste alors à trouver un bit à 0, le positionner à 1 et à adjoindre l'adresse du granule alloué au descripteur du fichier.
II.3.3.2. -Stratégie par granule (à région fixe).
Ces stratégies confondent donc les notions de région et de granule. Elles sont simples et généralement implantées sur les petits systèmes. On peut distinguer :
• La stratégie du premier trouvé : le granule correspondant à la tête de liste de la liste des granules libres, ou au premier bit à 0 dans la table des granules libres, est choisie ;
• La stratégie du meilleur choix : le granule le plus proche (du point de vue déplacement de bras) du dernier granule alloué au fichier est retenu.
II.3.3.3. - Stratégie par région (à région variables).
Ces stratégies permettent d'allouer des régions composées de plusieurs granules consécutifs, selon les besoins des fichiers. Le noyau du gestionnaire de fichiers reçoit alors des demandes d'allocation/libération de régions de tailles variables. Dans le cas ou aucune région de la taille demandée ne peut être constituée par des granules consécutifs la demande peut éventuellement être satisfaite par plusieurs régions. Parmi les stratégies par région, on peut distinguer :
• La stratégie du plus proche choix : Dans cette stratégie deux régions libres consécutives sont fusionnées en une seule. Lors d'une demande d'allocation, la liste des régions libres est parcourue jusqu'à trouver une région de la taille demandée ; dans le cas où aucune région de la taille demandée n'est libre, la première région de taille supérieure est découpée en une région de la taille cherchée qui est allouée au fichier et une nouvelle région libre correspondant au reste.
• La stratégie des frères siamois : Cette stratégie offre la possibilité d'allouer des régions de 1, 2, 4, 8…2K granules. Des listes séparées sont maintenues pour les régions libres de dimensions 20, 21, … 2K granules. Lors d'une demande d'allocation, une région libre peut être extraite de la liste des régions libres de taille 2i+1 pour constituer deux régions libres de taille 2i. Lors d'une libération deux régions libres consécutives (deux siamoises) de taille 2i sont fusionnées afin de constituer une région libre de taille 2i+1. L'algorithme de recherche d'une région libre de taille 2i consiste à chercher cette région dans la liste des régions de taille 2i. Si cette liste est vide, on recherche alors une région de taille 2i+1 que l'on divise en deux. S'il n'y en a pas, on passe alors au niveau suivant 2i+2, etc… jusqu'à atteindre le niveau k ; c'est seulement dans le cas où les listes 2i à 2K sont vides que l'on ne peut satisfaire la demande par une seule région. Cet algorithme qui est emprunté aux mécanismes d'allocation de segments dans les systèmes pagés [LISTER79] est sans doute le plus efficace ; il est aussi très bien adapté à certaines méthodes d'accès.
En résumé, les stratégies par région de tailles variables sont en général plus efficace du point de vue déplacement de bras et taille de la table des régions d'un fichier. Un problème commun à ces stratégies peut cependant survenir après des découpages trop nombreux s'il n'existe plus de régions de taille supérieure à un granule. Dans ce cas, l'espace disque doit être réorganisé (garbage collection). Ce dernier point fait que les stratégies par granules restent les plus utilisées.
II.4 - ORGANISATIONS ET METHODES D'ACCES PAR HACHAGE
Les organisations et méthodes d'accès par hachage sont basées sur l'utilisation d'une fonction de calcul qui, appliquée à la clé, détermine l'adresse relative d'une zone appelée paquet (Bucket en anglais) dans laquelle est placé l'article. On distingue les méthodes d'accès par hachage statique, dans lesquelles la taille du fichier est fixe, des méthodes par hachage dynamique, où le fichier peut grandir.
II.4.1. - Organisation hachée statique
C'est la méthode la plus ancienne et la plus simple. Le fichier est de taille constante fixée lors de sa création. Une fois pour toute, il est divisé en p paquets de taille fixe L. La clé permet de déterminer un numéro de paquet N dont l'adresse relative est alors obtenue par la formule :
AR = N * L.
Nous introduirons donc la notion de fichier haché statique comme suit.
Notion II.20. : Fichier haché statique (Static hashed file)
Fichier de taille fixe dans lequel les articles sont placés dans des paquets dont l'adresse est calculée à l'aide d'une fonction de hachage fixe appliquée à la clé.
A l'intérieur d'un paquet, les articles sont rangés à la suite dans l'ordre d'arrivée. Ils sont retrouvés grâce à la donnée contenant la clé. La figure II.9 illustre un exemple de structure interne d'un paquet.
Lorsqu'un nouvel article est inséré dans un fichier, il est logé à la première place libre dans le paquet. S'il n'y a pas de place libre, on dit qu'il y a débordement. Il faut évidemment contrôler l'unicité de la clé d'un article lors des insertions.
A l'intérieur d'un tel paquet, un article est accédé par balayage séquentiel. Des structures de paquet plus sophistiquées permettent l'accès direct à un article de clé donnée à l'intérieur d'un paquet.
Figure II.9. - Structure interne d'un paquet.
A partir de la clé d'un article, on calcule le numéro de paquet dans lequel l'article est placé à l'aide d'une fonction appelée fonction de hachage (Fig. II.10). Une fonction de hachage doit être choisie de sorte à distribuer uniformément les articles dans les paquets. Plusieurs techniques sont possibles :
- le pliage consiste à choisir et combiner des bits de la clé (par exemple par ou exclusif) ;
- les conversions de la clé en nombre entier ou flottant avec utilisation de la mantisse permettant d'obtenir également un numéro de paquet ;
- le modulo est sans doute la fonction la plus utilisée ; il consiste à prendre pour numéro de paquet le reste de la division de la clé par le nombre de paquets.
Ces techniques peuvent avantageusement être combinées.
Figure II.10. - Illustration d'un fichier haché statique.
A titre d'exemple, soit un fichier de 47 paquets et des articles de clé numérique. Le modulo 47 pourra alors être choisi comme fonction de hachage. Ainsi, l'article de clé 100 sera placé dans le paquet 6, l'article de clé 47 dans le paquet 0, celui de clé 123 dans le paquet29, etc …
Le problème de débordement se pose lorsqu'un paquet est plein. Une première solution simple consiste à ne pas gérer de débordements et à répondre fichier saturé à l'utilisateur. Ceci implique une mauvaise utilisation de la place occupée par le fichier, surtout si la distribution des articles dans les paquets est mauvaise. Des solutions plus satisfaisantes consistent à utiliser une technique de débordement parmi l'une des suivantes [KNUTH73] :
- l'adressage ouvert consiste à placer l'article qui devrait aller dans un paquet plein dans le premier paquet suivant ayant de la place libre ; il faut alors mémoriser tous les paquets dans lequel un paquet plein a débordé ;
- le chaînage consiste à constituer un paquet logique par chaînage d'un paquet de débordement à un paquet plein ;
- le rehachage consiste à appliquer une deuxième fonction de hachage lorsqu'un paquet est plein ; cette deuxième fonction conduit généralement à placer les articles dans des paquets de débordements.
Dans tous les cas la gestion de débordements dégrade les performances et complique la gestion des fichiers hachées.
La méthode d'accès basée sur l'organisation hachée statique a plusieurs avantages. En particulier, elle s'adapte à des fichiers de clés quelconques, reste simple et donne d'excellentes performances tant qu'il n'y a pas de débordements : une lecture d'articles s'effectue en une entrée-sortie (lecture du paquet) alors qu'une écriture en nécessite en général deux (lecture puis réécriture du paquet). Cependant, les débordements dégradent rapidement les performances. De plus, le taux d'occupation de la mémoire secondaire réellement utilisé peut rester assez éloigné de 1. Enfin, la taille d'un fichier doit être fixée a priori. Si le nombre d'articles d'un fichier devient plus important que prévu, le fichier doit être réorganisé.
II.4.2. - Organisation hachées dynamiques
II.4.2.1. - Principes du hachage dynamique.
La première organisation hachée dynamique a été proposée pour des tables en mémoire [KNOTT71]. Puis plusieurs techniques basées sur le même principe mais différentes ont été proposées pour étendre les possibilités du hachage à des fichiers dynamiques [FAGIN79, LARSON78, LITWIN78, LARSON80, LITWIN80, VALDURIEZ & VIEMONT 84]. Le principe de base de ces différentes techniques est la digitalisation progressive de la fonction de hachage : la chaîne de bits résultat de l'application de la fonction de hachage à la clé est exploitée progressivement bit par bit au fur et à mesure des extensions du fichier.
De manière plus précise, les méthodes dynamiques utilisent une fonction de hachage de la clé h(K) générant une chaîne de N bits, où N est grand (par exemple 32). La fonction est choisie de telle sorte qu'un bit quelconque de h(K) a la même probabilité d'être à 1 ou à 0. Lors de la première implantation du fichier haché, seulement les M premiers bits de h(K) (avec M petit devant N) sont utilisés pour calculer le numéro de paquet dans lequel placer un article. Ensuite, lorsque le fichier est considéré comme saturé (par exemple lorsqu'un premier paquet est plein), une partie du fichier (par exemple le paquet plein) est doublée : une nouvelle région est allouée pour cette partie et les articles de l'ancienne partie sont distribués entre l'ancienne partie et la nouvelle en utilisant le bit M+1 de la fonction de hachage. Ce processus d'éclatement est appliqué chaque fois que le fichier est saturé, de manière récursive. Ainsi les bits (M+1), (M+2), (M+3), … de la fonction de hachage sont successivement utilisés et le fichier peut grandir jusqu'à 2**N paquets. Une telle taille est suffisante pour les plus gros fichiers rencontrés en gestion.
Les méthodes de hachage dynamique différent par les réponses qu'elles apportent aux questions suivantes :
(1) Quel est le critère retenu pour décider qu'un fichier haché est saturé?
(2) Quelles partie du fichier faut-il doubler quand un fichier est saturé?
(3) Comment retrouver les parties d'un fichier qui ont été doublées et combien de fois ont-elles été doublées?
(4) Faut-il conserver une méthode de débordement et si oui quelle méthode?
Nous présentons ci-dessous deux méthodes qui nous paraissent des plus intéressantes : le hachage extensible [FAGIN79] et le hachage linéaire [LITWIN80]. Le lecteur pourra trouver des méthodes sans doute plus élaborées dans [LARSON80], [LOMET83] ainsi que des évaluations du hachage extensible dans [SCHOLL81] et du hachage linéaire dans [LARSON82].
II.4.2.2. - Le hachage extensible.
Le hachage extensible [FAGIN79] apporte les réponses suivantes aux questions précédentes :
(Q1) Le fichier est étendu dès qu'un paquet est plein ; dans ce cas un nouveau paquet est ajouté au fichier.
(Q2) Seul le paquet saturé est doublé lors d'une extension du fichier.
(Q3) La fonction de hachage adresse un répertoire des adresses de paquets ; la taille du répertoire est 2**(M+P) où P est le niveau du paquet qui a doublé le plus grand nombre de fois ; chaque entrée du répertoire donne l'adresse d'un paquet ; les 2**(P-Q) adresses correspondant à un paquet qui a éclaté Q fois sont identiques et pointent sur ce paquet ; ainsi, par l'indirection du répertoire, le système retrouve les paquets. De plus, en tête de chaque paquet est mémorisé le nombre de bits de la fonction de hachage à utiliser pour ce paquet.
(Q4) La gestion de débordement n'est pas nécessaire.
En résumé, une méthode de hachage extensible peut être définie comme suit.
Notion II.21. : Hachage extensible (Extended hashing)
Méthode de hachage dynamique consistant à éclater un paquet plein et à mémoriser l'adresse des paquets dans un répertoire accédé directement par les (M+P) premiers bits de la fonction de hachage où P est le nombre d'éclatements maximum subit par les paquets.
Un fichier haché extensible est donc structuré en deux niveaux : le répertoire et les paquets. le répertoire contient une entête qui indique la valeur de M+P, le nombre de bits de la fonction de hachage utilisés pour le paquet ayant le plus éclaté. Après l'entête figurent des pointeurs vers les paquets. Le premier pointeur correspond à la valeur 0 des (M+P) premiers bits de la fonction de hachage, alors que le dernier correspond à la valeur 2**(M+P)-1, c'est-à-dire aux (M+P) premiers bits à 1. Chaque paquet contient une entête qui indique la valeur de (M+Q) où Q est le niveau d'éclatement du paquet ; à chaque paquet sont associés 2**(P-Q) pointeurs consécutifs dans le répertoire qui indiquent son adresse. Cette organisation est illustrée figure II.11 [FAGIN79].
Figure II.11. - Répertoire et paquets d'un fichier haché extensible.
L'insertion d'un article dans un fichier haché extensible nécessite tout d'abord l'accès au répertoire. Pour cela, les (M+P) bits de la clé sont utilisés. L'adresse du paquet dans lequel l'article doit être placé est ainsi lue dans l'entrée adressée du répertoire. Si le paquet est plein, alors celui-ci doit être doublé et son niveau d'éclatement Q augmenté de 1 ; un paquet frère au même niveau d'éclatement doit être créé ; les articles sont répartis dans les deux paquets selon la valeur du bit (M+Q+1) de la fonction de hachage. Si le niveau du répertoire P est supérieur à Q, alors le répertoire doit simplement être mis à jour, 2**(P-Q+1) pointeurs étant forcé sur l'adresse du nouveau paquet. Si P est égal à Q, alors le répertoire doit être doublé.
La suppression d'un article dans un paquet peut théoriquement conduire à réorganiser le répertoire. En effet, si le paquet concerné est le seul paquet avec son frère au niveau d'éclatement le plus bas et si la suppression d'un article laisse assez de place libre pour fusionner les deux frères, la fusion peut être entreprise. Le niveau d'éclatement du répertoire doit alors être réduit de un et celui-ci doit être divisé par deux en fusionnant les blocs jumeaux.
II.4.2.2. - Le hachage linéaire.
Le hachage linéaire [LITWIN80] apporte les réponses suivantes aux questions déterminantes d'une méthode de hachage dynamique :
(Q1) - Le fichier est étendu dès qu'un paquet est plein, comme dans le hachage extensible ; un nouveau paquet est aussi ajouté au fichier à chaque extension.
(Q2) - Le paquet doublé n'est pas celui qui est saturé, mais un paquet pointé par un pointeur courant initialisé au premier paquet du fichier et incrémenté de un à chaque éclatement d'un paquet (donc à chaque saturation) ; lorsque ce pointeur atteint la fin de fichier, il est repositionné au début du fichier ;
(Q3) - Un niveau d'éclatement F du fichier (initialisé à 0 et incrémenté lorsque le pointeur courant revient en début de fichier) est conservé dans le descripteur du fichier ; pour un paquet situé avant le pointeur courant, (M+F+1) bits de la fonction de hachage doivent être utilisés alors que seulement (M+F) sont à utiliser pour adresser un paquet situé après le pointeur courant et avant le paquet 2**(M+F) ;
(Q4) - Une gestion de débordement est nécessaire puisqu'un paquet plein n'est en général pas éclaté ; il sera seulement quand le pointeur courant passera par son adresse. Une méthode de débordement quelconque peut être utilisée.
En résumé, il est possible de définir le hachage linéaire comme suit.
Notion II.22. : Hachage linéaire(Linear hashing)
Méthode de hachage dynamique nécessitant la gestion de débordement et consistant à : (1) éclater un paquet pointé par un pointeur courant circulaire quand un paquet est plein (2) mémoriser le niveau d'éclatement du fichier afin de déterminer le nombre de bits de la fonction de hachage à appliquer avant et après le pointeur courant.
La figure II.12 illustre un fichier haché linéairement
Figure II.12 . -Fichier haché linéairement
L'insertion d'un article dans un fichier haché linéairement se fait très simplement : si F est le niveau d'éclatement du fichier, (M+F) bits de la clé sont tout d'abord pris en compte pour déterminer le numéro de paquet. Si le numéro obtenu est supérieur au pointeur courant, il est correct ; sinon, un bit supplémentaire de la fonction de hachage est utilisé pour déterminer le numéro de paquet. L'insertion s'effectue ensuite de manière classique excepté que lorsqu'un paquet est saturé, le paquet pointé par le pointeur courant est éclaté ; ce pointeur courant est augmenté de un ; s'il atteint le paquet 2**(M+F) du fichier, il est ramené au début et le niveau d'éclatement du fichier est augmenté de un.
De manière similaire au répertoire du hachage extensible, la suppression d'article dans un paquet peut amener la fusion de deux paquets et donc le recul de un du pointeur courant. Attention, les paquets fusionnés n'incluent en général pas le paquet dans lequel a lieu la suppression, la fusion peut amener des distributions d'articles en débordement.
Une variante de cette méthode consistant à changer la condition d'éclatement a été proposée dans [LARSON80]. La condition retenue est l'atteinte d'un taux de remplissage maximum du fichier, le taux de remplissage étant le rapport de la place occupée par les articles à la taille totale du fichier.
En résumé, les méthodes de hachage dynamique sont bien adaptées aux fichiers dynamiques, c'est-à-dire de taille variable sans doute pas trop gros pour éviter les saturations de paquets trop nombreuses et/ou les accroissements de la taille du catalogue. Leurs limites sont encore mal connues. le hachage extensible paraît plus robuste aux mauvaises distributions de clés que le hachage linéaire. Par contre, la gestion d'un répertoire est plus lourde que celle d'un pointeur courant.
De plus, le grand problème des méthodes par hachage reste l'absence de possibilités efficaces d'accès ordonné pour un tri total ou pour des questions sur les plages de valeur. Ceci, est la limite essentielle qui nécessite l'emploi d'autres méthodes.
II. 5 ORGANISATIONS ET METHODES D'ACCES INDEXEES
II.5.1. - Principes des organisations
II.5.1.1. - Notion d'index.
Le principe de base des organisations et méthodes d'accès indexées est d'associer à la clé d'un article son adresse relative dans le fichier à l'aide d'une <<table des matières>> du fichier, appelée index.
Notion II.23. : Index (Index)
Table (ou plusieurs tables) permettant d'associer à une clé d'article l'adresse relative de cet article.
La figure II.13 illustre cette notion d'index. L'index d'un fichier peut en général être rangé dans le fichier ou dans un fichier spécial.
Figure II.13. - Exemple de fichier indexé
Les étapes successives exécutées pour l'accès à un article dans un fichier indexé sont les suivantes :
a) accès à l'index ;
b) recherche sur la clé de l'article désiré afin d'obtenir l'adresse relative de l'article ou d'un paquet contenant l'article ;
c) conversion de l'adresse relative en adresse absolue ;
d) accès à l'article (ou paquet d'articles) sur disques magnétiques ;
e) transfert de l'article dans la zone du programme usager.
II.5.1.2. - Variantes possibles.
Tout d'abord, un index d'un fichier peut être trié ou non. Le fait que l'index soit trié autorise la recherche dichotomique. Ainsi, un index contenant n clés, divisé en blocs (d'un secteur) de b clés nécessitera en moyenne n/2b accès pour retrouver une clé s'il n'est pas trié alors qu'il suffira de Log2n/b accès s'il est trié. A titre d'illustration, avec n = 106 , b = 100 clés, on obtient 10 accès si l'index est trié contre 5 000 accès sinon.
Un index d'un fichier indexé peut contenir toutes les clés (c'est-à-dire celles de tous les articles) ou seulement certaines. Afin de différencier les méthodes d'accès obtenues, on introduit la notion de densité d'un index.
Notion II.24. : Densité d'un index (Index key selectivity)
Quotient du nombre de clés dans l'index sur le nombre d'articles du fichier.
La densité d'un index varie entre 0 et 1. Les cas intéressants à distinguer sont densité = 1 (on parle dans ce cas d'index dense) et densité <1 où l'on parle d'index non dense . Dans le cas d'index non dense, les articles du fichier ainsi que l'index sont triés. Le fichier est divisé en paquets de taille fixe et chaque paquet correspond à une entrée en index contenant le doublet : <plus grande clé du paquet-adresse relative du paquet>. La figure II.14 illustre un index non dense et le fichier correspondant.
Figure II.14. - Exemple d'index non dense.
Finalement, compte tenu que le fichier puisse être trié ou non trié, l'index dense ou non dense, trié ou non trié, diverses variantes sont théoriquement possibles. Le tableau de la figure II.15 illustre les possibilités pratiques.
IS3 = Indexé type système 3
ISAM = Séquentiel indexé IBM
VSAM = Séquentiel indexé régulier IBM
UFAS = Séquentiel indexé régulier CII-Honeywell-BULL
Figure II.15. -Variantes de méthodes d'accès indexées.
II.5.1.3. - Index hiérarchisé.
Un index peut être vu comme un fichier de clés. Si l'index est grand (par exemple plus d'une page) il est nécessaire de créer un index d'index, c'est-à-dire des index à plusieurs niveaux. Un tel index est appelé index hiérarchisé.
Notion II.25 : Index hiérarchisé (Multilevel index)
Un index hiérarchisé à deux niveaux est un index trié en paquets, possédant lui-même un index, la clé de chaque entrée de ce dernier étant la plus grande du paquet. Un index hiérarchisé à n niveaux est un index hiérarchisé à n -1 niveaux, possédant lui-même un index à un niveau.
La figure II.16 illustre un index hiérarchisé. La notion d'index hiérarchisé est indépendante du nombre de niveaux qui peut grandir autant que nécessaire.
Figure II.16. - Exemple d'index hiérarchisé.
II.5.1.4. - Arbres-B.
Afin de mieux caractériser la notion d'index hiérarchisé et de la rendre indépendante des particularités d'implantation, on a été amené à introduire une structure d'arbre, avec un nombre variable de niveaux. Cette structure appelée arbre-B [BAYER72, COMER79] peut être introduite formellement comme suit :
Notion II.26. : Arbre-B(B-tree)
Un arbre-B d'ordre m est un arbre au sens de la théorie des graphes tel que :
1°) Toutes les feuilles sont au même niveau ;
2°) Tout noeud non feuille a un nombre NF de fils tel que m+1 < NF < 2m +1, sauf la racine qui a un nombre NFR de fils tel que 0 < NFR < 2m +1
La figure II.17 représente un arbre balancé d'ordre 2.
Figure II.17. -Arbre-B d'ordre 2.
Un arbre-B peut être utilisé pour constituer un index hiérarchisé d'un fichier. Dans ce cas, les noeuds représentent des pages de l'index. Ils contiennent des clés triées par ordre croissant et des pointeurs de deux types : les pointeurs internes désignent des fils et permettent de définir la structure de l'arbre, alors que les pointeurs externes désignent des pages de données (en général, des adresses relatives). La figure II.18 précise la structure d'un noeud.
Pi : Pointeur interne permettant de représenter l'arbre ; les feuilles ne contiennent pas de pointeurs Pi ;
ai : Pointeur externe sur une page de données ;
xi : valeur de clé.
Figure II.18. -Structure d'un noeud d'un arbre-B.
De plus, l'ensemble des clés figurant dans l'arbre-B doit être trié selon l'ordre post-fixé induit par l'arbre, ceci afin de permettre les recherche en un nombre d'accès égal au nombre de niveaux. Plus précisément, en désignant par K(Pi) l'ensemble des clés figurant dans le sous-arbre dont la racine est pointé, on doit vérifier :
(1) (x1, x2…xK) est une suite croissante de clés ;
(2) Toute clé y de K(P0) est inférieure à x1 ;
(3) Toute clé y de K(P1) est comprise entre xi et xi+1 ;
(4) Toute clé y de K(PK) est supérieure à xk.
La figure II.19 représente un exemple d'index sous forme d'arbre-B d'ordre 2. Cet arbre contient les valeurs de clé de 1 à 25. Les traits pleins représentent les pointeurs internes, les traits pointillés les pointeurs externes.
Figure II.19. -Exemple d'index sous forme d'arbre-B.
La recherche d'une clé dans un arbre-B s'effectue en partant de la racine. En règle générale, les valeurs contenues dans un noeud partitionnent les valeurs possibles de clés en un nombre d'intervalles égal au nombre de branches. Ainsi, si la valeur cherchée est inférieure à la première clé du noeud, on choisit la première branche ; si elle est compris entre la première clé et la deuxième clé, on choisit la deuxième branche, etc … Si une clé n'est pas trouvée après recherche dans un noeud terminal, c'est qu'elle n'existe pas.
Le nombre de niveaux d'un arbre-B est déterminé par son degré et le nombre de clés contenues. Ainsi, dans le pire des cas si l'arbre est rempli au minimum, il existe :
- une clé à la racine,
- deux branches en partent avec m clés,
- (m+1) branches en partent avec m clés.
Pour un arbre de niveaux, le nombre de clés est donc :
1 + 2 m (1+ (m+1) + (m+1)2 + … + (m+1)h-2)
= 1 + 2 ((m+1)h-1-1)
D'où l'on déduit que pour stocker N clés, il faut :
h = 1 + logm+1N + 1 niveaux
2
Par exemple, pour stocker 1 999 999 clés avec un arbre-B de degré 99, il faut :
h £ 1 + log100106= 4
soit, au plus quatre niveaux. Ceci conduit à penser qu'un article d'un fichier de deux millions d'articles avec un index hiérarchisé organisé comme un arbre-B peut être cherché en quatre entrées-sorties.
L'insertion d'un clé dans un arbre-B est une opération complexe. Elle peut être définie simplement de manière récursive comme suit :
a) Rechercher le noeud terminal qui devrait contenir la clé à insérer et l'y insérer en bonne place ;
b) Si le nombre de clés après insertion de la nouvelle clé est supérieur à 2 m, alors migrer la clé médiane au niveau supérieur, en répétant la procédure d'insertion dans le noeud supérieur.
A titre d'exemple, la figure II.20 représente les étapes nécessaires à l'insertion de la clé (25) dans l'arbre-B représenté figure II.19.
La suppression d'un clé soulève également des problèmes. Tout d'abord si l'on supprime une clé non terminale, il faut remonter la clé suivante pour garder le partitionnement. De plus, si un noeud a moins de m clés, il faut regrouper avec le précédent de même niveau afin de respecter la définition.
Une variante de l'arbre-B tel que nous l'avons décrit pour réaliser des index est l'arbre B* [KNUTH73, COMER79] l'algorithme d'insertion essaie de redistribuer les clés dans un noeud voisin avant d'éclater. Ainsi, l'éclatement ne se produit que quand deux noeuds consécutifs sont pleins. Les deux noeuds éclatent alors en trois. Les pages des index de type arbre-B* sont donc en général mieux remplies que celles des index de type arbre-B.
Figure II.20. - Insertion de la clé 25.
II.5.1.5. - Arbre B+.
L'utilisation des arbre-B pour réaliser des fichiers indexés tels que décrit ci-dessus conduit à des traitements séquentiels coûteux. En effet, l'accès selon l'ordre croissant des clés à l'index nécessite de nombreux passages des pages externes pages internes. Pour éviter cet inconvénient, il a été proposé de répéter les clés figurant dans les noeuds internes au niveau des noeuds externes. De plus, les pages correspondant aux feuilles sont chaînées entre-elles. On obtient alors un arbre-B+. L'arbre-B+ correspondant à l'arbre-B de la figure II.19 est représenté figure II.21. Les pointeurs externes se trouvent seulement au niveau des feuilles.
Les arbres-B+ peuvent être utilisés pour réaliser des fichiers à index hiérarchisés de deux manières au moins :
- l'arbre B+ peut être utilisé pour réaliser seulement les index. Autrement dit, les articles sont stockés dans un fichiers séquentiel classique et l'arbre-B+ contient toutes les clés ainsi que les adresses d'articles. Une telle organisation est proche de celle proposée par IBM sur la série3.
Nous appelons cette méthode présentée ci-dessous IS3.
- L'arbre-B+ peut être utilisé pour réaliser fichier et index. Dans ce cas, les pointeurs externes sont remplacés par le contenu des articles. Les articles sont donc triés. Seules les clés sont bien sur déplacées aux niveaux supérieurs qui constituent un index non dense. Cette méthode correspond à l'organisation séquentielle indexée régulière de IBM connue sous le nom de VSAM et également à celle de CII-Honeywell-BULL connue sous le nom de UFAS.
Figure II.21. - Exemple d'index sous forme d'arbre-B+.
II.5.2.- Organisation indexée IS3
Cette organisation est voisine de celle des systèmes IBM3.38… Les articles sont rangés en séquentiel dans un fichier dont l'index est dense et organisé sous forme d'un arbre-B+.
Notion II.27. : Fichier indexé(Indexed file)
Fichier non trié, d'index trié dense organisé sous forme d'un arbre-B+.
L'interprétation de la définition que constitue la notion II.27 soulève plusieurs problèmes. Tout d'abord, comment est défini l'ordre de l'arbre-B+ qui constitue l'index? La solution consiste à diviser l'index en pages (une page = 1 à p secteurs). Lors de la première écriture, les pages ne sont pas complètement remplies. Lors d'une insertion, si une page est pleine elle est éclatée en deux pages à demi-pleines. La clé médiane est remontée au niveau supérieur.
Un deuxième problème consiste à garder un index dense. En fait, celui-ci est dense au dernier niveau. Autrement dit, toutes les clés d'articles sont gardées au plus bas niveau. Ainsi, quand une page éclate, la clé médiane devient la plus grande clé de la première page résultant de l'éclatement. Cette clé est donc dupliquée au niveau supérieur de l'index. La figure II.22 illustre une insertion dans un fichier indexé.
Figure II.22. - Insertion dans un fichier IS3.
Un dernier problème est celui du stockage de l'index. Celui-ci peut être stocké en fin de fichier. Il est ainsi possible de lire la page supérieure de l'index en mémoire centrale lors du début d'un travail sur un fichier, puis de la réécriture en fin de travail. Il est aussi possible avec une telle méthode d'enregistrement des index de garder les versions historiques des index à condition que les nouveaux articles écrits le soient après le dernier index enregistré, c'est-à-dire en fin de fichier.
La méthode d'accès-organisation indexé IS3 présente plusieurs avantages : l'insertion des articles est simples puisqu'elle s'effectue en séquentiel dans le fichier ; il est possible de garder des versions historiques des index. Les performances de la méthode sont satisfaisantes. Si m est le nombre de clés par page d'index, du fait de l'organisation de l'index en arbre-B, le nombre d'entrées-sorties nécessaires pour lire un article dans un fichier de N articles reste inférieur ou égal à :
2 + log(m/2) N + 1
2
Une écriture nécessite en général deux accès, sauf dans les cas d'éclatement de page index où il faut une lecture et deux écriture de plus par niveau éclaté, en général. En pratique, et à titre d'exemples, un fichier de moins de 106articles ne nécessitera pas plus de trois entrées-sorties en lecture.
Cette méthode présente cependant trois inconvénients sérieux :
- du fait de la séparation des articles et de l'index les mouvements de bras des disques sont en général importants ;
- la lecture en séquentiel par clé croissante doit se faire par consultation de l'index et en conséquence est très coûteuse ;
- l'index est dense et donc de grande taille si aucune technique de compactage de clés n'est mise en oeuvre.
II.5.3. - Organisation séquentielle indexée ISAM
II.5.3.1. - Présentation générale.
Il s'agit de l'organisation IBM utilisée dans les systèmes DOS, OS/VS et connue sous le nom ISAM (Indexed Sequential Acces Method) [IBM78].
Notion II.28. : Fichier séquentiel indexé (Indexed sequential file)
Fichier trié d'index trié non dense composé d'une zone primaire et d'une zone de débordement. Une piste saturée déborde dans une extension logique constituée par une liste d'articles en débordement.
Un fichier ISAM comporte trois zones logiques :
- zone primaire où l'on écrit les articles à la première écriture ;
- zone de débordement où l'on transfère les articles lors des additions au fichier ;
- zone d'index où l'on écrit les index.
Ci-dessous nous étudions successivement chacune des zones.
II.5.3.2. - Etude de la zone primaire.
La zone primaire se compose de cylindres successifs dont certaines pistes sont réservées pour l'index et les zones de débordement. En zone primaire, les articles sont enregistrés par ordre croissant des clés. Ils peuvent être bloqués ou non. Lors de la première écriture du fichier, les articles doivent être délivrés au système de fichiers par ordre croissant des clés. La figure II.23 illustre un fichier ISAM après une première écriture. Ce fichier est composé de deux cylindres.
Figure II.23. -Fichier ISAM après une première écriture des articles 1, 3, 5, 7, 9, 14, 17, 21, 23, 27, 29, 31 (dans l'ordre).
II.5.3.3. - Etude de la zone de débordement.
Il existe deux types de zone de débordement : la zone de débordement de cylindres composées de quelques pistes sur chaque cylindre et la zone de débordement indépendante, composée des derniers cylindres du fichier (Fig. II.24).
Figure II.24. -Zones de débordement d'un fichier ISAM.
En zone de débordement, les articles ne sont pas bloqués. Ils sont chaînés entre eux afin de reconstituer la piste qui a débordé de manière logique. Quand un article est inséré, on recherche sa séquence dans la piste logique. S'il est placé en zone primaire, les articles suivants sont déplacés et le dernier est écrit en zone de débordement. Les chaînages sont mis à jour. S'il vient en zone de débordement, il est écrit dans cette zone et inséré en bonne place dans la chaîne des articles en débordement.
La zone de débordement de cylindre est tout d'abord utilisée. Lorsqu'elle est saturée, la zone de débordement indépendante est utilisée. Dans ce cas, du fait que le chaînage est effectué par ordre croissant des clés, il est possible que celui-ci parte de la zone de débordement de cylindre, puis pointe en zone de débordement indépendante, puis revienne en zone de débordement de cylindre, etc … Alors, la méthode devient particulièrement peu performante pour recherche d'un article dans une piste ayant débordé, du fait des déplacements de bras.
II.5.3.4. - Etude de la zone index.
Il existe obligatoirement deux niveaux d'index et optionnellement trois: les index de pistes, les index de cylindres et le (ou les) index maîtres.
Le premier niveau d'index obligatoire est l'index de piste. Il en existe un par cylindre : il est en général contenu sur la première piste du cylindre. Chaque entrée correspond à une piste du cylindre : elle fournit la plus grande clé de la piste logique en zone de débordement ainsi que l'adresse du premier article en zone de débordement s'il existe. La figure II.25 illustre le format de l'index de piste.
CD = Contrôle de débordement précisant l'adresse du dernier article de la zone de débordement.
PCP = Plus grande clé en zone primaire et adresse de la piste.
PCD = Plus grande clé en zone de débordement et adresse du premier article en zone de débordement.
Figure II.25. -Format de l'index de piste.
Le deuxième niveau de l'index obligatoire est l'index de cylindre. Il existe un index de cylindre par fichier. Cet index contient une entrée par cylindre comportant la plus grande clé du cylindre ainsi que l'adresse du cylindre. L'index de cylindre est généralement rangé dans une zone particulière, par exemple en début de zone de débordement indépendante. Cet index parmet, à partir d'une clé d'article, de sélectionner le cylindre où doit se trouver l'article.
Le troisième niveau d'index est optionnel : c'est l'index maître. Il est utilisé quand l'index de cylindre est trop grand afin d'accélérer les recherches. Il existe une entrée en index maître par piste de l'index de cylindre. Cette entrée contient l'adresse de la piste et la valeur de la plus grande clé dans la piste.
II.5.3.5. - Vue d'ensemble.
La figure II.26 donne une vue d'ensemble d'un fichier ISAM après insertion d'articles, avec seulement deux niveaux d'index. Les avantages de la méthode sont le fait que le fichier est trié, ce qui facilite l'accès en séquentiel trié, ainsi que les temps d'accès tant que le fichier n'a pas débordé (3. E/S pour lire un article). Les inconvénients sont, d'une part, la gestion des débordements qui est complexe et dégrade les performances de sorte qu'il est nécessaire de réorganiser périodiquement les fichiers ayant débordé, et d'autre part le fait que la méthode d'accès ne soit pas indépendante des caractéristiques physiques du support (pistes, cylindres, …). Les performances dépendent des débordements. Si une piste comporte des articles en débordement, une lecture nécessitera approximativement 3+[d/2] entrées-sorties alors qu'une écriture demandera 2+[d/2]+4 entrées-sorties, ceci afin de trouver la position de l'article, l'écrire et mettre à jour les chaînages. Ceci peut devenir très coûteux.
Figure II.26. - Vue d'ensemble d'un fichier ISAM
(Les pointeurs issus du cylindre 1 ne sont pas représentés)
II.5.4. - Organisation séquentielle indexée régulière VSAM
II.5.4.1. - Présentation générale.
Il s'agit de l'organisation IBM utilisée dans le système IBM OS/VS et connue sous le nom de VSAM (Virtual Sequential Acces Method) [IBM87].
Notion II.29. : Fichier séquentiel indexé régulier (Virtual sequential file)
Fichier trié d'index trié non dense dont l'ensemble fichier plus index est organisé sous forme d'un arbre-B.
Le fichier est divisé en aires, une aire étant un ensemble de pistes du même cylindre ou de cylindres contigus. Chaque aire est elle-même divisée en intervalles, un intervalle étant généralement composé d'une partie de piste ou de plusieurs pistes consécutives lue(s) en une seule entrée-sortie. Lorsqu'un intervalle est saturé, il éclate en deux intervalles ; lorsqu'une aire est saturée, elle éclate aussi en deux aires, si bien que le fichier se réorganise de lui-même par incréments.
Cette organisation résulte d'une étude critique de ISAM. Cette fois, le fichier est plus indépendant de la mémoire secondaire : la piste est remplacée par l'intervalle qui peut être une fraction de piste ou plusieurs pistes, le cylindre est remplacé par la notion d'aire. Les débordements ne perturbent plus l'organisation puisque le mécanisme de débordement est celui de l'arbre-B, c'est-à-dire qu'un intervalle ou une aire saturée éclatent en deux.
II.5.4.2. - Etude de la zone des données.
Cette zone qui contient les articles est divisée en intervalles et aires, comme représentée figure II.27. Lors de la première écriture, comme avec des fichiers séquentiels indexés ISAM, les articles sont enregistrés triés, c'est-à-dire que le programme doit les délivrer à la méthode d'accès dans l'ordre croissant des clés. Cette fois, les mises à jour sont prévues : de la place libre est laissée dans chaque intervalle et des intervalles libres sont laissés dans chaque aire afin de permettre les insertions de nouveaux articles.
A titre d'exemple, le fichier II.27 a été créé avec les paramètres suivants :
- % octets libres par intervalles = 25 ;
- % intervalles libres par aire = 25.
Lors de la première écriture, le programme créant le fichier a délivré au système les articles suivants (dans l'ordre) : 1, 5, 7, 9, 15, 20, 22, 27, 30, 31, 33, 37, 40, 43, 47, 51, 53.
Figure II.27. - Fichier séquentiel indexé régulier après première écriture.
L'algorithme d'insertion d'un article consiste à déterminer grâce aux index l'intervalle qui doit contenir l'article. Ensuite, deux cas sont possibles :
a) si l'intervalle n'est pas plein, alors l'article est rangé dans l'intervalle, en bonne place dans l'ordre lexicographique des clés. Par exemple, l'insertion de l'article de clé 10 conduira à la substitution d'intervalle représentée figure II.28 ;
Figure II.28. -Insertion de l'article de clé 10 dans le fichier représenté figure II.20.
b) si l'intervalle est plein, alors il éclate en deux intervalles à demi-pleins.
Deux cas sont encore possibles :
b1) s'il existe un intervalle libre dans l'aire, celui-ci est utilisé afin de stocker l'un des deux intervalles résultant de l'éclatement. Par exemple, l'insertion de l'article de clé 13 dans le fichier obtenu après insertion de l'article de clé 10 (Fig. II.21) conduit au fichier représenté figure II.29.
b2) s'il existe pas d'intervalle libre dans l'aire, on alloue alors une aire vide au fichier et on éclate l'aire saturée en deux à demi-pleines ; pour cela la moitié des intervalles contenant les articles de plus grandes clés sont recopiés dans l'aire nouvelles. Par exemple, l'insertion des articles de clés 11 et 12 dans le fichier de la figure II.29 conduit au fichier représenté figure II.30.
Figure II.29. - Fichier après insertion des articles de clés 10 et 13.
Figure II.30. - Fichier après insertion des articles supplémentaires 11 et 12.
II.5.4.3. - Etude de la zone index.
Il peut exister deux ou trois niveaux d'index. Le premier niveau est appelé index d'intervalles. Il en existe un par aire. Chaque entrée contient la plus grande clé de l'intervalle correspondant ainsi que son adresse. Le deuxième niveau est appelé index d'aires. Il en existe un par fichier. Chaque entré contient la plus grande clé de l'aire correspondante ainsi que l'adresse de l'aire. Il est également possible, dans le cas où l'index d'aire est trop grand (par exemple plus d'une piste), de faire gérer au système un index de troisième niveau appelé index maître et permettant d'accéder directement à la partie pertinente de l'index d'aire. A titre d'illustration, la figure II.31 représente les index d'intervalles et d'aires du fichier représenté figure II.30.
Figure II.31. -Index du fichier représenté figure II.30.
II.5.4.4. - Vue d'ensemble.
La figure II.32 donne une vue d'ensemble d'un autre fichier VSAM composé de deux aires, avec seulement deux niveaux d'index. Les avantages de la méthode sont le fait que le fichier est trié, ce qui facilite les accès en séquentiel trié, ainsi que les temps d'accès à un article: la lecture s'effectue toujours en trois entrée-sorties. Les inconvénients sont peu nombreux ; cependant l'écriture peut parfois être très longue dans le cas d'éclatement d'intervalles ou pire, dans le cas d'éclatement d'aires.
Figure II.32. - Vue d'ensemble d'un fichier séquentiel indexé régulier.
II.6 - CONCLUSION
Nous venons de passer en revue les fonctions essentielles et les techniques de base des gestionnaires de fichier. D'autres études peuvent être trouvées dans [GARDARIN79, JOUFFROY77, WIDERHOLD77]. Il faut savoir qu'un service de gestions de fichiers est de plus en plus souvent la base d'un système de gestion de bases de données. Pour ce faire, des niveaux de logiciels supérieurs sont généralement implantés pour assurer la gestion d'index multiples, la description centralisée des données des articles de fichiers, des interfaces de gestion de données variées avec les programmes d'applications, etc…
La nécessité de pouvoir supporter un Système de Gestion de Bases de Données tend aujourd'hui à compliquer le service de gestion de fichiers qui devient de plus en plus élaboré. Il n'est par exemple, pas rare de trouver des systèmes gérant plusieurs index sur des clés différentes appelés index secondaires pour un même fichier. En effet, les systèmes de gestion de bases de données, pour permettre la consultation des données selon des critères variés, nécessitent généralement plusieurs chemins d'accès à un même article. Nous reviendrons sur les problèmes de méthodes d'accès et d'organisation de fichiers pour les systèmes de gestion de bases de données dans un chapitre spécifique au sujet.