Enoncé 10 : Fichiers structurés en listes linéaires chaînées - Méthodes d'index - Hachage externe    Corrigé 10

Exercice 1 : Méthodes d'index

1. Donner les structures de tables en RAM pour les méthodes:

(a) - Index primaire à un niveau

(b) - Index primaire à 2 niveaux

(c) - Index secondaire sous forme de listes inversées

2. Définir les modules nécessaires sans les écrire en spécifiant uniquement les paramètres d'entrée et de sortie pour effectuer une insertion d'article de clé donnée pour les méthodes (a), (b) et (c) de 1.

Exercice 2 : Hachage externe

1. Pour le chaînage séparé, la solution qui consiste à associer une liste linéaire chaînée de blocs pour chaque bloc primaire rempli n'est pas bonne.

(a) - Pourquoi ?

(b) - Proposer une solution en donnant un schéma

(c) - Décrire le schéma.

2. Quel est le nombre maximum de buffers utilisés pour effectuer :

(a) - une suppression physique dans l'essai linéaire,

(b) - une insertion dans le chaînage interne,

(c) - une insertion dans le chaînage séparé.

Exercice 3 : Méthode d'accès à un fichier de caractères (UNIX)

Considérons la méthode d'accès suivante à un fichier de caractères :

Le fichier est une liste linéaire chaînée bilatérale de blocs sur le disque. Chaque bloc contient 1024 caractères.

On veut effectuer les opérations suivantes :

- accès directement à un caractère de position donnée,

- récupérer les P suivants ( ou précédents) caractères à partir d'une position donnée,

- accès directement à la dernière position du fichier pour ajouter éventuellement d'autres caractères,

- etc. ..

Pour pouvoir faire l'accès direct , on doit disposer en RAM d'une table o� l'entrée I désigne le I-ième bloc de la liste linéaire chaînée.

Le premier bloc est spécial et est organisé comme suit :

- du premier au quatrième caractère : position libre du dernier bloc du fichier,

- du cinquième au sixième caractère : nombre de blocs de la liste linéaire chaînée,

- ensuite par groupe de 4 caractères les adresses des blocs 1, 2, dans cet ordre.

(a) Donner la structure de la table en RAM et celle du buffer.

(b) Ecrire les modules suivants :

- Chargement de la table.

- Récupération du N-ième caractère, N donné.

- Ajout d'un caractère C en fin de fichier.

- Récupération des N caractères qui précédent un caractère de position donnée.

Opérations à utiliser :

- Demandebloc (Type) : fonction qui fournit un numéro de bloc libre sur le disque.

- Lirebloc (F, I, Buffer) : transfert vers Buffer du bloc n� I du fichier.

- Ecrirebloc (F, I, Buffer) : transfert de Buffer vers le bloc n� I du fichier.

- Convert (C, N) : convertit une chaîne de caractères C en un entier N.

* * * * *