Le fichier est une suite contigu� de blocs sur le disque numérotés 1, 2, .. M. Tous les articles dans le bloc I ont des clés inférieures à celles des articles du bloc I+1 ( 1 <= I < M). A l'intérieur d'un bloc, les articles sont ordonnés selon leurs clés. Autrement dit, le fichier est ordonné. En plus, les articles sont de longueur fixe.

Initialement, on remplit le fichier à raison de � % par bloc par des clés arrivant en ordre croissant ( chaque lecture délivre le prochain article)

Une insertion d'article est faite comme suit :

(a) s'il y a de la place dans le bloc, l'article est inséré à sa bonne position.

(b)s'il n'y a pas de place dans le bloc, l'article est inséré dans un bloc d'un autre fichier F', qui est une liste linéaire chaînée de blocs. De plus, tous les articles issus d'un même bloc sont chaînés entre eux et sont ordonnés selon la clé.

Une suppression est faite tout simplement par le positionnement d'un champ d’effacement au niveau de l'article.

- Donner la structure du bloc du fichier F

- Donner la structure du bloc du fichier F'

- Ecrire le moule de chargement initial

- Ecrire le module de recherche

- Ecrire le module de suppression

- Quelles informations doit-on sauvegarder à la fermeture du fichier?

On veut réorganiser le fichier en construisant un autre fichier Fres avec 2M blocs remplis chacun à � %.

a) A quel moment doit-on faire cette réorganisation pour que d'une part le fichier F' soit complètement éliminé et d'autre part le nouveau fichier Fres soit rempli à � %.

b) Donner l'algorithme correspondant.

Exercice 2 : Implémentation d'une file d'attente

Soit l'implémentation suivante :

Fin

o� l'opération Créerfile est définie comme suit :

Allouer (S, Q)

F.Tête := Q ; F.Queue := Q

o� F est un objet de type Typefile.

Le premier élément de la liste linéaire chaînée ne fait donc pas partie de la file d'attente.

- Retrouver les autres modules du modèle : Filevide, Enfiler et Défiler.

Exercice 3 : Accès multi-critères

On veut faire des accès par 2 clés secondaires C1 et C2 données.

- Donner le schéma général des tables d'index en RAM.

- Donner leur description algorithmique.

- Donner le pseudo-algorithme ( en faisant apparaître le différents modules) qui recherche tous les articles de clés secondaires C1 et C2 données.

- Dire comment se fait une suppression d'article de clé primaire donnée dans une telle méthode. Justifier.

- Faut-il changer la structure des tables? si oui, comment ?

- Donner l'algorithme correspondant.