Enoncé 26 : Méthodes d'index   Corrigé 26

Problème : Un système de gestion de fichiers avec réorganisation dynamique

Pour réaliser des opérations sur un fichier o� chaque article est composé de deux champs:

- la clé ( 5 caractères numériques )

- une chaîne de caractères de longueur variable,

on décide de structurer le fichier comme un ensemble de M blocs contigus sur le disque (de 0 à M-1). Chaque bloc est un tableau de B caractères (de 0 à B-1). En plus, pour pouvoir accéder directement à tout article, on maintient une table Tchaîne en mémoire centrale de Max éléments, triée selon la clé, o� chaque entrée est le quadruplé (Clé, Adresse, Déplacement, Longueur) avec :

- Clé : clé de l'article

- Adresse : adresse du bloc o� se trouve l'article

- Déplacement : indice dans le bloc ou commence l'article.

- Longueur : longueur de l'article.

On décide aussi de réserver les N premiers blocs pour y mettre les caractéristiques et l'index(table Tchaîne).

- le bloc 0 contient les caractéristiques du fichier.

- les (N-1) prochains blocs contiennent la table d'index.

- les blocs suivants contiennent les articles proprement dits.

NB.

* Une chaîne de caractères est assimilée à un tableau de caractères.

* La fonction Long(Y) donne la longueur de la chaîne contenue dans le tableau Y.

* la fonction Chaîne(Nombre) donne la chaîne de caractères associée au nombre Nombre.

* la fonction Nombre(Chaîne) donne le nombre (entier ou réel) associé à la chaîne de caractères.

* Un article peut commencer dans un bloc et finir dans un autre qui lui soit contigu. On dit qu'il est "à cheval" sur 2 blocs.

* Un bloc d'index contient un nombre entier d'entrées de la table d'index.

* La longueur maximale d'un article est la taille du bloc.

Dans l'exemple qui suit , on obtient la configuration suivante après l'insertion des articles suivants(dans cet ordre) ( B = 50 et N = 10 ):

article1 = 34537aaaaaaaaaaaaaaa

article2 = 12345bbbbbbbbbbbb

article3 = 53721ccccc

article4 = 33333xxxxxxxxxxxxxxxxxxxxxxxxx

article5 = 00000yyyyyyyyyyyyyyyxxxxxxxxxxxxxxxxxxxxxxxxy

Le fichier

Bloc 10 :

51 52 53 51 55 97 97 97 97 97 97 97 97 97 97 97 97 97 97 97 49 50 51 52 53 98 98 98 98 98 98 98 98 98 98 98 98 53 51 55 50 49 99 99 99 99 99 51 51 51

Bloc 11 :

51 51 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 48 48 48 48 48 121 121 121 121 121 121 121 121 121 121 121 121 121 121 121 120 120 120

Bloc 12 :

120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 121 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32

NB : quelques codes

'x' = 120; 'y' = 121; 'a' = 97; 'b' = 98 ; 'c' = 99;

'0' = 48 ; '1' = 49 ; '2' = 50 ; etc.

Questions

*Initialisation : Définir tous les paramètres nécessaires à l'exploitation du fichier (caractéristiques) et dire comment les initialiser.

*Organisation des N premiers blocs : Donner une organisation possible du bloc 0 contenant les caractéristiques du fichier et une organisation possible des blocs contenant la table d'index (fournir des schémas respectifs).

*Fermeture : Ecrire le module qui sauvegarde les caractéristiques et la table d'index.

Afin d'éviter la réorganisation, on décide de récupérer dynamiquement les fragments d'espace devenus inaccessibles ("trous") par des suppressions d'articles. Pour cela, on maintient une liste linéaire chaînée de "trous" sur le disque.

- Que faut-il mettre dans ces trous ?

- Donner une organisation possible.

- Peut-on récupérer l'espace à 100% ? justifier.

* Gestion des trous

Ecrire les modules de :

- Recherche d'un trou de longueur supérieure ou égale à une longueur L donnée.

- Insertion d'un trou.

* Opération d'insertion et de suppression :

Paramètre les modules de gestion des "trous" pour écrire:

- le module de suppression d'un article de clé X donnée.

- le module qui insère un article de clé K donnée et de chaîne Y donnée.