a)

Etant donné qu'un bloc de données dispose de 1536 octets et qu'une donnée occupe 76 octets, il peut y avoir au plus 20 données par bloc (1536 div 76=20 et restent 16 octets qui peuvent être utilisés pour pointer vers le bloc suivant et vers un eventuel bloc de débordement).

Du fait que les blocs ne sont initialement remplis qu'à 80%, il n'y aura que 16 données par bloc (20*80/100 = 16). Il faudra donc 62'500 blocs de données pour stocker 1'000'000 éléments (1'000'000/16 = 62'500).

Pour ce qui est des blocs d'index, chaque élément du bloc est composé d'une clé de 8 octets et d'une référence de 4 octets, soit 12 octets par élément. Il y a donc 85 éléments par bloc d'index (1024 div 12 = 85, reste 4).

La première couche de blocs d'index, qui pointent vers des blocs de données, doit contenir un élément par bloc de données. Il y a donc 736 blocs (62'500 div 85 = 735, reste 25; c'est-à-dire qu'il y a 735 blocs entièrement pleins et le dernier bloc ne contenant que 25 éléments).

La deuxième couche de blocs d'index occupe 9 blocs (736 div 85 = 8, reste 56 -> 8 blocs pleins et le neuvième avec 56 éléments). La troisième et dernière couche de blocs d'index ne contient qu'un seul bloc, avec seulement 9 éléments sur 85 occupés.

La taille de l'espace disque occupé est donc: (nombre de blocs de données*taille d'un bloc de données) + (nombre de blocs d'index*taille d'un bloc d'index) = 62'500*1536 + (736+9+1)*1024 = 96'763'904 octets.

En résumé:

• nombre de blocs de données = 62'500
• profondeur de l'arborescence d'index = 3
• nombre de blocs d'index = 736 puis 9 puis 1
• espace disque occupé = 96'763'904

b)

Etant donné qu'une page du B-arbre dispose de 1024 octets et qu'il faut stocker une référence de plus que de données, en supposant que l'on utilise 2 octets pour stocker le nombre d'éléments effectifs dans la page, il peut y avoir ((1024-4-2) div (76+4) = 12, reste 58 octets inutilisés). Le B-arbre est donc d'ordre 6.

Si l'on suppose que toutes les pages sont pleines, 1'000'000 éléments occuperaient alors 83'334 pages (1'000'000 div 12 = 83'333, reste 4 éléments qui vont occuper partiellement la 83'334ème page).

Si, à l'autre extrème, l'on suppose que les pages ne sont qu'à moitié pleines, 1'000'000 éléments occuperont alors 166'667 pages (1'000'000 div 6 = 166'666, reste 4 éléments qui vont occuper une page de plus).

L'espace disque nécessaire sera donc compris entre 85'334'016 octets (83'334*1024) et 170'667'008 octets (166'667*1024).

Pour ce qui est du nombre de niveaux de l'arborescence, il faut là aussi envisager les 2 cas extrèmes de pages toutes entièrement pleines ou toutes à moitié pleines:

• Quand les pages sont entièrement pleines, chaque page a 13 descendants. On peut facilement calculer le nombre de pages à chaque niveau puisque ce sont les puissances successives de 13: 1, 13, 169, 2197, 28561, 371'293. On voit alors facilement qu'il faut 6 niveaux pour avoir les 83'334 pages nécessaires pour stocker les 1'000'000 éléments.
• Dans le cas le plus défavorable où la racine ne contient qu'un seul élément (et deux descendants) et toutes les autres pages 6 éléments (et 7 descendants), les niveaux successifs contiennent: 1, 2, 14, 98, 686, 4802, 16'807 et, finalement 235'298 pages. Cela correspond à 2*7^n-2 pages pour le niveau n. On voit donc qu'il faut 8 niveaux dans ce cas.

En résumé:

• nombre de pages: entre 83'334 et 166'667
• espace disque: entre 85'334'016 et 170'667'008 octets
• niveaux: entre 6 et 8.

Site Hosting: Bronco