Cours Structures de Fichiers et de Données PDF

STRUCTURES DE FICHIERS ET DE DONNEES Pr SERIDI HASSINA  STRUCTURES DE FICHIERS ET DE DONNEES Les fichiers sont diluées dans plusieurs cours différents : Structure de machines, Algorithmique, Systèmes d’information, Analyse, bases de données, Systèmes d’exploitat...

STRUCTURES DE FICHIERS ET DE DONNEES Pr SERIDI HASSINA  STRUCTURES DE FICHIERS ET DE DONNEES Les fichiers sont diluées dans plusieurs cours différents : Structure de machines, Algorithmique, Systèmes d’information, Analyse, bases de données, Systèmes d’exploitation L’étudiant pourra : Concevoir des structures de fichiers efficaces et répondant aux besoins de tout type d’applications. Maitriser toute la terminologie et les concepts fondamentaux des fichiers Avoir des connaissances suffisantes sur la technologie des supports magnétiques afin que ces dernières ne soient pas vues comme de simples boites noires Connaître les différents types d’organisation des fichiers, leur représentation, leur fonctionnement et comment effectuer les choix Percevoir l’ensemble de ces éléments comme un tout cohérent et complet, qui sera un pré requis nécessaire à d’autres enseignements et à la vie professionnelle.  STRUCTURES DE FICHIERS ET DE DONNEES Le Programme GENERALITES SUR LES FICHIERS (6 h.) concepts de base fichier, enregistrement, zone, caractère activité d’un fichier, taux de consultation, taux de renouvellement, stabilité typologie des fichiers (permanent ou de base, mouvement, manœuvre, intermédiaire, archive, historique, fichier mono volume, multi volume, volume multi fichiers, table, opérations fondamentales sur les fichiers (création, mise à jour, réunion, éclatement, tri, fusion, extraction, copie) différence entre Ram et Mémoire secondaire fichiers physique et fichier logique enregistrement logique et enregistrement physique types d’enregistrements (longueur fixe, variable, indéfinie) le facteur de blocage, son intérêt fichiers statiques et dynamiques  STRUCTURES DE FICHIERS ET DE DONNEES TECHNOLOGIE DES SUPPORTS (4 h.) La bande magnétique le disque magnétique le disque optique Description, enregistrement physique, densité d’enregistrement, mode d’enregistrement, capacité de stockage théorique et pratique, temps de lecture/écriture) Evolution des supports magnétiques  STRUCTURES DE FICHIERS ET DE DONNEES ORGANISATION DES FICHIERS (17 h.) STRUCTURES SIMPLES (3 h.) Organisation contiguë Organisation chainée Classification des structures simples METHODES D’INDEX (3 h.) Index primaire Index secondaire o Index multiniveaux STRUCTURES D’ARBRES (5 h.) Fichier arborescent Index arborescent o B-Arbres HACHAGE (4 h.) Fonction de hachage Méthodes de résolution de collisions o Hachage statique Hachage dynamique CHOIX D’UNE ORGANISATION (2 h.) paramètres du choix exemple d’application  STRUCTURES DE FICHIERS ET DE DONNEES INTRODUCTION AUX BASES DE DONNEES (3 h.) Pourquoi une base de données ? Définition Concepts fondamentx communs à toutes les bases de données Principales fonctions d’un SGBD  STRUCTURES DE FICHIERS ET DE DONNEES GENERALITES SUR LES FICHIERS concepts de base fichier, enregistrement, zone, caractère activité d’un fichier, taux de consultation, taux de renouvellement, stabilité  STRUCTURES DE FICHIERS ET DE DONNEES Concepts de base Le cours sur les fichiers et les structures de données traite de concepts fondamentaux liés à la manipulation et au stockage de données sur des dispositifs de stockage, tels que des disques durs, des mémoires flash ou des bandes magnétiques.  STRUCTURES DE FICHIERS ET DE DONNEES Fichier, enregistrement, zone, caractère 1.Fichier : 1. Définition : Un fichier est une unité de stockage de données utilisée pour regrouper des informations. Il s'agit d'une structure de données qui permet de stocker et d'organiser des données sur un support de stockage, tel qu'un disque dur ou une mémoire flash. 2. Exemple : Un fichier texte contenant une liste de noms et de numéros de téléphone. 2.Enregistrement : 1. Définition : Un enregistrement est une structure de données dans un fichier qui regroupe un ensemble d'informations liées. Il représente une entité individuelle et contient plusieurs champs ou zones de données. 2. Exemple : Dans une base de données d'employés, chaque enregistrement peut contenir des champs tels que le nom, le prénom, le numéro d'employé et le salaire d'un employé spécifique.  STRUCTURES DE FICHIERS ET DE DONNEES Fichier, enregistrement, zone, caractère 1.Fichier : Exemple : Imaginons que vous ayez un fichier de données d'étudiants dans une école. Chaque enregistrement dans ce fichier pourrait ressembler à ceci : Code Enregistrement 1 : Nom : Smith Prénom : John Âge : 20 Matricule : 12345 Dans cet exemple, chaque enregistrement représente un étudiant, et les zones caractères (Nom, Prénom, Matricule) contiennent des informations textuelles relatives à cet étudiant.  STRUCTURES DE FICHIERS ET DE DONNEES Fichier, enregistrement, zone, caractère 1.Zone : 1. Définition : Une zone est une partie spécifique d'un enregistrement dans un fichier. Elle est généralement utilisée pour stocker des données de type similaire, comme des caractères ou des nombres. 2. Exemple : Dans un fichier de données sur les étudiants, une zone "Nom" peut contenir le nom de l'étudiant (par exemple, "Smith"), une zone "Âge" peut contenir l'âge de l'étudiant (par exemple, 20 ans), et ainsi de suite. 2.Caractère : 1. Définition : Un caractère est un symbole individuel, tel qu'une lettre, un chiffre, un espace ou un signe de ponctuation, qui peut être utilisé pour représenter des informations textuelles. 2. Exemple : Les caractères individuels dans le mot "Informatique" sont "I", "n", "f", "o", "r", "m", "a", "t", "i", "q", "u", "e". En résumé, dans le contexte des structures de fichiers et de données, un fichier est une unité de stockage de données, un enregistrement est une structure de données qui regroupe des informations connexes, une zone est une partie spécifique d'un enregistrement, et un caractère est un symbole individuel utilisé pour représenter des données textuelles. Ces concepts sont fondamentaux pour organiser et manipuler des données de manière efficace dans un système informatique.  STRUCTURES DE FICHIERS ET DE DONNEES Activité d’un fichier Définition : L'activité d'un fichier se réfère à la fréquence à laquelle un fichier est consulté ou modifié. Cela mesure à quel point un fichier est actif ou inactif. Exemple : Un fichier journal de serveur Web peut avoir une activité élevée car il est constamment mis à jour pour enregistrer les visites sur un site Web. En revanche, un fichier de configuration système peut avoir une activité beaucoup plus faible car il est rarement modifié.  STRUCTURES DE FICHIERS ET DE DONNEES Taux de consultation Définition : Le taux de consultation d'un fichier est la mesure de la fréquence à laquelle un fichier est lu ou consulté par rapport au nombre total d'accès au fichier (lectures ou écritures). Exemple : Si un fichier a été lu 100 fois et écrit 50 fois au cours d'une période donnée, le taux de consultation serait de 100 / (100 + 50) = 66,67 %.  STRUCTURES DE FICHIERS ET DE DONNEES Taux de renouvellement, Définition : Le taux de renouvellement d'un fichier indique la fréquence à laquelle un fichier est modifié ou réécrit par rapport à son nombre total d'accès. Exemple : Si un fichier a été modifié 20 fois et consulté 80 fois au cours d'une période donnée, le taux de renouvellement serait de 20 / (20 + 80) = 20 %.  STRUCTURES DE FICHIERS ET DE DONNEES Stabilité Définition : La stabilité d'un fichier se rapporte à la persistance des données dans le fichier. Un fichier stable est celui dont le contenu reste relativement inchangé sur une longue période. Exemple : Un fichier de données historiques sur les températures moyennes mensuelles dans une région est généralement stable car il conserve des données qui ne changent pas fréquemment au fil du temps.  STRUCTURES DE FICHIERS ET DE DONNEES Ces concepts sont importants pour la gestion et l'optimisation des fichiers, en particulier dans les systèmes informatiques et de gestion de données. Comprendre l'activité d'un fichier, son taux de consultation, son taux de renouvellement et sa stabilité permet aux administrateurs de système et aux développeurs de prendre des décisions éclairées sur la gestion des fichiers et des données.  La typologie des fichiers peut varier en fonction de leur utilisation, de leur durée de stockage, et de leur rôle dans un système informatique. Voici une liste de différents types de fichiers :  Fichier Permanent ou de Base Il s'agit d'un fichier de base qui contient des données essentielles et permanentes pour le fonctionnement d'un système ou d'une application. Ces fichiers ne sont généralement pas supprimés.  Fichier de Mouvement : Ces fichiers sont utilisés pour enregistrer les données relatives aux transactions ou aux mouvements d'un système, tels que les ventes quotidiennes d'un magasin.  Fichier de Manœuvre : Les fichiers de manœuvre contiennent des données temporaires ou de travail nécessaires pour effectuer des opérations temporaires, mais qui ne sont pas conservées à long terme.  Fichier Intermédiaire : Les fichiers intermédiaires sont utilisés pour stocker des données en cours de traitement ou pour effectuer des opérations de transformation avant de les enregistrer dans d'autres fichiers.  Fichier d'Archive : Les fichiers d'archive sont destinés à stocker des données historiques ou obsolètes qui ne sont plus utilisées fréquemment, mais qui doivent être conservées à des fins de référence ou de conformité.  Fichier Historique : Ces fichiers contiennent des données historiques qui peuvent être consultées pour l'analyse ou la recherche. Ils peuvent être similaires aux fichiers d'archive. Fichier Mono Volume : Un fichier mono volume est stocké dans un seul fichier physique, ce qui signifie qu'il n'est pas divisé en parties distinctes.  Fichier Multi Volume : Les fichiers multi volume sont divisés en plusieurs parties, chacune étant stockée dans un fichier distinct. Ils sont souvent utilisés pour gérer de grandes quantités de données. Volume Multi Fichiers : Un volume multi fichiers est une structure de stockage qui regroupe plusieurs fichiers en un seul ensemble, souvent utilisé pour faciliter la gestion des fichiers.  Fichier Multi Volume : Les fichiers multi volume sont divisés en plusieurs parties, chacune étant stockée dans un fichier distinct. Ils sont souvent utilisés pour gérer de grandes quantités de données. Volume Multi Fichiers : Un volume multi fichiers est une structure de stockage qui regroupe plusieurs fichiers en un seul ensemble, souvent utilisé pour faciliter la gestion des fichiers. Fichier Table : Les fichiers table sont couramment utilisés dans les bases de données pour stocker des données sous forme de tableaux, avec des lignes et des colonnes, pour permettre une manipulation structurée des données  Opérations fondamentales sur les fichiers 1. Création, 2. Mise à jour, 3. Réunion, 4. Eclatement, 5. Tri, 6. Fusion, 7. Extraction, 8. Copie.  Exemple Création et écriture dans un fichier 1- Créez un programme C qui demande à - l'utilisateur d'entrer du texte au clavier (Hello ! i am « your name », i am a computer engineer student). 2- Enregistrez ce texte dans un fichier texte nouvellement créé. Exercice 2 Une personne est caractérisée par son nom, son prénom et son âge. Dans un algorithme: – Déclarer la structure de données Personne. – Déclarer deux enregistrements pers1 et pers2. – Saisir (lire) les informations (nom, prénom et âge) de pers1 et pers2. – Calculer la différence d'âge entre pers1 et pers2. – Afficher la différence d'âge entre pers1 et pers2. Exercice 1 Un compte en banque concerne une personne spécifiée par son nom, un numéro de compte (entier), et un montant (réel). Déclarer la structure de données Compte et deux enregistrements compte1 et compte2 de type Compte en langage algorithmique et en langage C. Exercice 2 Une personne est caractérisée par son nom, son prénom et son âge. Dans un algorithme : 1. Déclarer la structure de données Personne. 2. Déclarer deux enregistrements pers1 et pers2. 3. Saisir (lire) les informations (nom, prénom et âge) de pers1 et pers2. 4. Calculer la différence d'âge entre pers1 et pers2. 5. Afficher la différence d'âge entre pers1 et pers2. Exercice 3 Un employé dans une entreprise est caractérisé par un matricule, un nom, un salaire et un état civil. Les informations sur 50 employés sont stockées dans un tableau. 1. Faire la déclaration des structures de données Employé et TabEmp (tableau des employés). 2. Comment déclarer un enregistrement E de type Employé ? 3. Comment affecter les informations suivantes à l'enregistrement E ? Matricule : 201100084, Nom : Mohammed, Salaire: 40000, Etat civile : Marié. 4. Faire la déclaration d'un tableau T de type TabEmp. 5. Comment saisir (lire) les informations correspondantes à l'employé numéro i dans le tableau T Ce programme utilise les fonctions fopen pour ouvrir le fichier en mode lecture  Pour créer une copie du fichier "essai.txt" précédemment créé, vous pouvez utiliser le code C suivant. Ce programme lira le contenu du fichier "essai.txt" et le copiera dans un nouveau fichier nommé "copia_essai.txt". Assurez-vous que le fichier "essai.txt" existe avant d'exécuter ce programme. Ce programme ouvre le fichier source en mode lecture et le fichier destination en mode écriture, puis copie le contenu caractère par caractère de l'un à l'autre. Après la copie, il ferme les deux fichiers. Une copie du fichier "essai.txt" sera ainsi créée sous le nom "copia_essai.txt".  Pour créer un fichier "Agent" avec une structure comprenant le nom (20 caractères), le prénom (20 caractères) et l'âge (2 valeurs numériques), vous pouvez utiliser le code C suivant. Il crée d'abord le fichier "Agent" avec une entrée initiale, puis insère un nouvel élément dans le fichier. Assurez-vous que les fichiers "Agent.c" et "Agent.bin" n'existent pas avant d'exécuter le programme pour éviter d'écraser des données existantes.  Ce programme crée d'abord le fichier "Agent" en enregistrant les données d'un agent initial, puis il permet d'insérer un nouvel agent à la fin du fichier en ouvrant le fichier en mode lecture/écriture binaire. Les données des agents sont stockées sous forme binaire pour respecter la structure de la struct Agent. Assurez-vous que le fichier "Agent.bin" n'existe pas ou qu'il est vide avant d'exécuter le programme pour éviter d'écraser des données existantes. printf("Un nouvel agent a été inséré dans le fichier \"Agent\".\n"); return 0; }  La suppression d'un élément d'un fichier binaire, comme dans le cas de votre fichier "Agent", nécessite une opération de copie qui exclut l'élément que vous souhaitez supprimer. Voici un programme en C qui vous montre comment supprimer un élément du fichier "Agent" en effectuant une copie du fichier original sans l'élément à supprimer : Ce programme lit chaque agent du fichier "Agent", vérifie si l'agent correspondant au nom que vous souhaitez supprimer a été trouvé, et copie tous les autres agents dans un fichier temporaire. Enfin, il supprime le fichier original et renomme le fichier temporaire pour qu'il prenne le nom du fichier original. Pour modifier la donnée "âge" d'un agent dans le fichier "Agent" précédemment créé, vous pouvez utiliser le code C suivant. Ce programme vous permet de rechercher un agent par son nom, puis de mettre à jour son âge dans le fichier. Assurez-vous que le fichier "Agent.bin" contenant les données existe avant d'exécuter ce programme. #include #include #include // Structure pour représenter un agent struct Agent { char nom; // Nom (20 caractères + le caractère nul) char prenom; // Prénom (20 caractères + le caractère nul) int age; // Âge (2 valeurs numériques) }; int main() { // Ouvrir le fichier "Agent" en mode lecture/écriture binaire FILE *fichierAgent; fichierAgent = fopen("Agent.bin", "r+b"); if (fichierAgent == NULL) { printf("Impossible d'ouvrir le fichier \"Agent\" pour la modification.\n"); return 1; } char nomAModifier; // Le nom de l'agent à modifier int nouvelAge; // La nouvelle valeur de l'âge printf("Saisissez le nom de l'agent que vous souhaitez modifier : "); scanf("%20s", nomAModifier); // Lire chaque agent du fichier struct Agent agentCourant; int agentTrouve = 0; // Pour indiquer si l'agent à modifier a été trouvé while (fread(&agentCourant, sizeof(struct Agent), 1, fichierAgent) == 1) { // Vérifier si l'agent actuel doit être modifié if (strcmp(agentCourant.nom, nomAModifier) == 0) { agentTrouve = 1; // L'agent a été trouvé printf("L'âge actuel de l'agent est : %d\n", agentCourant.age); printf("Saisissez la nouvelle valeur de l'âge : "); scanf("%d", &nouvelAge); agentCourant.age = nouvelAge; // Positionner le curseur à l'emplacement actuel pour la mise à jour fseek(fichierAgent, -sizeof(struct Agent), SEEK_CUR); // Écrire la mise à jour de l'âge fwrite(&agentCourant, sizeof(struct Agent), 1, fichierAgent); break; // Sortir de la boucle après la mise à jour } } // Fermer le fichier fclose(fichierAgent); if (agentTrouve) { printf("L'âge de l'agent a été modifié avec succès.\n"); } else { printf("Aucun agent avec ce nom n'a été trouvé.\n"); } return 0; } Ce programme lit chaque agent du fichier "Agent", recherche l'agent par son nom, puis permet à l'utilisateur de saisir une nouvelle valeur d'âge. Il met ensuite à jour le fichier avec la nouvelle valeur de l'âge. Assurez-vous que le fichier "Agent.bin" existe et contient des données avant d'exécuter le programme. Un exemple de programme en C qui fusionne deux fichiers triés en un fichier trié en utilisant la même structure de fichier "Agent" que précédemment. Assurez-vous que les fichiers "Fichier1.bin" et "Fichier2.bin" existent et contiennent des données triées avant d'exécuter le programme. Ce programme ouvre deux fichiers sources triés, lit les données d'agents de chaque fichier, les fusionne dans un fichier de destination trié en fonction du nom, puis ferme tous les fichiers. Le fichier de destination "FichierFusionne.bin" contiendra les données fusionnées triées par nom. La mémoire RAM (Random Access Memory) et la mémoire secondaire sont deux types de mémoire utilisés dans les systèmes informatiques, mais elles ont des rôles et des caractéristiques fondamentalement différents. De plus, les fichiers physiques et les fichiers logiques sont des concepts liés au stockage de données, mais ils se rapportent à des aspects différents de la gestion des données. Voici les distinctions entre ces termes. Mémoire RAM vs. Mémoire Secondaire : Mémoire RAM (Random Access Memory) : La RAM est une mémoire volatile utilisée pour stocker temporairement les données et les programmes en cours d'exécution par un ordinateur. Elle est rapide, mais elle perd toutes les données lors de l'extinction de l'ordinateur. La RAM est essentielle pour l'exécution de programmes et le traitement de données en temps réel. Mémoire Secondaire : La mémoire secondaire, telle qu'un disque dur ou une mémoire flash, est une mémoire non volatile utilisée pour stocker des données sur une base permanente. Contrairement à la RAM, les données dans la mémoire secondaire restent intactes même lorsque l'ordinateur est éteint. La mémoire secondaire est utilisée pour stocker des fichiers, des systèmes d'exploitation et d'autres données à long terme. Fichier Physique vs. Fichier Logique : Fichier Physique : Un fichier physique est un fichier stocké sur un dispositif de stockage (comme un disque dur) sous forme binaire. Il s'agit de la représentation réelle des données sur le support de stockage. Les fichiers physiques sont accessibles par l'ordinateur en utilisant des adresses de blocs ou des secteurs sur le dispositif de stockage. Fichier Logique : Un fichier logique est une représentation abstraite d'un fichier en utilisant des noms, des chemins et des extensions. Il est ce que l'utilisateur voit et utilise lorsqu'il travaille avec des données sur un système d'exploitation. Les fichiers logiques permettent aux utilisateurs d'interagir avec les données de manière conviviale, sans se soucier de leur emplacement physique sur le support de stockage. En résumé, la mémoire RAM est utilisée pour le stockage temporaire de données en cours d'exécution, tandis que la mémoire secondaire est utilisée pour le stockage permanent de données. Les fichiers physiques représentent la façon dont les données sont stockées sur un support de stockage, tandis que les fichiers logiques sont la manière dont les utilisateurs interagissent avec les données via des noms et des chemins de fichiers.  SGF requête réponse RequêtesE/S utilisateur traitement SystèmeE/S S.E. commandes PiloteE/S S.E. Interruptions matériel S.E. ContrôleurE/S accèsunité matériel Périphérique Types d'enregistrements : Enregistrements à longueur fixe : Dans ce type d'enregistrement, chaque champ de données occupe un nombre fixe d'octets. Cela facilite l'accès direct aux données, car on peut calculer la position d'un champ en fonction de sa taille fixe et de sa position dans l'enregistrement. Cependant, cela peut gaspiller de l'espace mémoire si certains champs n'utilisent pas tous les octets qui leur sont assignés.  Enregistrements à longueur variable : Les enregistrements à longueur variable permettent une utilisation plus efficace de l'espace mémoire en ajustant la longueur des champs en fonction des données réelles stockées. Cela peut être plus complexe à gérer, car il faut généralement inclure des informations sur la longueur de chaque champ. Enregistrements à longueur indéfinie : Certains systèmes de gestion de bases de données permettent des enregistrements de longueur indéfinie, où la taille des données peut varier dynamiquement. Cela est souvent utilisé pour stocker des données telles que des chaînes de caractères de longueur variable.. Facteur de blocage : Le facteur de blocage se réfère à la manière dont les enregistrements sont stockés en mémoire ou sur un support de stockage. Il peut être influencé par la taille des blocs utilisés pour stocker les données. Par exemple : Blocage fixe :  Les enregistrements sont stockés en blocs de taille fixe.  Cela peut entraîner un gaspillage d'espace si les enregistrements ne remplissent pas complètement le bloc. Blocage dynamique : Les enregistrements sont stockés en blocs de taille variable en fonction des besoins. Cela peut être plus efficace en termes d'utilisation de l'espace, mais peut rendre l'accès aux données légèrement plus complexe. Le choix du type d'enregistrement et du facteur de blocage dépend des besoins spécifiques de l'application, des performances requises et des contraintes de stockage. Un modèle de données bien conçu prend en compte ces facteurs pour optimiser l'efficacité et la performance du stockage des données. Le facteur de blocage est généralement calculé en divisant la taille totale des enregistrements par la taille totale du bloc de stockage. La formule mathématique pour le calcul du facteur de blocage (FB) est la suivante : FB=Taille totale des enregistrements / Taille totale du bloc de stockage Voyons un exemple simple pour illustrer cela. Supposons que nous ayons une série d'enregistrements de longueur fixe de 100 octets chacun, et que nous stockons ces enregistrements dans des blocs de stockage de 500 octets. Taille totale des enregistrements : Si nous avons, par exemple, 50 enregistrements, la taille totale des enregistrements serait 50×100=5000 octets. Taille totale du bloc de stockage : Dans cet exemple, chaque bloc a une taille de 500 octets. FB=5000/500=10 Dans ce cas, le facteur de blocage serait de 10. Cela signifie que chaque bloc de stockage est rempli en moyenne par 10 enregistrements de 100 octets chacun. Il est important de noter que le facteur de blocage peut varier en fonction de la manière dont les enregistrements sont répartis dans les blocs et peut influencer l'efficacité de l'utilisation de l'espace de stockage. Dans certains cas, un facteur de blocage plus élevé peut indiquer une utilisation plus efficace de l'espace, tandis qu'un facteur de blocage plus bas peut indiquer un gaspillage d'espace.  Bande magnétique, le disque magnétique et le disque optique. Bande Magnétique : La bande magnétique est un support de stockage de données qui utilise une bande plastique recouverte d'une substance magnétique. Les données sont enregistrées sous forme de variations magnétiques sur la bande. Les bandes magnétiques sont souvent utilisées pour la sauvegarde de données, l'archivage et la diffusion de médias. Elles ont été populaires dans le passé pour le stockage de données à long terme, mais ont été largement remplacées par des technologies plus récentes, notamment les disques durs et les disques SSD. Disque Magnétique : Les disques magnétiques, tels que les disques durs, sont des dispositifs de stockage qui utilisent des plateaux recouverts d'un matériau magnétique. Les données sont enregistrées sous forme de charges magnétiques sur la surface du disque. Les disques magnétiques offrent une grande capacité de stockage et sont couramment utilisés dans les ordinateurs personnels et les serveurs. Cependant, ils sont sensibles aux chocs et aux champs magnétiques, et leur utilisation comme support de stockage principal diminue avec l'avènement des disques SSD. Disque Optique : Les disques optiques utilisent la lumière pour lire et écrire des données. Ils comprennent des formats tels que les CD (Compact Disc), les DVD (Digital Versatile Disc) et les disques Blu-ray. Ces disques ont une surface réfléchissante avec des creux et des bosses qui représentent les données. Un laser est utilisé pour lire ces variations, ce qui permet de récupérer les données stockées. Les disques optiques sont couramment utilisés pour la distribution de contenu multimédia, tels que des films, de la musique et des logiciels. Cependant, leur capacité de stockage est généralement inférieure à celle des disques magnétiques. En résumé, chaque type de support de stockage a ses propres avantages et inconvénients, et le choix entre eux dépend souvent des besoins spécifiques d'utilisation, de la capacité de stockage requise et d'autres facteurs tels que la durabilité et la vitesse d'accès aux données. Un disque dur est un dispositif de stockage de données magnétique qui utilise des plateaux recouverts d'une couche magnétique pour enregistrer et lire des informations. Voici une liste des principaux composants d'un disque dur : Plateaux (Platters) : Les plateaux sont des disques en aluminium ou en verre recouverts d'une fine couche de matériau magnétique. Ces plateaux sont montés sur un axe motorisé et tournent à des vitesses élevées (par exemple, 5400 tours par minute (tr/min) ou 7200 tr/min) pendant le fonctionnement du disque dur. Tête de Lecture/Écriture (Read/Write Head) : Chaque plateau a une tête de lecture/écriture associée. Les têtes flottent très près de la surface du plateau sans jamais la toucher. Elles sont responsables de l'écriture des données sur le plateau et de la lecture des données à partir de celui-ci. Bras d'Actionnement (Actuator Arm) : Le bras d'actionnement est responsable du mouvement des têtes de lecture/écriture vers la piste appropriée sur le plateau. Le positionnement précis des têtes est crucial pour un accès rapide et efficace aux données. Actionneur : L'actionneur est le mécanisme qui déplace le bras d'actionnement. Il utilise généralement un système de bobines mobiles ou une technologie similaire pour déplacer les têtes de manière précise sur la surface du plateau. Moteur du Plateau (Spindle Motor) : Le moteur du plateau fait tourner les plateaux à une vitesse constante. La vitesse à laquelle les plateaux tournent est mesurée en tours par minute (tr/min). Électronique de Contrôle (Controller Board) : Le contrôleur (ou électronique de contrôle) gère le fonctionnement global du disque dur. Il contrôle le mouvement des têtes, la rotation des plateaux, et la lecture/écriture des données. Il est également responsable de l'interface du disque dur avec l'ordinateur hôte (par exemple, SATA, IDE). Cache (Buffer) : Le cache est une petite quantité de mémoire vive (RAM) intégrée au disque dur. Il sert à stocker temporairement les données fréquemment utilisées pour améliorer les performances d'accès aux données. Connecteurs d'Alimentation et de Données : Le disque dur est connecté à l'ordinateur par le biais de connecteurs d'alimentation et de données. Les connecteurs d'alimentation fournissent l'énergie nécessaire au fonctionnement du disque dur, tandis que les connecteurs de données permettent la transmission des informations entre le disque dur et l'ordinateur. Lorsque le disque dur est en marche, ces composants travaillent de manière coordonnée pour permettre le stockage et l'accès aux données de manière rapide et fiable. Enregistrement Physique : L'enregistrement physique se réfère à la manière dont les données sont stockées sur le support de stockage, qu'il s'agisse d'une bande magnétique, d'un disque magnétique (comme un disque dur) ou d'un disque optique. Bande Magnétique : Les données sont enregistrées sous forme de variations magnétiques sur une bande plastique. Disque Magnétique : Les données sont enregistrées sous forme de charges magnétiques sur la surface d'un plateau recouvert d'une couche magnétique. Disque Optique : Les données sont enregistrées sous forme de creux et de bosses réfléchissants sur la surface d'un disque optique. Densité d'Enregistrement : La densité d'enregistrement représente le nombre de bits ou d'unités de données stockées par unité de longueur ou de surface. Bande Magnétique : Mesurée en flux magnétique par unité de longueur.  Disque Magnétique : Mesurée en bits par pouce carré (bits per square inch) ou densité de bits linéaire. Disque Optique : Mesurée en bits par unité de surface. Mode d'Enregistrement : Bande Magnétique : Séquentiel, les données sont lues ou écrites de manière séquentielle sur la bande. Disque Magnétique : Les données peuvent être accédées de manière aléatoire, permettant un accès direct à n'importe quelle position sur le disque. Capacité de Stockage Théorique et Pratique : Bande Magnétique : Théoriquement élevée, mais la capacité pratique peut être affectée par la vitesse de défilement de la bande et d'autres facteurs. Disque Magnétique : La capacité théorique augmente avec la densité d'enregistrement. Les disques durs modernes peuvent avoir des capacités de plusieurs téraoctets (TB) à plusieurs pétaoctets (PB).  Disque Optique : La capacité théorique dépend du type de disque (CD, DVD, Blu-ray). Les disques Blu-ray ont une capacité supérieure à celle des DVD et CD. Disque Optique : Principalement séquentiel, mais certains formats permettent un accès partiel direct. Temps de Lecture/Écriture : Bande Magnétique : Le temps de recherche est relativement long car l'accès est séquentiel. Disque Magnétique : Le temps de recherche est généralement plus court que sur une bande magnétique en raison de l'accès aléatoire. Disque Optique : Le temps d'accès peut varier en fonction de la position du point de lecture sur le disque. Les lecteurs optiques peuvent avoir des temps d'accès plus longs que les disques durs. Ces caractéristiques varient en fonction des technologies spécifiques et de l'évolution des capacités de stockage au fil du temps. L'évolution des supports magnétiques a été marquée par des avancées significatives tant en termes de capacité de stockage que de performances. Voici une vue d'ensemble de l'évolution des supports magnétiques au fil des ans : 1.Bandes Magnétiques : Début à milieu du 20e siècle : Les bandes magnétiques étaient largement utilisées pour le stockage de données, en particulier dans les domaines de la sauvegarde et de l'archivage. Années 1950-1970 : Améliorations constantes de la densité d'enregistrement et de la qualité des supports, mais les performances restaient limitées par la nature séquentielle de l'accès aux données. 2.Disques Magnétiques (Disques Durs) : Années 1950-1960 : Début des disques durs dans les ordinateurs, offrant un stockage plus rapide et plus direct que les bandes magnétiques. Années 1980-1990 : Introduction de disques durs avec des capacités de stockage de plusieurs mégaoctets. L'évolution rapide de la technologie a conduit à des disques plus petits, plus rapides et plus efficaces. 3.Disques Magnétiques (Disques Durs) - Années 2000 à nos jours : 2000-2010 : Augmentation significative de la capacité des disques durs, avec des unités atteignant plusieurs téraoctets. L'introduction de nouvelles technologies, comme la connectivité SATA, a également amélioré les taux de transfert de données. 2010-2020 : Émergence des disques durs hybrides (HDD) combinant des disques magnétiques avec de petites quantités de mémoire flash pour améliorer les performances. Depuis 2020 : Les disques SSD (Solid State Drives) basés sur la technologie de mémoire flash ont commencé à concurrencer sérieusement les disques durs traditionnels en offrant des performances plus rapides, une plus grande durabilité et une consommation d'énergie réduite. 4.Bandes Magnétiques - Années 2000 à nos jours : 2000-2010 : Les bandes magnétiques continuent d'être utilisées pour la sauvegarde à grande échelle, mais sont souvent complétées par d'autres solutions de stockage. Depuis 2010 : Certains développements ont amélioré la densité d'enregistrement des bandes magnétiques, les rendant toujours pertinentes pour l'archivage à long terme de grandes quantités de données. L'évolution des supports magnétiques a été marquée par la concurrence constante avec d'autres technologies de stockage, en particulier les disques SSD, qui offrent des performances supérieures dans de nombreux cas d'utilisation. Cependant, les disques magnétiques restent une solution de stockage économique pour des capacités de stockage massives, tandis que les bandes magnétiques persistent dans des applications spécifiques, notamment pour la sauvegarde à long terme. Il faut clarifier ces concepts en relation avec le stockage de données, en particulier dans le contexte des systèmes de fichiers. 1.Organisation Contiguë : L'organisation contiguë fait référence à la manière dont les blocs ou clusters d'un fichier sont physiquement situés les uns à la suite des autres sur le support de stockage. Dans une organisation contiguë, les blocs de données d'un fichier sont placés consécutivement sur le disque, ce qui signifie qu'ils occupent des emplacements adjacents. Cela facilite l'accès séquentiel aux données mais peut entraîner une fragmentation si des fichiers sont supprimés ou modifiés, laissant des espaces vides dispersés. 2.Organisation Chainée : L'organisation chainée implique l'utilisation de pointeurs ou de liens pour connecter les blocs d'un fichier qui peuvent être dispersés sur le disque. Chaque bloc de données d'un fichier contient un pointeur vers le bloc suivant, créant ainsi une chaîne de blocs liés. Cette méthode peut réduire la fragmentation, mais elle peut entraîner des performances légèrement inférieures lors de l'accès séquentiel aux données. 3.Classification des Structures Simples : Dans le contexte des systèmes de fichiers, la classification des structures simples concerne la manière dont les fichiers sont organisés et gérés sur un support de stockage. Les structures simples comprennent l'organisation contiguë, l'organisation chainée, et d'autres méthodes comme l'index et la table d'allocation. Chaque méthode a ses avantages et ses inconvénients en termes d'efficacité d'accès, de gestion de l'espace et de complexité de mise en œuvre. En résumé, l'organisation contiguë et l'organisation chainée sont deux approches différentes pour stocker des données sur un support de stockage. L'organisation contiguë place les blocs consécutifs, tandis que l'organisation chainée utilise des liens ou des pointeurs pour connecter les blocs dispersés. La classification des structures simples englobe différentes méthodes d'organisation et de gestion de fichiers dans le cadre des systèmes de fichiers.  ORGANISATION DES FICHIERS STRUCTURES SIMPLES (3 h.) Organisation contiguë Organisation chainée Classification des structures simples METHODES D’INDEX (3 h.) Index primaire Index secondaire o Index multi niveaux STRUCTURES D’ARBRES (5 h.) Fichier arborescent Index arborescent o B-Arbres HACHAGE (4 h.) Fonction de hachage Méthodes de résolution de collisions o Hachage statique Hachage dynamique CHOIX D’UNE ORGANISATION (2 h.) paramètres du choix exemple d’application METHODES D’INDEX Index primaire Index secondaire o Index multi niveaux  Les méthodes d'indexation sont des techniques utilisées pour accélérer l'accès et la recherche dans une base de données en ajoutant des structures d'index aux données. Un index est une structure de données qui permet un accès rapide aux enregistrements d'une table en utilisant une clé ou une combinaison de clés. On distingue généralement deux types d'index : l'index primaire et l'index secondaire. Index Primaire : Définition : L'index primaire est une structure d'index qui est créée sur la clé primaire d'une table. La clé primaire est une colonne (ou un ensemble de colonnes) qui identifie de manière unique chaque enregistrement dans une table. Exemple : Supposons une table "Employes" avec les colonnes suivantes : ID (clé primaire) Nom Salaire En SQL code CREATE TABLE Employes ( ID INT PRIMARY KEY, Nom VARCHAR(50), Salaire FLOAT ); CREATE INDEX idx_nom ON Employes(Nom); Dans cet exemple, l'index primaire est créé sur la colonne ID. Cela garantit que chaque valeur dans la colonne ID est unique, et l'index accélère les opérations de recherche et de jointure sur cette clé. Exemple d'indexation dans une base de données relationnelle (par exemple, MySQL) avec l'utilisation d'index uniques, d'index composites et d'index textuels : Soit une base de données simple sur des livres et leurs auteurs. CREATE TABLE Auteurs ( AuteurID INT PRIMARY KEY, Nom VARCHAR(50) NOT NULL); CREATE TABLE Livres ( LivreID INT PRIMARY KEY, Titre VARCHAR(100) NOT NULL, AuteurID INT, AnneePublication INT, INDEX idx_AuteurID (AuteurID), FOREIGN KEY (AuteurID) REFERENCES Auteurs(AuteurID));  Index Unique : Supposons que chaque auteur a un nom unique. Nous pouvons ajouter un index unique sur la colonne Nom de la table Auteurs CREATE UNIQUE INDEX idx_NomUnique ON Auteurs(Nom); Cela garantit que le nom de chaque auteur est unique, améliorant ainsi les performances lors de la recherche d'auteurs par leur nom. Index Composite : Supposons que nous voulons rechercher des livres en fonction de l'auteur et de l'année de publication. Nous pouvons ajouter un index composite sur les colonnes AuteurID et AnneePublication de la table Livres. CREATE INDEX idx_AuteurAnnee ON Livres(AuteurID, AnneePublication); Cela améliorera les performances des requêtes qui filtrent les livres par auteur et année de publication. Index Textuel (Full-Text) : Si nous voulons effectuer des recherches textuelles avancées dans les titres des livres, nous pouvons utiliser un index de texte intégral. Cependant, notons que la prise en charge des index de texte intégral varie en fonction du système de gestion de base de données. Pour MySQL, voici un exemple : ALTER TABLE Livres ADD FULLTEXT INDEX idx_TitreFullText (Titre); Cela permettra d'effectuer des recherches de texte intégral plus sophistiquées dans la colonne Titre.  Index Secondaire : Définition : Un index secondaire est une structure d'index créée sur une colonne autre que la clé primaire. Il est utilisé pour accélérer les recherches basées sur cette colonne. Exemple : Continuons avec la table "Employes", mais ajoutons un index secondaire sur la colonne Nom. SQL CREATE TABLE Employes ( ID INT PRIMARY KEY, Nom VARCHAR(50), Salaire FLOAT, INDEX Nom_Index (Nom) ); Dans cet exemple, un index secondaire appelé Nom_Index est créé sur la colonne Nom. Cela accélère les opérations de recherche basées sur le nom des employés.  Index Multiniveaux : Définition : Un index multiniveau (ou index composite) est un index qui est créé sur plusieurs colonnes. Il est souvent utilisé pour accélérer les recherches qui impliquent plusieurs critères de sélection. Exemple : Supposons une table "Commandes" avec les colonnes suivantes : ID_Commande ID_Client Date_Commande SQL CREATE TABLE Commandes ( ID_Commande INT PRIMARY KEY, ID_Client INT, Date_Commande DATE, INDEX Commande_Client_Date_Index (ID_Client, Date_Commande) ); Ici, un index multiniveau appelé Commande_Client_Date_Index est créé sur les colonnes ID_Client et Date_Commande. Cela peut améliorer les performances pour les requêtes qui filtrent ou trient les commandes par client et par date. Exemples d'Opérations Accélérées par les Index : Recherche : Index Primaire : Recherche rapide d'un enregistrement spécifique par sa clé primaire. Index Secondaire : Recherche rapide d'enregistrements basée sur des colonnes autres que la clé primaire. Index Multiniveau : Recherche rapide d'enregistrements basée sur une combinaison de colonnes. Jointures : Index Primaire : Accélère les jointures entre tables basées sur les clés primaires. Index Secondaire : Accélère les jointures basées sur des colonnes indexées. Tri et Regroupement : Les index accélèrent les opérations de tri et de regroupement basées sur les colonnes indexées. Contraintes d'Intégrité : Les index aident à appliquer les contraintes d'intégrité comme les clés étrangères. Il est important de noter que bien que les index accélèrent la recherche, ils ont des coûts en termes d'espace de stockage et d'efficacité lors des opérations de modification (insertion, mise à jour, suppression) des données. Par conséquent, il est crucial de concevoir judicieusement les index en fonction des besoins spécifiques de l'application. STRUCTURES D’ARBRES Fichier arborescent Index arborescent o B-Arbres Structures d'Arbres : Les structures d'arbres sont des modèles de données hiérarchiques qui sont largement utilisés en informatique pour organiser et représenter des informations de manière efficace. Voici quelques structures d'arbres couramment utilisées : 1. Arbre Binaire : Un arbre binaire est une structure d'arbre où chaque nœud a au plus deux enfants : un nœud gauche et un nœud droit. Un exemple d'arbre binaire est l'arbre binaire de recherche (BST) où les nœuds sont organisés de manière à ce que les valeurs plus petites soient à gauche et les valeurs plus grandes soient à droite. 10 / \ 5 15 /\ / \ 3 7 12 20 2. Arbre N-aire : Un arbre N-aire est une généralisation de l'arbre binaire où chaque nœud peut avoir jusqu'à N enfants. Un exemple courant d'arbre N-aire est l'arbre DOM (Document Object Model) utilisé dans la représentation des pages web. Structures d'Arbres : 3. Arbre AVL : Un arbre AVL est un arbre binaire de recherche équilibré où la différence de hauteur entre les sous-arbres gauche et droit de chaque nœud est au plus 1. Cela garantit des temps de recherche et d'insertion logarithmiques. 4. Arbre Binaire de Recherche Équilibré (ARB) : ARB est une structure d'arbre binaire de recherche équilibré avec des propriétés spécifiques pour garantir une recherche, une insertion et une suppression efficaces. 5. Arbre Trie : Un arbre trie est une structure d'arbre où chaque nœud représente une lettre, et les chemins de la racine aux feuilles représentent des mots. Il est couramment utilisé pour la recherche de chaînes dans des dictionnaires ou pour la mise en œuvre de structures de données telles que les arbres de préfixes. Fichier Arborescent : Un fichier arborescent est une structure de stockage où les données sont organisées sous forme d'arbre. Chaque nœud de l'arbre représente un dossier ou un fichier, et les branches de l'arbre décrivent la hiérarchie des répertoires. Les systèmes de fichiers des ordinateurs utilisent souvent des structures de fichiers arborescentes pour organiser les données. -/ - home - utilisateur1 - documents - fichier1.txt - fichier2.txt - utilisateur2 - var - logs - syslog - www  Fichier Arborescent : Index Arborescent (Arbre B) : Un index arborescent, également connu sous le nom d'arbre B, est une structure d'arbre utilisée pour améliorer les opérations de recherche dans une base de données ou un système de fichiers. Les arbres B sont conçus pour être équilibrés et efficaces pour les opérations d'insertion, de suppression et de recherche. Propriétés d'un Arbre B : Ordre de l'Arbre (t) : Le nombre minimum de clés dans chaque nœud (autre que la racine) est t-1 et le nombre maximum est 2t-1. Chaque nœud interne a : t-1 clés triées en ordre croissant. t pointeurs vers des sous-arbres. Chaque feuille a : t-1 clés triées en ordre croissant. Pas de pointeurs vers des sous-arbres (NULL). Fichier Arborescent : Toutes les feuilles ont la même profondeur. Exemple d'Arbre B (t = 2) : 10 / \ 5,8 15 / \ / \ 3 7 12 20 L'arbre B ci-dessus a un ordre de 2 (t = 2). Chaque nœud interne a au plus deux clés et trois pointeurs vers des sous-arbres. Les structures d'arbres et les concepts associés sont fondamentaux en informatique et sont utilisés dans une variété d'applications, de la gestion des bases de données à la représentation des données hiérarchiques dans les systèmes de fichiers. Les arbres B sont des structures de données utilisées pour organiser des données dans des fichiers ou des bases de données, fournissant des opérations d'insertion, de suppression et de recherche efficaces. Les arbres B sont souvent utilisés dans la gestion des fichiers pour maintenir l'ordre des enregistrements et faciliter la recherche. Voici un exemple détaillé d'utilisation d'un arbre B dans la gestion des fichiers : Supposons que nous voulons créer un fichier d'index pour un ensemble de noms, où chaque enregistrement a un identifiant unique (clé) et un nom associé. Nous allons construire un arbre B pour gérer cet index. 1.Initialisation de l'arbre B : Nous commençons par créer un nœud racine vide. Chaque nœud contient des paires clé-valeur, où la clé est l'identifiant unique et la valeur est l'adresse (offset) de l'enregistrement dans le fichier de données. Racine: [] 2.Insertion d'enregistrements : Supposons que nous devons insérer les enregistrements suivants dans notre fichier : (1, "Alice") (5, "Bob") (8, "Charlie") (12, "David") (4, "Eve") Pour chaque enregistrement, nous insérons la clé dans l'arbre B. Étape 1: Insertion de (1, "Alice") Racine: Étape 2: Insertion de (5, "Bob") Racine: [1, 5] Étape 3: Insertion de (8, "Charlie") Racine: [1, 5, 8] Étape 4: Insertion de (12, "David") Racine: [1, 5, 8, 12] Étape 5: Insertion de (4, "Eve") Racine: [1, 4, 5, 8, 12] 3-Recherche dans l'arbre B : Supposons que nous devons rechercher l'enregistrement avec la clé 8. Recherche de la clé 8: -Aller à la racine [1, 4, 5, 8, 12] -Descendre dans le sous-arbre associé à 8 -Trouver la clé 8 dans le sous-arbre - Renvoyer l'adresse associée à la clé 8 (adresse de "Charlie" dans le fichier de données) 4- Suppression d'enregistrements : Supposons que nous devons supprimer l'enregistrement avec la clé 5. Étape 1: Suppression de la clé 5 Racine: [1, 4, 8, 12] Étape 2: Ajustement de l'arbre B après la suppression Racine: [4, 8, 12] Cet exemple illustre comment un arbre B peut être utilisé pour gérer un fichier d'index, facilitant l'insertion, la recherche et la suppression efficaces des enregistrements. Les propriétés des arbres B, telles que l'équilibrage automatique lors des insertions et des suppressions, contribuent à maintenir des performances efficaces même avec des ensembles de données volumineux.  HACHAGE Fonction de hachage Méthodes de résolution de collisions Hachage statique Hachage dynamique Hachage : Le hachage est une technique utilisée en informatique pour associer des données à une position spécifique dans une structure de données, souvent une table de hachage, en utilisant une fonction de hachage. Cette fonction de hachage prend en entrée une clé et renvoie un indice (ou une adresse) dans la table de hachage où la valeur associée à cette clé est stockée. Le but du hachage est de permettre un accès rapide aux données en évitant une recherche séquentielle. Fonction de Hachage : Une fonction de hachage prend une clé en entrée et renvoie un indice dans la table de hachage. Une bonne fonction de hachage doit distribuer uniformément les clés pour minimiser les collisions (lorsque deux clés différentes produisent le même indice). Hachage Statique et Hachage Dynamique : 1. Hachage Statique : La taille de la table de hachage est fixe. Peut entraîner des collisions plus fréquentes si la table est petite. Simple à mettre en œuvre. 2. Hachage Dynamique : La taille de la table de hachage peut changer dynamiquement en fonction du nombre d'éléments. Réduit les risques de collisions avec une table de taille adaptative. Plus complexe à mettre en œuvre. Hachage Statique et Hachage Dynamique : 1. Hachage Statique : La taille de la table de hachage est fixe. Peut entraîner des collisions plus fréquentes si la table est petite. Simple à mettre en œuvre. CHOIX D’UNE ORGANISATION paramètres du choix exemple d’application  Exemple Dans les bases de données, l'indexation avancée peut impliquer l'utilisation de plusieurs types d'index et de techniques pour optimiser les performances des requêtes. Un exemple avancé d'indexation dans une base de données relationnelle (par exemple, MySQL) avec l'utilisation d'index uniques, d'index composites et d'index textuels : Considérons une base de données simple qui stocke des informations sur des livres et leurs auteurs. La structure des tables pourrait ressembler à ceci : CREATE TABLE Auteurs ( AuteurID INT PRIMARY KEY, Nom VARCHAR(50) NOT NULL ); CREATE TABLE Livres ( LivreID INT PRIMARY KEY, Titre VARCHAR(100) NOT NULL, AuteurID INT, AnneePublication INT, INDEX idx_AuteurID (AuteurID), FOREIGN KEY (AuteurID) REFERENCES Auteurs(AuteurID) ); Dans cet exemple, la table Auteurs stocke des informations sur les auteurs, et la table Livres stocke des informations sur les livres, y compris l'ID de l'auteur. Maintenant, voyons comment nous pourrions utiliser différents types d'index pour optimiser les requêtes.