Précédent Remonter Suivant

Chapitre 7  Organisation Physique

Exercice A :
On prend ici comme exemple la relation Directeur (nom_directeur, nom_film).
  1. Organisation Séquentielle : Expliquer l'organisation séquentielle et représenter un exemple sur la relation Directeur. Montrer le fichier après une insertion et après quelques suppressions d'articles.

    Les articles sont stockés les uns derrière les autres dans des pages successives. L' avantage de cette structure physique est sa simplicité. En particulier, il n'existe pas d'ordre entre les articles. La seule façon d'accéder à un article est par balayage séquentiel: on parcourt le fichier en séquence, page par page: chaque page est lue en mémoire: les articles dans la page sont alors parcourus séquentiellement. On lit chaque article et le sélectionne si la valeur de ses champs correspond au(x) critère(s) de recherche. Un exemple d'une organisation séquentielle pour la relation Directeur se trouve dans la Figure 7.1
    ./figures/sequentiel.eps
    Figure 7.1 : Organisation Séquentielle de la relation Directeur



  2. Organisation Indexée : Montrer des exemples d'index non dense (primaire) et dense (secondaire) sur la relation Directeur.

    On illustre dans les Figures 7.2 et  7.3 des exemples d'index non dense respectivement sur l'attribut directeur et sur l'attribut nom de film. L'index est ordonné sur le même attribut que le fichier. Dans la figure 7.4 on montre deux index denses, l'un sur l'attribut directeur l'autre sur le nom du film. L'index est trié sur la clé alors que l'ordre des articles dans le fichier est quelconque. Deux remarques sont importantes: on a supposé dans ces exemples que l'index tient dans une page (feuille unique). Il faut se rappeler qu'en pratique, l'index a une structure arborescente (Arbre B, voir http://deptinfo.cnam.fr/CycleA/SD/ pour une démonstration en ligne de l'arbre B et des tris). Ensuite, l'exemple dans la figure 7.4 suppose qu'on associe à une valeur de clé ``c'' dans l'index une adresse de page (où se trouvent un ou plusieurs nuplets ayant ``c'' pour valeur de l'attribut clé). En fait la plupart du temps, ce n'est pas une adresse de page, mais une adresse complète du nuplet (adresse de page et adresse dans la page, voir cours) qui est associée à ``c'' dans l'index. Ceci a pour conséquence, que s'il y a ``n'' nuplets dans la page ayant pour valeur de clé ``c'', il y aura ``n'' couples (``c, adresse de nuplet) dans l'index.
    ./figures/index_nondense_directeur.eps
    Figure 7.2 : Index non dense sur l'attribut nom_directeur de la relation Directeur

    ./figures/index_nondense_film.eps
    Figure 7.3 : Index non dense sur l'attribut nom_film de la relation Directeur

    ./figures/index_dense.eps
    Figure 7.4 : Index dense



Exercice B :
Construire un index sur la date de naissance des musicien (arbre B, ordre 2) : 
          Monteverdi    1589
          Couperin      1668
          Bach          1685
          Rameau        1684
          Debussy       1862
          Ravel         1875
          Mozart        1756
          Faure         1856
fi-arbre-b-dates.ps

Exercice C :
Construire un index sur les noms des musicien (arbre B, ordre 2).

fi-arbre-b-noms.ps

Exercice D :
Construire un arbre B+ d'ordre 2 sur les numéros de département. 
            3       Allier
            36      Indre
            18      Cher
            9       Ariège
            11      Aude
            12      Aveyron
            73      Savoie
            55      Meuse
            46      Lot
            39      Jura
            81      Tarn
            25      Doubs
            15      Cantal
            51      Marne
            42      Loire
fi-arbre-b+-dept.ps

Exercice E :
Soit le fichier séquentiel suivant (on ne donne pour chaque article du fichier que la clé sur laquelle on construit l'arbre): 1 15 3 12 6 4 11 7 2 5 14 8 9 17 10 13 16. L'index en arbre B d'ordre 2 après l'insertion des clés 1 15 3 12 6 4 11 7 2 5 14 8 est montré dans la figure suivante :

fi-arbre-b-1-avant.ps
  1. Donnez l'arbre résultant après l'insertion de tous les articles du fichier séquentiel.

    fi-arbre-b-1-apres.ps

  2. Combien de noeuds différents (racine et feuilles compris) doit-on parcourir dans l'index pour répondre à la requête qui cherche les articles dont la clé appartient à l'intervalle [5,10].

    Il faut parcourir 6 noeuds : [9], [3,6], [4,5], [7,8] [12, 15], [10,11].
Exercice F :
Soit les fichiers séquentiels suivants (on ne donne pour chaque article du fichier que la clé sur laquelle on construit l'arbre) :
  1. Construire un index en arbre B d'ordre 2 pour chacun des fichier.
    1. fi-arbre-b-2.ps

    2. fi-arbre-b-3.ps
    3. fi-arbre-b-4.ps


  2. Construire un index en arbre B+ d'ordre 2 pour chacun des fichier.
Précédent Remonter Suivant