Enoncé 29. Méthodes d'index   Corrigé 29

Problème : Méthode d'index avec format variable des articles

Méthode d'accès : Utilisation d'un fichier d'index ordonné non présent en mémoire centrale pendant l'exploitation du fichier et d'un fichier de données non ordonné. Les blocs d'index et de données sont de même taille B. Le bloc est l'unité de transfert. On prendra B=4K=4096.

Organisation interne du fichier de données : format variable des articles. Un article est composé d'une clé sur 10 caractères, du nombre de ses champs sur 2 caractères et de n champs (n > 0) à raison de 20 caractères par champ.

Format d'un article :

10c 2c 20c,.... 20c

<------><----><---------> ..... <--------->

Clé           n     Champ1          Champn

Un article ne doit pas être à cheval sur deux blocs.

Table des espaces libres : Afin de récupérer dynamiquement l'espace libre dans les blocs ( dû au non chevauchement des articles ), on maintient un table TLIBRE sur le disque contenant les adresses des espaces non utilisés. Une entrée de cette table, dans le bloc, a le format suivant :

4 c 4 c

<---------------><----------------------->

Adresse du bloc Position dans le bloc

La table n'est pas triée et est chargée en mémoire centrale à l'ouverture du fichier.

Structure du fichier de données : Le fichier est un ensemble de TAILLE_DON blocs contigus sur le disque répartis comme suit :

- Le bloc 0 du fichier contient les caractéristiques du fichier, c'est à dire l'ensemble des informations utiles pour la gestion du fichier.

- Les blocs 1 à 10 contiennent donc la table des emplacements libres.

- Les blocs 11 à TAILLE_DON - 1 sont destinés pour les articles.

Structure du fichier d'index : Le fichier d'index est ordonné et est un ensemble de TAILLE_INDEX blocs contigus sur le disque. Chaque bloc contient au maximum FB_INDEX triplets (Clé, Adresse, Déplacement). On suppose aussi que l'opération de chargement initial remplit les blocs à 70%.

Opération d'insertion : Une insertion se fait donc de la façon suivante : si l'article n'est pas dans le fichier, il est inséré

- soit dans l'emplacement libre, fourni par TLIBRE, tel que la différence entre la longueur de l'article et celle disponible dans le bloc soit minimale.

- soit dans le prochain bloc ajouté pour le fichier.

Attention : S'il reste dans un bloc, un espace inférieur à 32, il sera perdu.

Questions :

Déterminer en fonction de B,

- FB_LIBRE : le nombre maximal d'entrées par bloc des espaces libres.

- FB_INDEX : le nombre maximal d'entrées par bloc d'index.

- MAX_LIBRE: la taille maximale de la table TLIBRE en mémoire centrale.

Définir toutes les structures de données nécessaires. ( Fichiers d'index et de données, TLIBRE)

Que doit contenir le bloc 0. Donner son découpage physique, puis écrire le module d'ouverture du fichier. En déduire le module de création du fichier.

Ecrire le module INSER_INDEX( Triplet, M, Pos) qui insère le triplet ( Cle, Adresse du bloc, Déplacement) à la position Pos du bloc M du fichier d'index.

Utiliser INSER_INDEX et RECH_INDEX pour écrire le module d'insertion d'un article de clé donnée et de ses n champs donnés.

On utilisera le module RECH_INDEX (sans l'écrire) défini comme suit :

RECH-INDEX( Cle, Trouv, Milieu, Mil, Binf) :

Recherche la clé Cle dans le fichier d'index. Si Trouv est VRAI, la clé est trouvée dans le bloc Milieu à la position Mil. Si Trouv est FAUX, Milieu pointe le bloc qui devrait contenir la clé recherchée et Binf la position o� elle devrait se trouver dans ce bloc.

On utilisera exclusivement les deux buffers suivants en mémoire centrale : BUF_DON pour le fichier de données et BUF_INDEX pour le fichier d'index.

Quelle est la taille maximale du fichier de données (en nombre d'articles) si on suppose que le nombre moyen de champs par article est 5. Justifier.

Quelle sont les tailles minimale et maximale que doit contenir le fichier pour que toute recherche d'article ne dépasse pas les 6 accès disque. Justifier.

N.B :

* Un entier occupe 2 octets.

* Un article est lu avec l'opération Lire(Clé, n), n étant le nombre de champs.

Clé est une chaîne de caractères qui peut aussi être utilisée comme un tableau de caractères.

* Il est conseillé d'utiliser les 4 modules suivants ( sans les écrire):

- Récupérer (I, L, Chaine) qui récupère dans Chaine la chaîne de caractères commençant à la position I et ayant une longueur égale à L dans le buffer présent en RAM.

- Recopier( Chaine, L, I) qui recopie la chaîne Chaine dans le buffer présent en RAM à partir de la position I sur une longueur de L position).

- Chaine( Entier ) : donne la chaîne de caractères associée à l'entier Entier.

- Nombre ( Chaîne ) : donne l'entier associé à la chaîne de caractères Chaîne.

* * * * *