Gestion de Fichiers

GF-1: Introduction à la Géstion des Fichiers et

Opérations de Base

2

Organisation du Cours Professeur: Dr. Nathalie Japkowicz, STE 5-029, x6693,

nat@site.uottawa.ca. Heures de Consultation: Lundi 13h15-14h15.

Jeudi 14h45-15h45 Heures de Cours: Lundi, 14h30-15h50 (Morisset 221)

Jeudi, 16h00-17h30 (Morisset 221) Heures de Laboratoire:

Mercredi, 8h30-10h00 (STE 0130) Manuel de Cours: File Structures, An Object-Oriented

Approach with C++, by Michael J. Folk, Bill Zoellick & Greg Riccardi, Addison Wesley

3

Objéctifs du Cours L’Etude des Structures de Fichiers avec

le but d’améliorer l’efficacité de l’accès aux données en mémoire secondaire.

L’ étude des outils les plus importants pour l’organisation des fichiers, tels que les indexes, les processus co-séquentiels, les arbres B et B+ et l’addressage dispersé (HashCoding).

L’acquisition de bonnes bases de programmation en C++.

4

Evaluation 30% Devoirs (D)

3 Devoirs (quelques questions écrites et quelques questions de programmation)

25% Examen de Mi-Session (M) 45% Examen Final (F) If (.25 M + .45 F)/.7 < 50% then Note Finale = (.25 M + .45 F) /.7 If (.25 M + .45 F)/.7 ≥ 50% then Note Finale = (.25 M + .45 F

+ .3 D) Retard dans la remise des devoirs:

penalité de 10% pour tout retard; aucun devoir ne sera accepté apres 24h00 de la date et heure de remise des devoir.

5

Plan du Cours d’Aujourd’hui

Que sont les Structures de Fichiers? Pourquoi étudier la Gestion de Fichiers? Une vue générale de la conception des

Structures de Fichiers. Histoire de la Discipline. Une Introduction au C++

D’après Folk, Zoellick and Riccardi, Chapitre 1.

6

Définition Une structure de Fichier est une combinaison

1. de représentations pour les données sauvegardées dans des fichiers, et

2. d’opérations pour accéder a ces données. Une structure de Fichier permet aux applications de

lire, écrire et modifier les données. Elle peut aussi permettre de trouver les données correspondant a certains critères de recherche ou de lire les données dans un ordre particulier.

Les Structures de Données s’addressent a l’organisation de données en mémoire principale. Les Structures de Fichiers s’addressent a l’organisation des données en mémoire secondaire.

7

Storage des Données Les données sur ordinateur peuvent etre sauvegardées

dans trois types de location differents: En Storage Primaire: Mémoire de l’ordinateur (RAM) En Storage Secondaire: Cassette Magnétique,

Disque Dur, Disquette, CD-ROM, ZipDrive, USB Drive qui peuvent etre accédés par l’ordinateur.

En Storage Tertiaire ou Données d’Archives: Cassette Magnétique, Disque Dur, Disquette, CD-ROM, ZipDrive, USB qui ne peuvent pas etre accédés directement par l’ordinateur.

Notresujet

8

Différence entre le Storage Primaire et Secondaire

Le storage secondaire tel que les disques peuvent accumuler des milliers de mégabytes en utilisant tres peu d’espace physique.

Le storage primaire (i.e., la mémoire, le RAM), au contraire, est très limitée.

Cependant, l’accès au storage secondaire est très lent par rapport a l’accès au storage primaire: [Example: l’accès aux données sauvegardées en RAM lente prend 60 nanosecondes. Il prend 15 millisecondes lorsque les données sont sauvegardées sur disque.]

9

Pourquoi Etudier les Structures de Fichiers?

L’ étude des structures de fichiers est entreprise afin d’améliorer le temps d’accès au storage secondaire.

Etant donné que les détails de la représentation des données et des opérations associées a ces données déterminent l’efficacité des structures de fichiers (en fonction de l’application considerée), l’amélioration de ces détails peut améliorer le temps d’accès au storage secondaire.

10

Une Vue Générale de la Concéption des Structures de Fichiers I

But General: Obtention de l’information requise avec un seul accès au disque.

Si cela n’est pas possible: Obtention de l’information requise avec aussi peu d’accès au disque que possible.

En général, nous allons essayer de grouper toutes les informations requises par les utilisateurs du système de facon a pouvoir y accéder avec un seul accès au disque.

11

Une Vue Générale de la Concéption des Structures de Fichiers II

Fichiers Fixes et Fichiers Dynamiques Il est assez simple de trouver des structures

de fichiers efficaces (qui adhèrent aux buts généraux de la discipline) lorsque les fichiers ne changent pas pendant l’execution du système.

Par contre, si les fichiers peuvent s’aggrandir ou rapetisser, il est beaucoup plus difficile d’atteindre ces buts.

12

Histoire de la Discipline I: Au Début, l’Accès Séquentiel L’histoire de la discipline est très

intimement liée au développements téchniques associés aux ordinateurs et a leur usage pratique.

Au début, les fichiers étaient sauvegardés seulement sur cassettes magnétiques.

L’accès etait donc séquentiel et son cout grandissait proportionellement avec la taille du fichier.

13

Histoire de la Discipline II: l’Emergence des Disques et des Indexes

Lorsque les fichiers ont commencé a grandir de facon demesurée, l’accès sequentiel pur n’était plus une solution.

Les disques ont permis l’accès direct. Les indexes ont donné la possibilité de sauvegarder

des petits fichiers ne contenant qu’une liste de clés associées a des pointeurs. La recherche séquentielle dans ces petits fichiers pouvaient etre faite très rapidement.

La clé et le pointeur donnait l’accès direct au très grand fichier principal contennant les données.

14

Histoire de la Discipline III: l’Emergence des d’Arbres de Recherche

Les indexes ont eux aussi commencé a grandir de manière demesurée. Comme ils avaient une structure séquentielle, ils sont eux aussi devenu difficile a gérer.

L’idée d’utiliser des structures d’arbres de recherche afin de gérer l’index est apparue au début des années 60.

Cependant, les arbres de recherches peuvent grandir de facon tres inégale lorsque les enregistrements sont ajoutés ou effacés. Ceci resultait en des recherches tres longues nécéssitant plusieurs accès au disque avant de trouver l’enregistrement requis.

15

Histoire de la Discipline IV: l’Emergence des d’Arbres Equilibrés

En 1963, l’idée des arbres AVL a émergé pour les données sauvegardées en storage primaire.

Cette idée, cependant, ne s’appliquait pas au storage secondaire car les arbres AVL sont utiles lorsque les noeuds d’arbres sont composés d’enregistrements simples plutot que de douzaines ou centaines d’enregistrements.

Dans les années 70, l’idée des arbres B a émergé. Ces arbres ont un temps d’accès de O(logkN) ou N est le nombre d’enregistrements dans le fichier et k, le nombre d’enregistrements indexés dans un simple bloc de l’arbre B. => Les arbres B peuvent garantir une recherche ne nécéssitant que 3 ou 4 acces au disque pour un fichier de millions d’enregistrements.

16

Histoire de la Discipline V: L’Addressage Dispersé

Bien que la possibilité de trouver des données sauvegardées en storage secondaire avec 3 ou 4 accès au disque est impressionante, elle n’atteint pas le but fixé de trouver des données en un simple accès.

Depuis très longtemps, l’addressage dispersé (ou HashCoding) était un moyen connu d’atteindre ce but dans les fichiers dont la taille ne changeait pas beaucoup pendant l’utilisation du systeme.

Plus récemment, le HashCoding dynamique extensible garantit un ou, au plus, deux accès au disque quelle que soit la taille du fichier.

17

Une Introduction au C++ Le C++ a été créé par Bjarne Stroustrup. C++ a conservé l’efficacité du C tout en y

ajoutant la puissance de l’héritage d’objets. C++ vs. Java:

Java est basé sur le C++ mais est un langage plus simple.

Néanmoins, Java n’a pas autant de flexibilité que le C++ car il repose sur des concepts de plus haut niveau. Par example, Java n’a pas de pointeurs.