4_5965377530222351178 (1).pdf

Cours Structures de Fichiers (SFSD / 2CP) Prof. HIDOUCI Walid-Khaled / ESI 2021 (http://hidouci.esi.dz) Plan 1) Généralités ( 2 - 18 ) 2) Les structures séquentielles ( 19 - 28 ) 3) Les méthodes d’index ( 29 - 40 ) 4) Les méthodes à base d’arbres de...

Cours Structures de Fichiers (SFSD / 2CP) Prof. HIDOUCI Walid-Khaled / ESI 2021 (http://hidouci.esi.dz) Plan 1) Généralités ( 2 - 18 ) 2) Les structures séquentielles ( 19 - 28 ) 3) Les méthodes d’index ( 29 - 40 ) 4) Les méthodes à base d’arbres de recherche ( 41 - 55 ) 5) Les méthodes de Hachage ( 56 - 62 ) 6) Les opérations de haut niveau ( 63 - 77 ) Introduction L’objectif du cours est l’étude des méthodes d’accès aux fichiers (structures et algorithmes associés : recherche, insertion, suppression, …). Cela concerne principalement : - Les performances des solutions algorithmiques manipulant des structures de fichiers (manipulation efficace de données volumineuses et massives). - L’analyse de la complexité adaptées aux opérations d’entrées/sorties. Le cours prépare l’étudiant à : - Aborder les nouvelles problématiques du contexte Big Data avec une formation de base solide et rigoureuse. - Aborder sans difficultés, les futures enseignements dans les domaines des bases et ingénierie de données, ainsi que dans la programmation avancée et les systèmes d’exploitation modernes. On s’intéresse à l’étude des algorithmes de base sur les grands ensembles de données en mémoire externe. C’est un aspect fondamental dans la formation de base d’un ingénieur en informatique (toutes spécialités confondues). Les ensembles sont représentés par des structures de données externes et internes. Leurs manipulations induit des transferts de données entre mémoire centrale et mémoire externe (secondaire). L’optimisation du nombre de transferts est le cœur de la problématique des performances de ce type d’applications. La présence aux séances de cours est plus que conseillée. L’étudiant doit alors prendre des notes durant les séances de cours, pour les approfondir ensuite à travers des lectures de textes de références sur le domaine. Certaines ressources (documents et programmes de démonstration) seront envoyés aux étudiants par mail (certaines sont aussi disponibles en ligne : hidouci.esi.dz) ⇒ Mais ne couvrent pas la totalité des notions abordées dans le cours. Les questions peuvent être posées en cours ou en dehors du cours (bureau, par mail,...) Le langage C sera utilisé pour la mise en pratique des notions abordées. La maîtrise de ce langage en particulier, constitue généralement, une aide importante pour la bonne compréhension du fonctionnement interne et des détails techniques des systèmes informatiques. Hidouci W.K. / Introduction / Cours : Structures de fichiers (SFSD) / ESI – 2021 1  Structures de Fichiers Chapitre 1 Généralités Dans ce chapitre nous allons présenter les notions générales relatives aux structures de fichiers. Les principaux points abordés sont - Les mémoires - Les fichiers - Les opérations de base sur les fichiers 1) Les différents types de mémoires Il existe plusieurs types de mémoires dans un ordinateur. Chaque type de mémoire est caractérisé par la vitesse d’accès, la taille, la nature de l’accès permis (lecture, écriture, effacement,...), le coût et la volatilité (pertes d’information en cas de crash système ou redémarrage). Il y a des mémoires très rapides, très coûteuse et en très petites quantités : les registres du processeur. Leur utilisation est automatisée à travers le module de génération de code du compilateur utilisé. Il y a des mémoires très lentes, peu coûteuses et en très grandes quantités : par exemple les volumes de bandes magnétiques. De nos jours on ne les utilise principalement que pour l’archivage des données et programmes à travers des commandes particulières du système d’exploitation. Entre ces deux extrêmes on trouve (dans l’ordre croissant des vitesses d’accès et décroissant du coût à l’unité) les types de mémoires suivants : - Les mémoires cache entre le processeur et la mémoire centrale (en lecture/écriture et volatile gérées principalement par le hardware). Leurs tailles sont supérieures aux registres et inférieures à la mémoire centrale. - La Mémoire Centrale (MC) ou mémoire principale (en lecture/écriture et volatile) contenant les programmes et les données en cours de traitement. La taille est supérieure à celle des mémoires caches et inférieure à celle de la mémoire secondaire. - La Mémoire Secondaire (MS), souvent constituée de dispositifs de mémoires externes à accès direct : les disques magnétiques , les flash disques, les disques SSD, … (en lecture/écriture et non volatile). La MS est utilisée principalement pour le stockage persistent des programmes et/ou données et aussi pour la virtualisation de la MC (comme par exemple le paging dans les systèmes d’exploitation). Sa taille est souvent supérieure à celle de la MC mais l’accès est beaucoup plus lent aussi. Souvent une petite partie de la MC est réservée par le système d’exploitation pour être gérée comme mémoire cache de la MS (par exemple le buffer pool). - Les autres mémoires externes ou auxiliaires utilisées principalement pour l’archivage de données et de programmes sont constituées de dispositifs de mémorisation lents et peu coûteux. Souvent offrant la possibilité de gestion multi-volumes pour rendre leur capacité de stockage théoriquement illimitée. Nous retrouvons dans cette catégorie les disques optiques (en lecture seule ou en lecture/écriture limitée et non volatiles) et les bandes magnétiques à accès séquentielle (en lecture/écriture et non volatile). Hidouci W.K. / Généralités / Structures de Fichiers / SFSD / ESI - 2021 2 En programmation de structures de fichiers, nous nous intéressons principalement à la mémoire centrale (MC) et à la mémoire secondaire (MS). Toutes les variables d’un programme en cours d’exécution sont allouées en MC et le contenu des fichiers manipulés se trouve en MS. D’après le paragraphe précédent, nous retiendrons ce qui suit : - La MC est volatile (son contenu est perdu en cas de crash système ou redémarrage) - La MS n’est pas volatile (elle supposée résister aux crash et redémarrages) - L’accès à la MC est beaucoup plus rapide que celui à la MS. Par exemple avec les technologies actuelles, l’accès à une unité d’information en MC est presque 10000 à 100000 fois plus rapide que celui d’un disque magnétique et aussi 1000 fois plus rapide que celui d’un disque SSD. 1.1) Structure des disques magnétiques Un des types de MS les plus utilisés de nos jours reste le disque magnétique (ou encore disque dur : DD ou HDD pour Hard Disk Drive). Un HDD est un ensemble de plateaux en forme de disques superposés. Chacun d'eux est formé de deux faces magnétiques (surfaces) et tournent en continu avec une certaine vitesse de rotation (R). Chaque piste est découpée en secteurs de même taille. Le secteur représente l'unité de transfert entre la MS et la MC. C'est la plus petite quantité d'information pouvant être lue ou écrite sur le disque. Disque = ensemble de plateaux tournant avec une vitesse de rotation déterminée Plateau = ensemble de pistes concentriques numérotées 0, 1, 2,... sur chaque face Cylindre = ensemble de pistes ayant un même diamètre sur les différents plateaux Piste = ensemble de secteurs de même taille Le bras du disque contient les têtes de lecture/écriture (une pour chaque face d'un plateau). Il se déplace latéralement de cylindre en cylindre pour positionner les têtes de lecture/écriture sur les bonnes pistes. Pour lire ou écrire un secteur donné, le contrôleur déplace d'abord le bras vers le bon cylindre, ensuite attend que le bon secteur passe sous la tête de lecture/écriture concernée avant de transférer les données. Avec la technologie actuelle, le temps nécessaire à cette opération (temps d'accès = temps du déplacement du bras + le temps d'attente de passage du secteur sous la tête de lecture/écriture, incluant le transfert de données) est au voisinage de quelques millisecondes en moyenne. Si on le compare au temps d'accès à la mémoire centrale (quelques dizaines ou centaines de nanosecondes), la différence est énorme (le temps d'accès au disque est plus lent que celui de la MC de plusieurs ordres de grandeurs). Le temps de déplacement du bras (temps de translation) est plus grand que le temps de rotation. Des lectures ne nécessitant pas de déplacement de bras (donc sur le même cylindre) coûtent aux environs de quelques ms en moyenne. Parmi les méthodes utilisées pour diminuer l'effet de cette grande différence dans le temps d'accès entre la MC et la MS, on trouve le buffering. Il s'agit de réserver une zone en mémoire centrale pouvant contenir plusieurs blocs en même temps (le buffer-cache). Lors de la lecture de blocs non présents en MC, des stratégies de remplacement (comme LRU, FIFO, …) sont utilisées afin de minimiser le nombre d'accès disque. Le prefetching (consistant à lire plusieurs blocs consécutifs lors d’une demande d’accès à un seul bloc donné) est très souvent utilisé, en combinaison avec le buffering, pour augmenter les chances de trouver les blocs demandés, déjà présents en MC, lors de leurs éventuels futurs accès. Hidouci W.K. / Généralités / Structures de Fichiers / SFSD / ESI - 2021 3  Bras surface piste plateaux Tête de lecture/écriture Vitesse de rotation R Vitesse de translation T secteurs D'autres techniques, comme la multi-programmation (durant l'opération d'E/S d'un programme, le processeur est alloué à un autre programme) avec le Time-Sharing (pseudo-parallélisme entre plusieurs processus en partageant le temps CPU) ou encore la parallélisation des E/S (les données sont réparties sur plusieurs disques – comme dans la technologie RAID) sont aussi utilisées pour diminuer le goulot d'étranglement sur les E/S. De plus, comme le temps de déplacement du bras est plus grand que celui nécessaire pour une rotation du disque, l'accès à des secteurs physiquement proches (situés sur la même piste ou le même cylindre par exemple) est beaucoup plus rapide que l'accès à des secteurs nécessitant un déplacement du bras. Le clustering est une technique de stockage rassemblant les données susceptibles d'être traitées ensemble dans des secteurs physiquement proches. Le disque est contrôlé par un circuit (le contrôleur de disque) qui offre au système d'exploitation des primitives d'E/S (du type 'Lire_un_Bloc(...) / Ecrire_un_Bloc(...)' ) cachant les détails internes concernant les déplacements du bras et la rotation des plateaux. Pour ce type de périphériques, les E/S sont dites "bufférisées" car les transferts se font bloc par bloc (ex: par secteur). Les primitives d'E/S permettent de manipuler les secteurs du disque (l'unité de transfert) comme étant des tableaux d'octets de taille fixe (ex 512, 1024 ou 4096 octets...). Hidouci W.K. / Généralités / Structures de Fichiers / SFSD / ESI - 2021 4 1.2) Structure des disques SSD Les Disques à base de mémoires flash : ‘Solid State Drive’ (SSD), représentent un nouveau type de MS, de plus en plus utilisés pour leur performance et leur faible consommation d’énergie (relativement aux traditionnels disques magnétiques HDD) C’est des dispositifs de stockage externe à base de mémoires flash de type NAND, ils sont aussi plus robustes que les disques magnétiques car ils ne contiennent pas de composants de mécanique de précision sensibles (comme les têtes de lectures/écritures du HDD) susceptibles de se détériorer en cas de chocs ou de mouvements brusques du périphérique. Ils sont à base, uniquement de semi- conducteurs. Mémoire Flash Flash Flash Flash Flash Volatile Chip Chip Chip Chip Chip Plan Flash Flash Flash Flash Flash Chip Chip Chip Chip Chip Plan Contrôleur Flash Flash Flash Flash Flash Chip Chip Chip Chip Chip Plan La mémoire du SSD est divisée en groupes (ou bloc de pages, de capacité fixe, ex: 256KO) et chaque groupe est composé d’un certain nombre de pages (ex. taille d’une page = 4KO). groupe page1 page2 page3 page4... page64 Il y a trois opérations possibles : - Lire une page ⇒ très rapide (20 microsecondes, pour les disques actuels) - Ecrire une page, à condition qu’elle soit dans un état effacé ⇒ rapide (100 à 200 microsecondes) - Effacer toute les pages d’un groupe (un bloc de pages) ⇒ lente (quelques millisecondes) Les groupes (ou blocs de pages) supportent un nombre fixe d’effacements, au delà duquel ils deviennent inutilisables. Il faut donc répartir de manière uniforme les effacements sur l’ensemble des groupes du SSD ⇒ C’est la technique du Wear-Leveling Lors d’une mise à jour du contenu d’une page, il est préférable d’écrire le nouveau contenu dans une nouvelle page (déjà effacée). Les numéros de pages physiques doivent donc être cachés des utilisateurs, car ils sont utilisés de manière interne, par le contrôleur du SSD pour retrouver les derniers contenus des pages manipulées par les applications. Ces dernières identifient donc les pages à travers des numéros logiques (qui restent constants et indépendants des localisations physiques des pages sur la mémoire flash). Le contrôleur maintient une ‘table’ de correspondance entre les numéros logiques et Hidouci W.K. / Généralités / Structures de Fichiers / SFSD / ESI - 2021 5 physiques des différentes pages du SSD (c’est la FTL). A chaque écriture d’une page (dans un nouveau emplacement physique), la FTL est mise-à-jour en conséquence pour garder le lien entre le numéro logique de la page (qui reste inchangé) et le nouveau numéro physique utilisé. 2) Notion de fichier et système de fichiers Pour faire abstraction de ces détails physiques (liés aux dispositifs utilisés : HDD, SSD,...), on considère la mémoire secondaire comme une grande zone de stockage formée de blocs physiques de même taille fixe. Selon le type de la MS, le bloc physique, au niveau du système d’exploitation, peut être composé d’un ou de plusieurs secteurs d’un HDD ou alors d’une ou de plusieurs pages d’un SSD. Chaque bloc physique représente donc un tableau d'octets pouvant être lu ou écrit en une seule opération d'accès (ou d’E/S physique) : LireBloc(num, Buf) et EcrireBloc(num, Buf). L'accès à la mémoire secondaire ne peut se faire qu'à travers ces deux opérations de base. L’opération LireBloc( i ,buf ) effectue le transfert physique du contenu du bloc numéro i (de la MS) vers une zone en MC (la variable buf) ayant la même taille qu’un bloc. L’opération EcrireBloc( i ,buf ) effectue le transfert physique du contenu de la variable buf (en MC) vers le bloc numéro i de la MS. Ces deux opérations d’E/S physiques sont très coûteuses (en terme de temps d’exécution) par rapport aux accès à la mémoire centrale, car elles engendrent des transferts de données vers des dispositifs externes (les disques). 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: i) Au 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), …). On peut aussi définir un fichier comme étant une suite d'octets, on parle alors de flux (ex : les streams de la librairie standard du langage C : FILE * ). C'est des fichiers « non typés ». Ces flux (streams) généralisent la notion d'E/S pour être indépendante du type de périphérique utilisé (disques, imprimantes, écrans, clavier, réseaux, …). Fichier (niveau applicatif) Fichier typé Fichier non typé (suite d'enregistrements) (flux d'octets ) Dans le cas des fichiers typés, les enregistrements (ou articles) sont formés par un ensemble de champs (ou attributs). Parmi ces champs, un ou plusieurs peuvent jouer le rôle de clé de recherche (Search Key). Ce sont le ou les champs utilisés généralement pour rechercher des enregistrements dans les applications (ex : matricule d'un étudiant, nom d'une personne, … etc). Pour faciliter Hidouci W.K. / Généralités / Structures de Fichiers / SFSD / ESI - 2021 6 certaines opérations sur les fichiers, on peut ordonner les enregistrements selon les valeurs de la clé (on parle alors de fichier ordonné). ii) Au 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. L'accès aux contenus des blocs se fait via les opérations d'E/S bufférisées (LireBloc et EcrireBloc). Enreg1 Enreg4 Enreg7 Enreg n-2 Enreg2 Enreg5 Enreg8 Enreg n-1 Enreg3 Enreg6 Enreg9 Enreg n Fichier = ensemble de blocs physiques Dans les deux cas, le fichier possède des propriétés ou caractéristiques permettant de le gérer de manière correcte, telles que le nom, la taille, l'organisation interne, la date de la dernière mise-à- jour, celle de la dernière consultation, le propriétaire, les droit d'accès,...etc. 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. Ainsi, si par exemple, une application demande la lecture d'un enregistrement donné, le 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 directement transmis à l'application, sans qu'il y ait de lecture physique en mémoire externe. Sinon, l'application est mise en attente et une opération de lecture physique de bloc est engagée afin de récupérer d'abord le bloc en MC et ensuite l'enregistrement cherché. Lors de la lecture physique d'un bloc, le système cherche un emplacement libre dans la zone tampon pour y copier le contenu du bloc lu. S'il n'y a pas d'emplacement libre, le système choisit un des blocs déjà présents en zone tampon et le recopie, éventuellement, sur disque (EcrireBloc) avant de l'écraser par le contenu du nouveau bloc. Le choix du bloc à écraser dépend de la stratégie de remplacement adoptée par le système. Lors de la mise à jour d'un enregistrement par une application, le système réalise l'opération directement dans sa zone tampon (en MC). L'écriture physique sur disque ne se fera que plus tard (lors d'un remplacement de bloc par exemple). Périodiquement, le système synchronise son cache avec la MS. Tous les blocs qui ont été modifiés dans la zone tampon, seront alors physiquement écrits en MS lors de l'opération de synchronisation. En cas de panne provoquant la perte de la mémoire centrale (donc de la zone tampon aussi), les dernières modifications effectués sur les fichiers ouverts, risquent donc d'être perdues. Hidouci W.K. / Généralités / Structures de Fichiers / SFSD / ESI - 2021 7  Prog1 manip. E E E E E E E E E E/S Prog2 Physiques E MC manip. F F F F F Prog3 E F manip. F Buffer cache F F MS Pour les applications critiques, il existe des moyens pour forcer l'écriture physique (sans attendre la synchronisation périodique du cache). Dans les systèmes de type Unix, l'appel système 'fsync( f )' permet d'écrire physiquement sur la MS, tous les blocs modifiés de la zone tampon et non encore synchronisés, relatifs au fichier f. Caractéristiques et bloc d'en-tête 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,... Ces informations (ou certaines de ces informations) sont stockées à certains endroits réservé du disque. Par exemple, pour un système de fichier très simple, le bloc se trouvant à une adresse fixe du disque, pourrait être réservé par le système pour contenir une table où chaque ligne renseigne sur les caractéristiques d'un fichier (nom, taille, blocs utilisés,...). Quand une application désire ouvrir un fichier de nom donné, le système récupère ses informations à partir de cette table. Dans les MS séquentielles de type bandes magnétiques, ce type d'information (les caractéristiques) se trouvait au début de chaque fichier (d'où le nom de "bloc d'en-tête"). Certaines applications ont besoin aussi de gérer des caractéristiques particulières pour pouvoir manipuler correctement leurs fichiers de données. Ces caractéristiques là, pourront par exemple être stockées aussi en début de fichier, avant les données à proprement parler. Méthode d'accè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. Cela inclus par exemple de définir : - une manière d'organiser les blocs du fichier sur MS - le placement des enregistrements à l'intérieur des blocs - les caractéristiques et informations nécessaires pour manipuler le fichier - le nombre de buffers à réserver en MC pour optimiser les accès - l'implémentation des opérations d'accès (recherche, insertion, suppression, …) Le but des structures de fichiers est d'optimiser les performances d'accès (temps d'exécution et occupation mémoire). Hidouci W.K. / Généralités / Structures de Fichiers / SFSD / ESI - 2021 8 3) Modèle pour les structures de fichiers 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 contiguë de blocs numérotés séquentiellement (ces numéros représentent les adresses de blocs). Les blocs sont des zones contiguës de même taille, renfermant, entre autre, les données (enregistrements ou simple suite d’octets) des fichiers. Dans le schéma suivant, la MS contient trois fichiers : E, F et G G1 E1 E2 E3 E4 G6 F1 F2 F3 F4 F5 F6 F7 G4 G5 G2 G3 Le fichier E est formé de 4 blocs contigus (E1, E2, E3 et E4), le fichier F est formé de 7 blocs contigus et le fichier G est une liste de blocs. Pour écrire des algorithmes sur les structures de fichiers on utilisera la machine abstraite définie par le modèle suivant: {Ouvrir, Fermer, LireDir, EcrireDir, Aff_Entete, Entete, Allocbloc } Dans ce modèle, on manipule des numéros de blocs relatifs au début de chaque ficher (c’est donc des numéros logiques). L'utilisation des adresses physiques n'est pas d'une utilité particulière à ce niveau de la présentation. Dans ce modèle, un fichier est donc un ensemble de blocs numérotés logiquement (1, 2, 3,... n) Déclaration d'un fichier f et de ses zones tampons buf1, buf2 (deux buffers) : TypeBloc = Structure // le contenu des blocs tab : Tableau [ b ] de TypeEnreg NB : eniter fin f : FICHIER de TypeBloc BUFFER buf1, buf2 ENTETE (type1, type2,...typem); Dans cette déclaration, il y a : La description du contenu des blocs (un tableau d’enregistrement et un entier) La variable f de type FICHIER Deux variables buf1 et buf2, de type 'TypeBloc' qui servent comme zones tampons pour lire et écrire les blocs du fichier. La structure de l'entête du fichier, formée par m caractéristiques dont les types sont spécifiés Hidouci W.K. / Généralités / Structures de Fichiers / SFSD / ESI - 2021 9 Les opérations du modèle sont : Ouvrir( f, nomfichier, mode ) Ouverture ou création d’un fichier de nom nomfichier, selon la valeur de mode ‘A’ : Ouverture d’un ancien fichier en lecture/écriture. Ses caractéristiques sont chargés en MC (par exemple à partir du bloc d’entête du fichier). ‘N’ : Création d’un nouveau fichier en lecture/écriture. Une zone en MC est allouée pour contenir ses caractéristiques, initialisées par des valeurs adéquates. Fermer( f ) Fermeture du fichier f, en sauvegardant ses caractéristiques sur disque (par exemple dans le bloc d’entête) en cas de modifications. LireDir(F, i, buf ) Lecture du bloc numéro i du fichier f dans la variable buf. EcrireDir( F, i, buf ) Ecriture du contenu de la variable buf dans le bloc numéro i du fichier f. Entete( f, i ) Cette fonction retourne la valeur de la ième caractéristique de f. Elle ne nécessite pas d'accès disque car les caractéristiques ont déjà été chargés en MC par l’opération d’ouverture. Aff_entete( f, i, val ) Affecte la valeur val dans la ième caractéristique de f. Elle ne nécessite pas d'accès disque car l’affectation se fait en MC dans la zone déjà allouée par l’opération d'ouverture du fichier. AllocBloc( f ) Allocation d’un nouveau bloc au fichier f. Cette fonction retourne le numéro du bloc alloué. Dans les fichiers formés par des blocs contigus, cette opération n'est pas nécessaire, car l'écriture dans un bloc juste après la fin du fichier est suffisante et est équivalente à une allocation de bloc. 4) Les fichiers en langage C En langage C les fichiers sont vus comme une suite d'octets en MS. Dans la librairie standard (libc) il existe des fonctions portables manipulant les fichiers sous forme de flux à travers la structure FILE définie dans. Les objets de type FILE seront alloués et libérés par les fonctions de la librairie de manière transparente au programme utilisateur. De ce fait on manipule cette structure qu’à travers des indirections (pointeurs). Pour déclarer une variable fichier (de type flux): FILE *f; Pour ouvrir un fichier: f = fopen(nomfichier, mode); nomfichier une chaîne de caractères indiquant le nom du fichier et mode une chaîne de caractères indiquant le mode d'ouverture. Hidouci W.K. / Généralités / Structures de Fichiers / SFSD / ESI - 2021 10  Pour un fichier texte, le mode peut être : mode explications «r» ouverture en lecture «w» création d'un nouveau fichier (écrasement de l'ancien s'il existe déjà) «a» ouverture en mode « ajout » « r+ » ouverture en lecture/écriture « w+ » création d'un nouveau fichier en lecture/écriture « a+ » ouverture en mode « ajout » en lecture/écriture Pour un fichier binaire, le mode peut être : mode explications « rb » ouverture en lecture « wb » création d'un nouveau fichier (écrasement de l'ancien s'il existe déjà) « ab » ouverture en mode « ajout » « rb+ » / « r+b » ouverture en lecture/écriture « wb+ » / « w+b » création d'un nouveau fichier en lecture/écriture « ab+ » / « a+b » ouverture en mode « ajout » en lecture/écriture Un fichier texte est formé d'un ensemble de lignes terminées chacune par une marque de fin de ligne. Dans les systèmes de type Unix (comme Linux par exemple), cette marque de fin de ligne est le caractère '\n' (code ascii 10). Dans d'autres systèmes, la marque de fin de ligne peut être composée de deux caractères (comme '\r' et '\n'). Les fonctions de lecture et d'écriture sur les fichiers textes, permettent de s'abstraire de ces différences entre systèmes. Un fichier binaire est simplement une suite d'octets sans aucune interprétation particulière faite par le système. Ces suites d'octets représentent les données telle qu'elles étaient représentées en MC avant leur transfert sur le fichier. De ce fait les données d'un fichier binaire sont très dépendantes du système où elles ont été produites (donc généralement peu portables). Pour fermer un fichier: fclose(f); Pour savoir si on a dépassé la fin de fichier (en mode lecture) : feof( f ) Retourne vrai (entier différent de 0) si on a tenté de lire au delà de la fin de fichier. Donc le schéma général pour lire le contenu d'un fichier est le suivant : FILE *f ; f = fopen(...) ; > while ( ! feof( f ) ) { // Traitement des données lus... ; > } fclose( f ) ; Hidouci W.K. / Généralités / Structures de Fichiers / SFSD / ESI - 2021 11 a) Lecture / Ecriture en mode binaire Pour lire des données d'un fichier binaire, on utilise généralement 'fread' : nbelt_lus = fread(buf, taille_elt, nb_elt, f); Demande de lecture d'un nombre d'éléments consécutifs égal à nb_elt, chacun de taille taille_elt octets depuis le fichier f. Le résultat de la lecture sera placé dans la zone pointée par buf et de taille au moins égale à taille_elt * nb_elt octets. La fonction retourne le nombre d'éléments effectivement lus, qui peut donc être inférieur au nombre demandé (en cas de fin de fichier ou d'erreur de lecture) Pour écrire des données dans un fichier binaire, on utilise généralement 'fwrite' : nbelt_ecr = fwrite(buf, taille_elt, nb_elt, f); Demande d'écriture d'un nombre d'éléments égal à nb_elt, chacun de taille taille_elt octets dans le fichier f. Les octets à écrire (au nombre de taille_elt*nb_elt) sont à récupérer depuis la zone pointée par buf. La fonction retourne le nombre d'éléments effectivement écrits, qui peut donc être inférieur au nombre demandé (en cas d'erreur d'écriture). Pour modifier la position courante dans un fichier, on peut utiliser 'fseek' : fseek( f, deplacement, origine ) ; Déplace la position courante d'un nombre d'octets égal à deplacement, relativement à : - début du fichier, si origine vaut SEEK_SET - position courante, si origine vaut SEEK_CUR - fin du fichier, si origine vaut SEEK_END b) Lecture / Ecriture en mode texte Pour lire un caractère dans un fichier texte, on peut utiliser : c = fgetc( f ); Lit et retourne (type int) le prochain caractère de f ou bien la constante EOF si la fin de fichier a été dépassée. En cas d'erreur EOF est aussi retournée. Pour écrire un caractère dans un fichier texte, on peut utiliser : fputc( c, f ); Ecrit le caractère c à la position courante du fichier f. En cas d'erreur, la fonction retourne (type int) la constante EOF. Pour lire une ligne dans un fichier texte, on peut utiliser : fgets( buf, n, f ); Lit dans la variable buf, tous les caractères à partir de la position courante de f, jusqu'à trouver une marque de fin de ligne '\n' (qui est aussi lue dans buf) ou alors jusqu'à ce que n-1 caractères soient lus. Un caractère de fin de chaîne '\0' est rajouté à la fin de buf. En cas d'erreur ou de dépassement de la fin de fichier, la fonction fgets retourne NULL. Hidouci W.K. / Généralités / Structures de Fichiers / SFSD / ESI - 2021 12 Pour écrire une chaîne de caractères dans un fichier texte, on peut utiliser : fputs( buf, f ); Ecrit tous les caractères contenus de buf (sauf le '\0') dans le fichier f, à partir de la position courante. Pour écrire une ligne, il faut prévoir un caractère '\n' à la fin de buf (et avant le caractère de fin de chaîne '\0'). En cas d'erreur, la fonction retourne (type int) EOF. Pour effectuer une lecture formatée depuis un fichier texte, on peut utiliser : fscanf( f, format, &var1, &var2, … ) Comme scanf, sauf que les données proviennent du fichier texte f (au lieu de la console) Pour effectuer une écriture formatée dans un fichier texte, on peut utiliser : fprintf( f, format, exp1, exp2, … ) Comme printf, sauf que les données iront dans le fichier texte f (au lieu de la console) c) Exemples de programmes C Dans le programme suivant, on construit un fichier binaire contenant un certain nombre d'enregistrements pour une application simple de gestion d'agenda téléphonique : #include int main() { // variable enregistrement struct Tenreg { char nom; char tel; } e; // variable fichier FILE *f; char nomf; printf( "\nConstruction d'un fichier agenda telephonique\n\n"); printf( "Donnez le nom du fichier à construire : "); // un espace avant %s permet de sauter tous les caractères blancs avant de lire le nom de fichier scanf( " %s", nomf ); // creation du nouveau fichier en mode binaire f = fopen( nomf, "wb" ); if ( f == NULL ) { printf( "erreur lors de l'ouverture du fichier %s en mode wb\n", nomf ); return 0; } Hidouci W.K. / Généralités / Structures de Fichiers / SFSD / ESI - 2021 13  // lecture d'un enregistrement depuis la console printf( "donnez un nom et un tel (ou 0 0 pour terminer le programme) : " ); // un espace avant %s permet de sauter tous les caractères blancs avant de lire les données e.nom et e.tel scanf( " %s %s", e.nom, e.tel ); while ( e.nom != '0' ) { // écriture dans le fichier fwrite( &e, sizeof(e), 1, f ); // lecture d'un enregistrement depuis la console printf( "donnez un nom et un tel (ou 0 0 pour terminer le programme) : " ); // un espace avant %s permet de sauter tous les caractères blancs avant de lire les données e.nom et e.tel scanf( " %s %s", e.nom, e.tel ); } // fermeture du fichier fclose( f ); return 0; } Voici un exemple de programme qui parcourt séquentiellement le fichier de données et affiche son contenu : #include int main() { // variable enregistrement struct Tenreg { char nom; char tel; } e; // variable fichier FILE *f; char nomf; int n, i; printf( "\nAffichage du contenu d'un fichier agenda telephonique\n\n" ); printf( "Donnez le nom du fichier à lister : " ); // un espace avant %s permet de sauter tous les caractères blancs avant de lire le nom de fichier scanf( " %s", nomf ); // ouverture du fichier f = fopen( nomf, "rb" ); if ( f == NULL ) { printf( "erreur lors de l'ouverture du fichier %s en mode rb\n", nomf ); return 0; } Hidouci W.K. / Généralités / Structures de Fichiers / SFSD / ESI - 2021 14  // lecture des enregistrements depuis le fichier i = 1; n = fread( &e, sizeof(e), 1, f ); if ( n == 1 ) // si le nombre d'enreg lus = 1 printf( "%3d nom : %s \t tel : %s\n", i++, e.nom, e.tel ); while ( ! feof(f) ) { n = fread( &e, sizeof(e), 1, f ); if ( n == 1 ) // si le nombre d'enreg lus = 1 printf( "%3d nom : %s \t tel : %s\n", i++, e.nom, e.tel ); } // fermeture du fichier fclose( f ); return 0; } Le programme suivant montre un exemple d'accès direct (avec fseek) à un enregistrement de position donnée : #include int main() { // variable enregistrement struct Tenreg { char nom; char tel; } e; // variable fichier FILE *f; char nomf; int n, i; printf( "\nAccès direct au contenu d'un fichier 'agenda telephonique'\n\n" ); printf( "Donnez le nom du fichier à manipuler : " ); scanf( " %s", nomf ); // ouverture du fichier f = fopen( nomf, "rb" ); if ( f == NULL ) { printf( "erreur lors de l'ouverture du fichier %s en mode rb\n", nomf ); return 0; } printf( "Donnez le numéro de l'enregistrement à lire : " ); // un espace avant %d permet de sauter tous les caractères blancs avant de lire la donnée i scanf( " %d", &i ); // lecture d'un enregistrement par un accès direct fseek( f, (i-1)*sizeof(e), SEEK_SET ); n = fread( &e, sizeof(e), 1, f ); Hidouci W.K. / Généralités / Structures de Fichiers / SFSD / ESI - 2021 15  if ( n == 1 ) // si le nombre d'enreg lus = 1 printf( "enreg num:%3d \t nom : %s \t tel : %s\n", i, e.nom, e.tel ); // fermeture du fichier fclose( f ); return 0; } Si on avait opté pour un fichier texte, on aurait eu le programme suivant pour la construction : #include int main() { // variable enregistrement struct Tenreg { char nom; char tel; } e; // variable fichier FILE *f; char nomf; printf("\nConstruction d'un fichier agenda telephonique\n\n"); printf("Donnez le nom du fichier à construire : "); // un espace avant %s permet de sauter tous les caractères blancs avant de lire le nom de fichier scanf(" %s", nomf); // creation du nouveau fichier en mode texte f = fopen( nomf, "w" ); if ( f == NULL ) { printf( "erreur lors de l'ouverture du fichier %s en mode w\n", nomf ); return 0; } // insertion des enregistrements lus à la console printf( "donnez un nom et un tel (ou 0 0 pour terminer le programme) : " ); // un espace avant %s permet de sauter tous les caractères blancs avant de lire les données e.nom et e.tel scanf( " %s %s", e.nom, e.tel ); while ( e.nom != '0' ) { // écriture formatée dans le fichier fprintf( f, " %s , %s\n", e.nom, e.tel ); // un enregistrement par ligne printf( "donnez un nom et un tel (ou 0 0 pour terminer le programme) : " ); scanf( " %s %s", e.nom, e.tel ); } // fermeture du fichier fclose( f ); return 0; } Hidouci W.K. / Généralités / Structures de Fichiers / SFSD / ESI - 2021 16 Voici un exemple de fichier texte produit par ce programme : $ cat agenda1.txt aaaaaa , 123456 bbbbb , 147258 ccccccc , 187456 ddd , 054963 eeeeee , 248269 fffff , 321654 Le programme suivant permet de lire séquentiellement le fichier ainsi construit et affiche les enregistrements à l'écran : #include int main() { // variable enregistrement struct Tenreg { char nom; char tel; } e; // variable fichier FILE *f; char nomf; int n, i; printf( "\nAffichage du contenu d'un fichier agenda telephonique\n\n" ); printf( "Donnez le nom du fichier à lister : " ); scanf( " %s", nomf ); // ouverture du fichier texte en mode lecture f = fopen( nomf, "r" ); if ( f == NULL ) { printf( "erreur lors de l'ouverture du fichier %s en mode r\n", nomf ); return 0; } // lecture des enregistrements depuis le fichier i = 1; n = fscanf( f, "%s , %s", e.nom, e.tel ); if ( n == 2 ) // si le nombre d'elements lus = 2 (le nom et le tel) printf( "%3d \t nom : %s \t tel : %s\n", i++, e.nom, e.tel ); while ( ! feof(f) ) { n = fscanf( f, "%s , %s", e.nom, e.tel ); if ( n == 2 ) // si le nombre d'elements lus = 2 (le nom et le tel) printf( "%3d \t nom : %s \t tel : %s\n", i++, e.nom, e.tel ); } // fermeture du fichier fclose( f ); return 0; } Hidouci W.K. / Généralités / Structures de Fichiers / SFSD / ESI - 2021 17 Voici un exemple d'affichage produit par ce programme : Affichage du contenu d'un fichier agenda telephonique Donnez le nom du fichier à lister : agenda1.txt 1 nom : aaaaaa tel : 123456 2 nom : bbbbb tel : 147258 3 nom : ccccccc tel : 187456 4 nom : ddd tel : 054963 5 nom : eeeeee tel : 248269 6 nom : fffff tel : 321654 Les écritures forcées en C Les opérations de lecture/écriture du langage C utilisent des buffers additionnels comme une zone tampon entre le programme d'application et le buffer cache du système (voir la figure en début de page 8 de ce même chapitre « Généralités »). Lors des écritures effectuées par un programme (par exemple à l'aide de fwrite) les données sont d'abord envoyées vers ces buffers applicatifs jusqu'à devenir pleins auquel cas ils seront ensuite automatiquement vider vers les blocs de la zone tampon du système (toujours en MC). Au moment de la synchronisation du cache système, les données seront alors physiquement écrites sur MS. Lors de la fermeture d'un fichier (fclose) les buffers applicatifs sont aussi vider vers la zone tampon du système. L'opération fflush(f) permet aussi de forcer le vidage du buffer applicatif de f vers la zone tampon système (en MC), même s'il n'était pas plein. Donc pour réaliser une écriture forcée (écriture physique vers la MS), il faut d'abord vider le buffer applicatif (fflush) et ensuite synchroniser le cache système (fsync). Ces écritures forcée sont quelquefois nécessaires pour mettre à l’abri des données critiques en les sauvegardant en MS avant l’occurrence d’une éventuelle panne qui pourrait effacer le contenu de la MC et donc des buffers non encore synchronisés par le système d’exploitation. 5) Conclusion Les prochains chapitres concernent les différents types d'organisations de fichiers et l'étude de leur impacts sur les performances. Ce sont les "méthodes d'accès". Voici quelques exemples d'organisations de fichier: - blocs contigus, enregistrements à taille fixe, non ordonné - liste de blocs, enregistrements à taille variable, ordonné - ensemble de blocs avec table d'index,... - arbre de blocs.... - blocs contigus avec fonction de hachage,... Certaines méthodes d'accès sont très simples, mais limitées à des fichiers de petite taille, d'autres donnent de bonnes performances à condition que la taille du fichier ne change pas beaucoup (fichiers statiques) et enfin il y en a qui donnent de bonnes performances même avec des fichiers volumineux et dynamique (B-Arbres, Hachage dynamique) Hidouci W.K. / Généralités / Structures de Fichiers / SFSD / ESI - 2021 18  Structures de Fichiers Chapitre 2 Les Structures Séquentielles 1) Organisation globale des blocs 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 » : les blocs ne sont pas forcément contigus, mais sont chaînés entre eux. Dans la figure ci-dessous, on a deux fichiers vus comme tableau (E et F) et un fichier vu comme une liste (G). Les blocs F1, F2, … F7 sont contigus, de même pour les blocs E1, E2, E3 et E4. Par contre les blocs G1, G2, … G6 ne sont pas contigus, ils sont chaînés entre eux formant une liste de blocs. G1 E1 E2 E3 E4 G6 F1 F2 F3 F4 F5 F6 F7 G4 G5 G2 G3 Parmi les caractéristiques nécessaires pour manipuler un fichier vu comme tableau, on pourra avoir par exemple : - Le numéro du premier bloc, - Le numéro du dernier bloc (ou alors le nombre de blocs utilisés). Pour un fichier vu comme liste, il suffirait par contre de connaître le numéro du premier bloc (la tête de la liste), car dans chaque bloc, il y a le numéro du prochain bloc (comme le champ suivant dans une liste). Dans le dernier bloc, le numéro du prochain bloc pourra être mis à une valeur spéciale (par exemple -1) pour indiquer la fin de la liste. 2) 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. Hidouci W.K. / Les structures séquentielles / Structures de Fichiers (SFSD) / ESI - 2021 19 Exemple: Type Tenreg = structure // structure d'un enregistrement du fichier matricule : chaine(10); nom : chaine(20); age : entier;... fin; Type Tbloc = structure // structure d'un bloc du fichier tab : tableau[ b ] de Tenreg; // un tableau pouvant contenir (au max) b enreg. NB : entier; // nombre d'enreg insérés dans tab (entre 0 et b). fin; Si on opte pour des enregistrements de tailles variables, chaque enregistrement sera vu comme étant une chaîne d’octets ou de caractères (de longueur variable). Les enregistrements peuvent être de longueur variable pour différentes raisons. Par exemple, il y a un ou plusieurs champs de tailles variables dans la structure d’un enregistrement, ou alors le nombre de champs varie d'un enregistrement à un autre, … etc. On peut représenter les valeurs à taille variable par des espaces de taille fixe (au risque d’une perte importante de l’espace de stockage), mais ce n’est pas toujours possible de le faire, car dans certaines situations, on ne connaît pas la taille maximale que peut prendre une valeur donnée. Pour séparer les champs entre eux (à l'intérieur de l'enregistrement), on pourra soit utiliser un caractère spécial, soit préfixer le début des champs par leur taille. Dans l'exemple ci-dessous, on utilise trois (03) positions pour indiquer la taille des champs....|0|2|7|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|0|1|7|b|b|b|b|b|b|b|b|b|b|b|b|b|b|0|3|7|c|c|c|.......|c|c|..... un champ sur 27 caractères un champ sur 17 caractères ….. En utilisant un nombre fixe de positions pour représenter la taille, on a de ce fait limiter la taille maximale de la valeur. Dans l’exemple précédent, avec 3 positions, cela implique que la taille maximale d’un champ ne peut pas dépasser 999 caractères (ou octets). Si par contre la taille maximale n’est pas connue au moment de la conception de la méthode, on peut représenter la taille sur un nombre variable de positions terminée par un caractère spécial. Dans le cas d'enregistrements à taille variable, le bloc ne peut pas être défini comme étant un tableau d'enregistrements, car les éléments d'un tableau doivent toujours être de même taille. La solution est alors de considérer le bloc comme étant (ou contenant) un grand tableau de caractères de taille fixe, renfermant les différents enregistrements (stockés caractère par caractère). Pour séparer les enregistrements entre eux, on utilise les mêmes techniques que celles utilisées dans la séparation entre les champs d'un même enregistrement (soit avec un caractère spécial '$', soit on préfixe chaque enregistrement par sa taille). Voici un exemple de déclaration d'un type de bloc pouvant être utilisé dans la définition d'un fichier vu comme liste avec format (taille) variable des enregistrements. Hidouci W.K. / Les structures séquentielles / Structures de Fichiers (SFSD) / ESI - 2021 20 Type Tbloc = structure tab : tableau[ b' ] de caractères; // tableau de caractères pour les enreg. suiv : entier; // numéro du bloc suivant dans la liste fin; Remarque: Même si les enregistrements sont de longueurs variables, la taille des blocs reste toujours fixe. Pour minimiser l'espace perdu dans les blocs (dans le cas : format variable uniquement), on peut opter pour une organisation avec chevauchement entre deux ou plusieurs blocs: Quand on veut insérer un nouvel enregistrement dans un bloc non encore plein et où l'espace vide restant n'est pas suffisant pour contenir entièrement cet enregistrement, celui-ci sera découpé en 2 parties de telle sorte à occuper tout l'espace vide du bloc en question par la 1ere partie, alors que le reste (la 2e partie) sera insérée dans un nouveau bloc alloué au fichier. On dit alors que l'enregistrement se trouve à cheval entre 2 blocs. On peut facilement généraliser cette approche pour supporter des enregistrements à cheval sur plusieurs blocs (c’est le cas des enregistrements de grandes tailles, éventuellement supérieure à celle d’un bloc physique) 3) Taxonomie des structures simples de fichiers En combinant d’une part, entre l'organisation globale des fichiers (vu comme tableau ou vu comme liste) et celle interne aux blocs (format fixe ou variable des enregistrements) et d’autre part, en considérant la possibilité de maintenir le fichier ordonné ou non, on peut définir une classe de méthodes d'accès (dites « séquentielle ») pour organiser des données sur disque. 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 séquentielles: structures séquentielle T L O O O O F V F V F V F V C C C C C C C C 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) : 1 2 3 N Hidouci W.K. / Les structures séquentielles / Structures de Fichiers (SFSD) / ESI - 2021 21 La recherche est séquentielle, l'insertion en fin de fichier et la suppression est logique. 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) : tête tab nb suiv tab nb suiv tab nb suiv -1 tab nb suiv 1 2 3 4 La recherche est séquentielle, l'insertion provoque des décalages intra-blocs uniquement (pour garder l'ordre des enregistrements) et la suppression peut être logique ou physique. 4) 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 l'opération de réorganisation périodique. Déclaration du fichier: Soit b = 30 // capacité maximale des blocs (en nombre d'enregistrements) // Les types utilisés : Tenreg = structure // Structure d'un enregistrement : effacé : booleen // booléen pour la suppression logique cle : typeqlq // le champs utilisé comme clé de recherche champ2 : typeqlq // les autres champs de l'enregistrement, champ3 : typeqlq // sans importance ici.... Fin Tbloc = structure // Structure d'un bloc : tab : tableau[ b ] de Tenreg // un tableau d'enreg d'une capacité maximal = b NB : entier // nombre d'enreg dans tab ( ≤ b) Fin Hidouci W.K. / Les structures séquentielles / Structures de Fichiers (SFSD) / ESI - 2021 22 // Les variables globales : F et buf F : Fichier de Tbloc Buffer buf Entete (entier, entier) Module de recherche: (dichotomique) en entrée la clé (c) à chercher. en sortie le booleen Trouv, le numéro de bloc (i) contenant la clé et le déplacement (j) Rech( c:typeqlq, var Trouv:bool, var i,j:entier ) var bi, bs, inf, sup : entier trouv, stop : booleen DEBUT bs ← entete( F,1 ) // la borne sup (le num du dernier bloc de F) bi ← 1 // la borne inf (le num du premier bloc de F) // boucle pour la recherche dichotomique externe (dans le fichier F) Trouv ← faux; stop ← faux; j ← 1 TQ ( bi ≤ bs et Non Trouv et Non stop ) i ← (bi + bs) div 2 // le bloc du milieu entre bi et bs LireDir( F, i, buf ) SI ( c ≥ buf.tab.cle et c ≤ buf.tab[ buf.NB ].cle ) // boucle pour la recherche dichotomique interne dans le bloc i (dans buf) inf ← 1; sup ← buf.NB TQ (inf ≤ sup et Non Trouv) // recherche interne j ← (inf + sup) div 2 SI (c = buf.tab[ j ].cle) Trouv ← vrai SINON SI (c < buf.tab[ j ].cle) sup ← j-1 SINON inf ← j+1 FSI FSI FTQ SI ( inf > sup ) j ← inf FSI // fin de la recherche interne. // j : la position où devrait se trouver c dans buf.tab stop ← vrai SINON // non ( c ≥ buf.tab.cle et c ≤ buf.tab[ buf.NB ].cle ) SI ( c < buf.tab.cle ) bs ← i-1 SINON // donc c > buf.tab[ buf.NB ].cle bi ← i+1 FSI FSI FTQ SI ( bi > bs ) i ← bi ; j ← 1 FSI // fin de la recherche externe. // i : num du bloc où devrait se trouver c FIN // Recherche Hidouci W.K. / Les structures séquentielles / Structures de Fichiers (SFSD) / ESI - 2021 23 Le coût de l’opération de recherche est logarithmique car la recherche dichotomique effectue, dans le cas le plus défavorable, log2 N lectures de blocs pour un fichier formé de N blocs. La complexité est O( log N). Module d'insertion: (avec éventuellement des décalages intra et inter blocs) Inserer( e:Tenreg , nomfich:chaine ) var trouv : booleen i,j,k : entier e,x : Tenreg DEBUT Ouvrir( F,nomfich, 'A') // on commence par rechercher la clé e.cle avec le module précédent pour localiser l'emplacement (i,j) // où doit être insérer e dans le fichier. Rech( e.cle, nomfich, trouv, i, j ) SI ( Non trouv ) // e doit être inséré dans le bloc i à la position j continu ← vrai // en décalant les enreg j, j+1, j+2,... vers le bas // si i est plein, le dernier enreg de i doit être inséré dans i+1 TQ ( continu et i ≤ entete(F,1) ) // si le bloc i+1 est aussi plein son dernier enreg sera LireDir( F, i, buf ) // inséré dans le bloc i+2, etc... donc une boucle TQ. // avant de faire les décalages, sauvegarder le dernier enreg dans une var x... x ← buf.tab[ buf.NB ] // décalage à l'intérieur de buf... k ← buf.NB TQ k > j buf.tab[ k ] ← buf.tab[ k-1 ] ; k ← k-1 FTQ // insérer e à la pos j dans buf... buf.tab[ j ] ← e // si buf n'est pas plein, on remet x à la pos NB+1 et on s'arrête... SI ( buf.NB < b ) // b est la capacité max des blocs (une constante) buf.NB ← buf.NB+1 ; buf.tab[ buf.NB ] ← x EcrireDir( F, i, buf ) continu ← faux SINON // si buf est plein, x doit être inséré dans le bloc i+1 à la pos 1... EcrireDir( F, i, buf ) i ← i+1 ; j ← 1 e ← x // cela se fera (l'insertion) à la prochaine itération du TQ FSI // non ( buf.NB < b ) FTQ // si on dépasse la fin de fichier, on rajoute un nouveau bloc contenant un seul enregistrement e SI i > entete( F, 1 ) buf.tab ← e ; buf.NB ← 1 EcrireDir( F, i, buf ) // il suffit d'écrire un nouveau bloc à cet emplacement Aff-entete( F, 1, i ) // on sauvegarde le num du dernier bloc dans l'entete 1 FSI Aff-entete( F, 2 , entete(F,2)+1 ) // on incrémente le compteur d'insertions FSI Fermer( F ) FIN // insertion Hidouci W.K. / Les structures séquentielles / Structures de Fichiers (SFSD) / ESI - 2021 24 L’opération d’insertion peut nécessiter dans le cas le plus défavorable, des décalages inter-blocs qui se propagent jusqu’à la fin du fichier. Comme chaque décalage coûte une lecture et une écriture de bloc (c-a-d 2 accès disques), le coût total d’une insertion, en pire cas, est au voisinage de 2N accès disques pour un fichier formé de N blocs plus le coût de la recherche (log 2 N lectures). La complexité est donc O(N). La suppression logique consiste à rechercher l'enregistrement et positionner le champs 'effacé' à vrai : Suppression( c:typeqlq; nomfich:chaine ) var trouv : booleen i,j : entier DEBUT Ouvrir( F,nomfich, 'A') // on commence par rechercher la clé c pour localiser l'emplacement (i,j) de l'enreg à supprimer Rech( c, nomfich, trouv, i, j ) // ensuite on supprime logiquement l'enregistrement SI ( trouv ) // Après Rech(...) buf contient déjà le contenu du bloc i (ce n’est donc pas la peine de le relire une 2e fois) buf.tab[j].effacé ← VRAI EcrireDir( F, i, buf ) FSI Fermer( F ) FIN // suppression La suppression logique coûte une seule écriture de bloc, en plus du coût de la recherche (log 2 N lectures) pour un fichier de N blocs. La complexité est donc celle de la recherche O( log N ). Le chargement initial d'un fichier ordonné consiste à construire un nouveau fichier contenant dès le départ n enregistrements. Ceci afin de laisser un peu de vide dans chaque bloc, qui pourrait être utilisé plus tard par les nouvelles insertions tout en évitant les décalages inter-blocs (très coûteux en accès disque) : Chargement_Initial( nomfich : chaine; n : entier; u : reel ) // u est un réel dans ]0,1] et désigne le taux de chargement voulu au départ var e : Tenreg i,j,k : entier DEBUT Ouvrir( F, nomfich, 'N' ) // un nouveau fichier i←1 // num de bloc à remplir j←1 // num d'enreg dans le bloc ecrire( 'Donner les enregistrements en ordre croissant suivant la clé : ' ) POUR k←1 , n lire( e ) SI ( j ≤ u*b ) // ex: si u=0.5, on remplira les bloc jusqu'à b/2 enreg buf.tab[ j ] ← e ; j ← j+1 SINON // j > u*b : buf doit être écrit sur disque buf.NB ← j-1 EcrireDir( F, i, buf ) buf.tab ← e // le kème enreg sera placé dans le prochain bloc, à la position 1 i ← i+1 ; j ← 2 FSI FP Hidouci W.K. / Les structures séquentielles / Structures de Fichiers (SFSD) / ESI - 2021 25  // à la fin de la boucle, il reste des enreg dans buf qui n'ont pas été sauvegardés sur disque buf.NB ← j-1 EcrireDir( F, i, buf ) // mettre à jour l'entête (le num du dernier bloc et le compteur d'insertions) Aff-entete( F, 1, i ) Aff-entete( F, 2, n ) Fermer( F ) FIN // chargement-initial Le chargement initial avec n enregistrements, nécessite la création d’un fichier formé de n / (b*u) blocs (donc n / (b*u) écritures ) avec b la capacité maximale d’un bloc et u le facteur de chargement souhaité (un réel entre 0 et 1). La réorganisation du fichier consiste à recopier les enregistrements vers un nouveau fichier de telle sorte à ce que les nouveaux blocs contiennent un peu de vide (1-u). Cette opération ressemble au chargement initial sauf que les enregistrements sont lus à partir de l'ancien fichier. ------------ Fusion de 2 fichiers ordonnés (TOF) On parcourt les 2 fichiers (F1 et F2) en parallèle avec 2 buffers (buf1 et buf2) et on rempli un 3e buffer (buf3) pour construire un 3e fichier (F3) en ordre croissant. Les déclarations sont celles utilisées dans les fichier TOF standards. Fusion (nom1,nom2, nom3: chaine) var F1 : Fichier de Tbloc Buffer buf1 Entete( entier, entier) F2 : Fichier de Tbloc Buffer buf2 Entete( entier, entier) F3 : Fichier de Tbloc Buffer buf3 Entete( entier, entier) i1, i2, i3 : entier j1, j2, j3 : entier continu : booleen e, e1, e2 : Tenreg buf : Tbloc i, j, indic : entier Debut Ouvrir(F1, nom1, 'A' ) Ouvrir(F2, nom2, 'A' ) Ouvrir(F3, nom3, 'N' ) i1←1; i2←1; i3 ←1 // les num de blocs de F1, F2 et F3 j1←1; j2←1; j3 ←1 // les num d'enreg dans buf1, buf2 et buf3 LireDir(F1, 1, buf1) LireDir(F2, 1, buf2) ; continu ← vrai Hidouci W.K. / Les structures séquentielles / Structures de Fichiers (SFSD) / ESI - 2021 26  TQ ( continu ) // tant que non fin de fichier dans F1 et F2 faire SI ( j1 ≤ buf1.NB et j2 ≤ buf2.NB ) // choisir le plus petit enreg, dans buf1 et buf2 e1←buf1.tab[ j1 ] e2 ← buf2.tab[ j2 ] SI ( e1.cle ≤ e2.cle ) e ← e1; j1← j1 + 1 SINON e ← e2; j2← j2 + 1 FSI // et le mettre dans buf3 SI ( j3 ≤ b ) buf3.tab[ j3 ] ← e; j3 ← j3 + 1 SINON buf3.NB ← j3 – 1 EcrireDir(F3, i3, buf3 ) i3 ← i3 + 1 buf3.tab ← e j3 ← 2 FSI SINON // c-a-d : non ( j1 ≤ buf1.NB et j2 ≤ buf2.NB ) // si tous les enreg d'un des blocs (buf1 ou buf2) ont été traités, passer au prochain SI ( j1 > buf1.NB ) SI ( i1 < entete(F1, 1) ) i1 ← i1 + 1 LireDir( F1, i1, buf1 ) j1 ← 1 SINON // ( donc i1 ≥ entete(F1, 1) ) continu ← faux i ← i2 // pour la suite du TQ j ← j2 N ← entete(F2,1) buf ← buf2 Indic ← 2 FSI // ( i1 < entete(F1, 1) ) SINON // c-a-d ( j2 > buf2.NB ) SI ( i2 < entete(F2, 1) ) i2 ← i2 + 1 LireDir( F2, i2, buf2 ) j2 ← 1 SINON // ( donc i2 ≥ entete(F2, 1) ) continu ← faux i ← i1 // pour la suite du TQ j ← j1 N ← entete(F1,1) buf ← buf1 Indic ← 1 FSI // ( i2 < entete(F2, 1) ) FSI // ( j1 > buf1.NB ) FSI // ( j1 ≤ buf1.NB et j2 ≤ buf2.NB ) FTQ Hidouci W.K. / Les structures séquentielles / Structures de Fichiers (SFSD) / ESI - 2021 27  // continuer à recopier les enregistrement d'un seul fichier (i,j,buf) dans F3 continu ← vrai; TQ ( continu ) // tant que non fin de fichier dans F1 ou F2 faire SI ( j ≤ buf.NB ) SI ( j3 ≤ b ) buf3.tab[ j3 ] ← buf.tab[ j ]; j3 ← j3 + 1 SINON buf3.NB ← j3 – 1 EcrireDir(F3, i3, buf3 ) i3 ← i3 + 1 buf3.tab ← buf.tab[ j ]; j3 ← 2 FSI // ( j3 ≤ b ) j←j+1 SINON // c-a-d non ( j ≤ buf.NB ) SI ( i ≤ N ) i ← i + 1; SI ( Indic = 1 ) LireDir( F1, i, buf ) SINON LireDir( F2, i, buf ) FSI j←1 SINON continu ← faux FSI FSI // ( j ≤ buf.NB ) FTQ // Le dernier buffer (buf3) n'a pas encore été ecrit sur disque... buf3.NB ← j3 – 1 EcrireDir( F3 , i3, buf3 ) Aff-entete( F3, 1, i3) // le nombre de blocs dand F3 Aff-entete( F3, 2, entete(F1,1) + entete(F2,1) ) // le nombre d'enregistrements dans F3 Fermer( F1 ) Fermer( F2 ) Fermer( F3 ) Fin L’opération de fusion de 2 fichiers F 1 et F2 de tailles respectives N1 et N2 blocs, nécessite le parcours complet de 2 fichiers (soit N 1 + N2 lectures) et la création du fichier résultat (F 3) formé par N1 + N2 blocs (soit N1 + N2 écritures), en supposant un même facteur de chargement pour les trois fichiers. Le coût total de la fusion est donc 2N1 + 2N2 accès disques. Si les fichiers F1 et F2 était de même taille (N blocs chacun), le coût total de la fusion serait alors de 4N accès disques (2N lectures et 2N écritures). La complexité de la fusion est donc en O(N). Hidouci W.K. / Les structures séquentielles / Structures de Fichiers (SFSD) / ESI - 2021 28  Structures de Fichiers Chapitre 3 Fichiers avec index 1) Introduction Avec les structures de fichiers séquentiels, quand le fichier de données devient volumineux, les opérations d'accès (recherche, insertion,...) deviennent inefficaces. Les méthodes d'index permettent d'améliorer, dans une certaine mesure, les performances en gérant une structure auxiliaire (table d'index) accélérant la recherche d’enregistrements. Un index est (généralement) une table ordonnée en mémoire centrale (MC) contenant principalement des couples < clé , adr >, utilisée pour accélérer la recherche des enregistrements d'un fichier. Le champs 'clé' représente un attribut (ou groupe d’attributs) d’un enregistrements du fichier et utilisé(s) pour la recherche. On appelle ce genre d’attribut une clé de recherche (Search Key). Cela peut être n’importe quel attribut, à valeurs uniques ou non. Le champs 'adr' représente les informations de localisation d’un enregistrement dans le fichier (par exemple : ). On peut aussi mettre dans l’index d'autres informations qui pourraient être utiles pour la gestion du fichier, comme par exemple un booléen indiquant les effacements logiques, la taille occupé par l'enregistrement (surtout dans le cas avec 'format variable'), … etc. Index non dense sur A clé | adr Fichier de données ordonné selon l’attribut A (les enreg sont formés par 3 attributs : A, B et C) a3 | [1 , 3] a7 | [2 , 4] A|B|C A|B|C A|B|C A |B|C A | B |C a9 | [3 , 2] a1, b1, c1 a4, b3, c2 a8, b5, c5 a10, b7, c1 a98, b2, c31 a12 | [4 , 3] a2, b2, c3 a5, b2, c4 a9, b4, c1 a11, b2, c5 a99, b6, c11 … |… a3, b1, c1 a6, b4, c1 a12, b4, c6 … … a99 | [N , 2] a7, b2, c4 1 2 3 4 N Un index est dit « dense » (Non Clustered Index) s'il contient toutes les valeurs de l’attribut clé du fichier de données. Dans ce cas, on n'a pas besoin de garder le fichier ordonné sur cet attribut. Un index est dit « non dense » (Clustered Index) s'il ne contient pas toutes les valeurs de l’attribut clé du fichier de données (par exemple, on ne garde dans l’index qu’une seule valeur par bloc ou groupe de blocs). Dans ce cas le fichier doit être ordonné sur l’attribut indexé. L'avantage d'un index non dense est sa taille (plus petite que celle d'un index dense pour le même fichier de données). Voir schéma ci-dessus. Dans le fichier de données, les valeurs de l’attribut indexé (la clé de recherche) peuvent être uniques (toutes les valeurs sont distinctes), ou alors multiples (non uniques, c-a-d qu’il existe des enregistrements différents pouvant avoir la même valeur pour l’attribut indexé). Dans ce dernier cas, à chaque entrée dans la table d’index est associé une liste d’adresses. On peut aussi dupliquer la Hidouci W.K. / Méthodes d'index / Structures de fichiers (SFSD) / ESI - 2021 29 valeur de l’attribut clé, dans la table d’index, en autant d’entrées que de valeurs multiples, chacune avec son adresse associée. Le schéma ci-dessous montre les deux possibilités de représentation des valeurs multiples (dans cet exemple la clé v se répète dans trois enregistrements localisés aux adresses a1, a2 et a3 du fichier de données). …. …. i v a1 i v a1 a2 a3 i+1 v a2 …. i+2 v a3 …. Table d’index avec une seule entrée par valeur multiple Table d’index avec plusieurs entrées par valeur multiple 2) Méthode avec index à un niveau Pour accélérer les opérations d’accès sur un fichier de données F, on peut maintenir en mémoire centrale (MC) une table d’index portant sur l’attribut (champs) utilisé comme clé de recherche (l’un des attributs des enregistrements de F). S’il existe plusieurs attributs (A1, A2, A3,...) pouvant être utilisés comme des clés de recherche, on peut aussi maintenir plusieurs index différents : IndexA1, IndexA2, IndexA3, … (un sur chaque attribut clé). Si de plus le fichier F est ordonné selon un des attributs clés (par exemple sur A1), l’index associé (IndexA1) sera dit « primaire » ou alors « Clustering Index » et les autres (IndexA2, IndexA3, …) seront « secondaires » ou bien « Non clustering indexes ». Dans ce cas (F est ordonné selon l’attribut A1), IndexA1 sera donc non dense alors que IndexA2, IndexA3, … seront des index denses. Il est à rappeler que dans le cas d’un fichier ordonné, l'opération d'insertion peut être coûteuse à cause des décalages inter-blocs générés. La suppression est généralement logique pour éviter les décalages inverses. Des réorganisations périodiques sont aussi à prévoir. On peut aussi maintenir une zone de débordement pour le fichier de données afin d’éviter les décalages inter-bloc lors des insertions, mais avec le nombre des insertions qui augmente dans le temps, les performances de la recherche se dégradent, malgré la présence de l’index, à cause du parcours séquentiel dans la zone de débordement, nécessitant donc aussi des réorganisations périodiques. - Fichier d’index Pour ne pas avoir à reconstruire la table d'index à chaque démarrage, on peut sauvegarder la table dans un fichier (dit « fichier index ») en fin de traitement par exemple. Celui-ci sera rechargé en MC dans une table lors de la prochaine session. Généralement le chargement de la table d’index depuis un fichier index est beaucoup plus rapide que de reconstruire la table à partir du fichier de données (surtout si ce dernier n’est pas ordonné). Il est à noter que les opérations d’accès au fichier de données (recherche, insertion, suppression …) utilisent uniquement la table d’index en MC et le fichier de données en MS. Le fichier d’index en MS n’est ni consulté, ni mis-à-jour durant ces opérations. Les fichiers de données et d'index peuvent être de n'importe quelle structure (blocs contigus, blocs chaînés,...). De même que les enregistrements peuvent être à format fixe ou variable (avec ou sans chevauchement). La figure ci-dessous montre les différentes structures utilisées dans un exemple de méthode d’accès avec un seul index. Hidouci W.K. / Méthodes d'index / Structures de fichiers (SFSD) / ESI - 2021 30  Table d'index en MC Clé Adr c (i,j) i' j' c' | xxx c' (i', j') i j c | yyy Fichier index (de sauvegarde) en MS Fichier de données en MS Les opérations de base a) Cas d'un fichier de données non ordonné (index dense) : - La recherche d'un enregistrement consiste à faire une recherche dichotomique de sa clé dans la table d'index en MC, si elle existe, on récupère l'enregistrement à partir du fichier de donnée avec un seul accès disque. => coût de l'opération : 1 accès disque (ou moins, si la clé n’existe pas dans l’index). - La requête à intervalle consiste à rechercher tous les enregistrements dont la valeur du champs clé appartient à un intervalle de valeurs donné : [a,b]. 1. On commence par rechercher la plus petite clé ≥ a dans l'index (recherche dichotomique dans la table en MC). 2. Puis on continue séquentiellement dans la table (en MC) jusqu'à trouver une clé > b. 3. Pour chaque clé, on accède au fichier de données pour récupérer le (ou les) enregistrement(s) associés. Ce dernier point peut être amélioré si on tri les numéros de blocs trouvés avant d'accéder au fichier de données (afin de ne pas lire, éventuellement, deux fois le même bloc). => coût de l'opération en nombre d'accès : le nombre d’enregistrements vérifiant la requête (dans le cas le plus défavorable). - L'insertion d'un nouvel enregistrement se fait au niveau du fichier de données selon sa structure et organisation, ensuite la valeur de son attribut indexé (la clé de recherche) est utilisée pour mettre à jour la table d'index (en MC). Si la valeur de la nouvelle clé n’existe pas dans la table, une nouvelle entrée est alors ajoutée à la table (avec les décalages nécessaires pour maintenir l’ordre des valeurs de clé dans la table). Si par contre, la clé existe déjà dans la table (cas des valeurs multiples), la nouvelle localisation de l’enregistrement dans le fichier de données est alors rajoutée à la liste des adresses associée. Hidouci W.K. / Méthodes d'index / Structures de fichiers (SFSD) / ESI - 2021 31 => coût de l'opération : le nombre d’accès disques nécessaires pour l’insertion de l’enregistrement dans le fichier de donnée non ordonné (la m-à-j de la table d’index ne coûte aucun accès disque). - La suppression s’effectue, éventuellement, au niveau du fichier de données (suppression physique ou logique), ensuite la table d'index est mise à jours soit en supprimant (par décalages) l’entrée associée à la valeur de la clé (lorsque la clé est à valeurs uniques), soit en supprimant un élément de la liste des adresses (lorsque la clé est valeurs multiples). Dans ce dernier cas, si la liste des adresses devient vide, l’entrée associée est aussi supprimée de la table par décalages. On peut aussi opter pour positionner uniquement un indicateur d’effacement au niveau de la table d’index pour ne pas avoir à effectuer les décalages en MC. => coût : le nombre d’accès disques nécessaires pour la suppression de l’enregistrement dans le fichier de donnée non ordonné (la m-à-j de la table d’index ne coûte aucun accès disque). b) Cas d'un fichier de données ordonné (donc généralement un index non dense) : Si le fichier de données est ordonné, on peut garder dans la table d'index que certaines valeurs de clé. Par exemple une clé par bloc (ou groupe de blocs), on choisit soit la plus grande ou la plus petite de chaque groupe. C'est alors un index non dense (car il ne contient pas toutes les clés). Cela permet de diminuer considérablement la taille de la table d'index tout en gardant pratiquement les mêmes performances de recherche qu'une méthode d'index avec fichier non ordonné (si le nombre de blocs par groupe est petit, par exemple un bloc par groupe). L'insertion risque par contre d’être coûteuse lorsque le fichier est formé par des blocs contigus (vu comme tableau), à cause des décalages dans le fichier de données s’il n’y a pas de zone de débordement. - La recherche d'un enregistrement consiste à faire une recherche dichotomique dans la table d'index, puis on continue séquentiellement dans un des groupes de blocs du fichier de données. => coût de l'opération : 1 accès disque (si chaque groupe est formé d’un seul bloc). - Pour la requête à intervalle (clé de recherche Î [a,b]), on procède comme suit : 1- On commence par rechercher la plus petite clé ≥ a dans l'index (recherche dichotomique en MC). 2- Puis on accède au fichier de données à partir du numéro de bloc spécifié dans l'index et on continue séquentiellement dans le fichier jusqu'à trouver une clé > b. => coût de l'opération en nombre d'accès se rapproche du nombre de clés vérifiant la requête divisé par la capacité moyenne d’un bloc (c’est un cas favorable). - L'insertion d'un nouvel enregistrement se fait dans le fichier de données ou alors en zone de débordement (voir plus bas un exemple) en utilisant l’algorithme associé à la structure du fichier (vu comme tableau ou comme liste, format fixe ou variable...). La table d'index (en MC) est alors mise à jour à chaque fois que le représentant d’un groupe a changé suite aux déplacements d’enregistrements (les décalages, les éclatement...) occasionnés par l'insertion du nouvel enregistrement dans le fichier. => coût de l'opération : celui de l’insertion dans le fichier de données associé - La suppression est généralement logique dans le fichier de données, sauf dans le cas d’un fichier vu comme liste et sans chevauchement inter-blocs auquel cas la suppression physique devient envisageable (car peu coûteuse). La table d’index est rarement mise-à-jour. => coût : celui de la suppression dans le fichier de données associé Hidouci W.K. / Méthodes d'index / Structures de fichiers (SFSD) / ESI - 2021 32 Gestion d'une zone de débordement Dans le cas d’un fichier ordonné vu comme tableau, une alternatives aux décalages inter-blocs lors des insertions (et des suppressions physiques), serait de maintenir une zone de débordement pour y stocker, de manière simple, les enregistrements expulsés des blocs pleins du fichier de données. A chaque insertion, si le bloc du fichier de données est plein, les enregistrements en surplus, seront insérés dans des blocs de débordements, chaînés au bloc principal pour maintenir l'ordre des clés. Au niveau de la table d'index, on met à jour la clé maximale (le représentant du groupe : la première ou la dernière clé du groupe) si elle vient à changer suite à l'insertion. Les performances reste bonnes tant que la longueur des listes de blocs en débordement reste petite. Lorsque les groupes sont formés d’un seul bloc chacun, les coûts des opérations sont pratiquement les mêmes que dans le cas d'un fichier non ordonné avec index, plus un surcoût égal à la longueur moyenne des listes en débordement.... c1 c1...... c2 c2 c3... c4 c5 c3...... c4 Table d'index non... dense en MC c5 Fichier de données Fichier de données zone primaire zone de débordement Si les blocs en débordement deviennent trop nombreux (les listes s'allongent), il faut réorganiser le fichier en créant un nouveau fichier principal, éventuellement plus grand s’il y a eu beaucoup d’insertions et peu de suppressions, ou alors plus petit dans le cas inverse. La nouvelle zone de débordement sera initialement vide. Autre représentation de l'index en MC On peut aussi représenter l'index en mémoire centrale sous forme d'un arbre de recherche binaire (AVL, Red-Black, …), au lieu d'une table ordonnée. L'avantage est d'éviter les décalages (en mémoire centrale) lors de l'insertion de nouvelles clés ou la suppression de clés dans l'index. L'inconvénient est l’encombrement mémoire plus important à cause des pointeurs (fg, fd,…) associés à chaque nœuds de l’arbre.... c c''... c'... c c''...... c' Index en arbre binaire en MC Fichier de données Hidouci W.K. / Méthodes d'index / Structures de fichiers (SFSD) / ESI - 2021 33 Pour la représentation des valeurs multiples des clés de recherche, on adapte assez facilement la structures des arbres binaire de recherche pour supporter les valeurs de clés identiques : - Soit chaque nœud de l’arbre pointe une liste d’adresses d’enregistrements du fichier de données ayant comme valeur de clé l’information du nœud. ,Voir exemple dans la figure ci-dessous.... c... La valeur c apparaît dans 3 enregistrements... c c... a1 a2 a3... c Fichier de données - Soit relaxer la contrainte du maintient de l’ordre de l’arbre binaire : < en ≤ (ou respectivement : > en ≥) pour accepter les valeurs en double en les plaçant à gauche (respectivement à droite) du nœud courant. Index de grande taille Si l'index est trop grand pour résider en mémoire centrale (MC), on peut travailler directement sur le fichier index à la place de la table d’index. Dans ce cas le fichier index qui est de type TOF ou TOVC (pour pouvoir faire des recherches dichotomiques), est utilisé comme structure auxiliaire permettant d’accélérer les opérations d’accès au fichier de données (il n’y a plus de table d’index en MC dans ce cas particulier). Par exemple une recherche d’enregistrement de clé v, commence d’abord par une recherche de v dans le fichier index (par dichotomie) afin de récupérer les informations de localisation (numéros de blocs, déplacement, indicateur d’effacement logique, taille...etc). Ensuite l’accès au fichier de données est effectuer pour récupérer le (ou les) enregistrement(s) associé(s). Les autres opérations (insertion, suppression, …) peuvent aussi être définies en utilisant le fichier index au lieu de la table d’index en MC. 3) Index multi-niveaux Si le fichier index est assez volumineux, même la recherche dichotomique nécessitera un nombre de lectures de blocs relativement élevé (par exemple de l’ordre des dizaines d’accès disques pour des fichiers index de plus de mille blocs). On peut diminuer ce nombre en construisant un deuxième index sur le fichier index (ordonné). Dans ce cas, on choisira une seule clé pour chaque groupe de blocs du fichier index (index non dense) pour construire le deuxième index. On obtient ainsi un index à 2 niveaux. Si le deuxième index est encore trop grand pour résider en MC, on le stocke sur disque (deuxième fichier index) et on construit un troisième index en choisissant une clé par groupe de blocs du deuxième fichier index. On peut répéter ce procédé jusqu’à obtenir un index pouvant résider en mémoire centrale (index à n niveaux). La figure ci-dessous, montre les différents composants d’un index à 2 niveaux: Hidouci W.K. / Méthodes d'index / Structures de fichiers (SFSD) / ESI - 2021 34  Table index 2 en MC Clé Adr Sauvegarde index2 Fichier index 1 en MS Chargement index2 Fichier de données en MS Fichier index 2 en MS (de sauvegarde) 4) Accès multiclés Pour améliorer les recherches basées sur plusieurs clé de recherche en même temps (requêtes multi- clés), on peut utiliser et combiner plusieurs index (un sur chaque attribut utilisé). Une requête multi-clés est de la forme : « trouver les enregistrement /que P soit vrai » avec P un prédicat de type conjonction ou disjonction de conditions élémentaire : C1 ∧/∨ C2... Cn chaque condition élémentaire Ck porte sur un seul attribut du fichier de données. Par exemple si on dispose de 2 index : IndA1 et IndA2, construits respectivement sur les attributs Hidouci W.K. / Méthodes d'index / Structures de fichiers (SFSD) / ESI - 2021 35 A1 et A2 du fichier de données, on peut localiser rapidement tous les enregistrements vérifiant une conditions de la forme A1=v1 ∧ A2=v2 (c’est une requête multi-clés portant sur A1 et A2). Les étapes peuvent être résumées comme suit : 1. On recherche v1 dans l’index IndA1 produisant comme résultat une liste L1 (éventuellement vide) d’adresses d’enregistrements. 2. On recherche v2 dans l’index IndA2 produisant comme résultat une liste L2 (éventuellement vide) d’adresses d’enregistrements. 3. On effectue l’intersection des deux listes L = L1 Ç L2. 4. On trie L sur le numéro de bloc et on accède au fichier de données pour récupérer les enregistrements cherchés. Cet algorithme (les 4 étapes ci-dessus) n’est pas forcément le meilleur (d’un point de vue performance). Tout dépend en fait du nombre d’enregistrements vérifiant la condition de la requête (c’est ce qui est appelé la sélectivité du prédicat P). Si ce nombre est important, un parcours séquentiel du fichier de données sera peut être plus avantageux que d’accéder par les index. On peut estimer à l’avance la sélectivité d’une requête si nous disposons de statistiques sur les valeurs des attributs dans le fichier de données. Par exemple lors des insertions/suppression on peut mettre à jours ce genre de statistiques. Un cas particulier (et assez fréquent aussi) de l’utilisation de plusieurs index en même temps, est la méthode des listes inversées. Cette méthode est applicable lorsque l’un des attributs indexés est à valeurs uniques (en bases de données en parle alors de clé primaire). Index sur clé X clésP Fichier de données secondaire X x1 c, c'' c'' | x1, y1 Index sur clé primaire x2 c' cléP Adr c (i,j) c | x1, y2 c' (i', j') Y clésP c'' (i'',j'') y1 c'' c' | x2, y3 y2 c y3 c' Index sur clé secondaire Y Hidouci W.K. / Méthodes d'index / Structures de fichiers (SFSD) / ESI - 2021 36 Par abus de langage, on désigne souvent l’index construit sur cet attribut comme étant « primaire » (même si le fichier de données n’est pas ordonné) et les autres index (sur les autres attributs) seront dits « secondaires » (cette terminologie : ‘index primaire et index secondaire’ est légèrement différente de celle utilisées généralement dans les structures de fichiers au niveau physique, comme cela a été présenté en début de chapitre et peut donc entraîner une certaine confusion chez le lecteur non averti). Dans la figure précédente, on dispose d’un index sur la clé primaire P (à valeurs uniques) et de deux index sur les clés secondaires X et Y (pouvant être à valeurs multiples). Le problème avec les clés secondaires, est qu'il peut exister plusieurs enregistrements pour une même valeur du champ indexé. On implémente généralement cette multiplicité à travers des listes de clés primaires (au lieu de listes d’adresses). X ptr cléP suiv cléP Adr … x1 c c (i,j) Vers le fichier de x2 c' c' (i', j') données c'' c'' (i'',j'') … Index secondaire avec ses listes de clés primaires Index sur clé primaire Quand on recherche les enregistrements suivant une clé secondaire (par exemple X=a), on utilise l'index sur la clé secondaire X pour récupérer la ou les clés primaires associées à la valeur cherchée (a). Pour chaque clé primaire trouvée, on utilise l'index sur la clé primaire P pour localiser l'enregistrement sur le fichier de données (numéro de bloc et déplacement). Dans cette méthode (listes inversées) la recherche commence sur l’index de clé secondaire, puis passe par l’index de clé primaire avant d’atteindre le fichier de données. Voici les étapes d’une requête multi-clés avec la méthode des listes inversées : « trouver tous les enregistrements dont la valeur de X = vx ET la valeur de Y = vy ET... » avec X, Y,... des clés secondaires. 1. En utilisant l'index secondaire X, trouver la liste Lx de clés primaires associées à la valeur de X (vx). 2. Refaire la même action pour chaque clé secondaire mentionnée dans la