Corrigé 29. Enoncé
1. Méthode d'index avec format variable des articles
Nous rappelons ci-après les caractéristiques et les structures de données de l'énoncé
en répondant en même temps aux premières questions.
B = 4096 : capacité du bloc.
Fb_libre = B/8 : nombre maximal d'entrées par bloc.
Fb_index = (B-2)/14 : nombre maximal d'entrées par bloc d'index.
Max_libre = (B/8) * 10: taille maximale de la table des emplacements libres.
Taille_don : nombre total de blocs
alloués pour le fichier de données.
Taille_index : nombre de blocs alloués
pour le fichier d'index.
Der_index : numéro du dernier bloc
alloué du fichier d'index.
Der_don : numéro du dernier bloc alloué
au fichier de données.
D_don : déplacement libre dans ce bloc.
Nbr_entreesTlibre : nombre d'entrées dans Tlibre.
Structures de données
Fichier de données :
TYPE Type_don = TABLEAU[0..B-1] DE CAR
Fdon : Fichier DE Type_don { Fichier d'articles }
Fichier d'index :
TYPE Telmt = STRUCTURE
Cle :CAR
Num : ENTIER
Depl : ENTIER
FIN
TYPE Tindex = STRUCTURE
Nb : ENTIER
Tab : TABLEAU[0..Fb_index-1] DE Telmt
FIN
Findex : Fichier DE Tindex { Fichier d'index }
Buffers d'entrée/sortie :
Buf_don : Type_don
Buf_index : Tindex
Table des emplacements libres :
TYPE T = STRUCTURE
Bloc : ENTIER
Deplacement : ENTIER
FIN
Tlibre : TABLEAU[0 ..Max_libre-1] DE T
Module d'initialisation
{ Nombre total de blocs alloués au fichier de données }
Taille_don := 200
{ Nombre total de blocs alloués pour le fichier d'index}
Taille_index := 50
{ Adresse du dernier bloc utilisé }
Der_don := 10
{ Déplacement dans le dernier bloc utilisé Der }
D_don := 0
Der_index := 0
Nbr_entreestlibre := 0
{ Initialisation du premier bloc d'index }
Buf_index.Nb := 0
Ecrirebloc(Findex, 0, Buf_index )
Remarque :
Le module de création consiste à ranger ces informations dans le bloc 0 du fichier de
données et à initialiser le premier bloc d'index.
Découpage physique du bloc 0 contenant les caractéristiques
Position 0 - 3 : Taille_don
Position 4 - 7 : Taille_index
Position 8 - 11 : Der_don
Position 12 - 15 : D_don
Position 16-19 : Nbr_entreesTlibre
Position 20-23 : Der_index
Module d'ouverture du fichier
{ Récupérer les caractéristiques du fichier }
Lirebloc(Fdon, 0, Buf_don)
Recuperer(0, 4, Chaine)
Taille_don := Nombre(Chaine)
Recuperer(4, 4, Chaine)
Taille_index := Nombre(Chaine)
Recuperer(8, 4, Chaine)
Der_don := Nombre(Chaine)
Recuperer(12, 4, Chaine)
D_don := Nombre(Chaine)
Recuperer(16, 4, Chaine)
Nbr_entreestlibre := Nombre(Chaine)
Recuperer(20, 4, Chaine)
D_index := Nombre(Chaine)
{ Chargement de la table des espaces libres }
N := Nbr_entreestlibre
Ni := 0
K := - 1
TANTQUE( N > 0 )
Ni := Ni + 1
Lirebloc(Fdon, Ni,Buf_don)
M := Min (Fb_libre, N)
Le := 0
POUR I:=1, M :
{ Adresse du bloc }
Ecuperer(Le, 4, Chaine)
Adrbloc :=
Nombre(Chaine)
{ Déplacement }
Recuperer(Le + 4, 4,
Chaine)
Deplacement :=
Nombre(Chaine)
K := K + 1
Tlibre[K].Bloc :=
Adrbloc
Tlibre[K].Deplacement:=
Deplacement
Le := Le + 8
FINPOUR
N : N - Fb_libre
FINTANTQUE
Insertion dans le fichier d'index
Insertion du triplet ( Cle, Adresse, Déplacement) à la position Binf du bloc Milieu du
fichier d'index.
Inser_index ( Triplet, Milieu, Binf )
SI Buf_index.Nb < Fb_index
POUR I = Buf_index.Nb - 1, Binf, -1
Buf_index.Tab[I+1],
Buf_index.Tab[I]
FINPOUR
Buf_index.Tab[Binf] := Triplet
Buf_index.Nb := Buf_index.Nb + 1
Ecrirebloc(Findex,Milieu, Buf_index)
SINON
SI Der_index := Taille_index
"Saturation"
SINON
SI (Binf :=
Buf_index.Nb)
Sauv := Triplet
SINON
Sauv := Buf_index.Tab[Fb_index - 1]
POUR I = Buf_index.Nb -
2,Binf, -1
Buf_index.Tab[I+1]:= Buf_index.Tab[I]
FINPOUR
Buf_index.Tab[Binf] := Triplet
Ecrirebloc(Findex ,Milieu, Buf_index)
FSI
Milieu := Milieu + 1
SI Milieu >
Der_index)
Der_index := Milieu
Buf_index.Tab[0] := Sauv
Buf_index.Nb := 1
Ecrirebloc( Findex, Milieu, Buf_index)
SINON
Lirebloc(Findex, Milieu, Buf_index)
Continue := VRAI
TANTQUE ( Continue )
SI ( Buf_index.Nb < Fb_index )
POUR I := Buf_index.Nb-1, 0, -1
Buf_index.Tab[I+1]:=Buf_index.Tab[I]
FINPOUR
Buf_index.Tab[0] := Sauv
Buf_index.Nb := Buf_index.Nb + 1
Ecrirebloc (Findex, Milieu,Buf_index)
Continue := FAUX
SINON
SI ( Der_index := Taille_index)
Continue := FAUX ; " Saturation"
SINON
Sauv2:= Buf_index.Tab[Buf_index.Nb-1]
POUR I := Buf_index.Nb - 2,0,-1
Buf_index.Tab[I+1]:=Buf_index.Tab[I]
FINPOUR
Buf_index.Tab[0]:= Sauv
Ecrirebloc(Findex,Milieu,Buf_index)
Sauv := Sauv2
Milieu := Milieu + 1
SI Milieu > Der_index)
Der_index := Milieu
Buf_index.Tab[0] := Sauv
Buf_index.Nb := 1
Ecrirebloc(Findex, Milieu,Buf_index)
Continue := FAUX
SINON
Lirebloc(Findex, Milieu, Buf_index)
FSI
FSI
FSI
FINTANTQUE
FSI
FSI
FSI
Insère un article dans le fichier
Inserer( Cle, N)
Insertion d'un article de clé Cle et de ses N champs (N > 0). Les contenus des champs
ne sont pas pris en considération.
on utilisera le module Rech_index défini comme suit :
Rech_index( Cle, Trouver, Milieu, Mil, Binf)
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.
Rech_index ( Cle, Trouver, Milieu, Mil, Binf )
SI NON Trouver
{ Recherche de la première place dans la table
des blocs libres }
K := 0
Trouv := FAUX
TANTQUE K < Nbr_entreestlibre ET NON Trouv
Dif := ( B -
Tlibre[K].Deplacement )
SI Dif >:= (12+
(N*20))
Trouv := VRAI
Min := Dif
Res := K
SINON K := K + 1 FSI
FINTANTQUE
{ Y a t-il une autre plus petite }
POUR I:=K+1, Nbr_entreestlibre-1
Dif := B -
Tlibre[I].Deplacement
SI Dif >:= (12+
(N*20))
SI
Dif < Min
Min := Dif ; Res := I
FSI
FSI
FINPOUR
SI Trouv
Lirebloc
(Fdon,Tlibre[Res].Bloc, Buf_don)
{ Clé }
Recopier(Cle,
Tlibre[Res].Deplacement, 10)
{ N }
Recopier(Chaine(N),
Tlibre[Res].Deplacement+10, 2)
Ecrirebloc(Fdon,
Tlibre[Res].Bloc, Buf_don)
{ Pour l'insertion dans
le fichier d'index }
Triplet.Num :=
Tlibre[Res].Bloc
Triplet.Depl:=
Tlibre[Res].Deplacement
SI B -
(Tlibre[Res].Deplacement + 12+N*20) >:= 32
Tlibre[Res].Deplacement :=
Tlibre[Res].Deplacement + (10 + 2 + N*20 )
SINON
Tlibre[Res] := Tlibre[nbr_entreestlibre-1]
Nbr_entreestlibre := Nbr_entreestlibre - 1
FSI
SI (Tlibre[Res].Bloc :=
Der_don)
D_don := Tlibre[Res].Deplacement
FSI
SINON {Insertion à la fin }
SI (Der_don :=
Taille_don )
"Saturation du fichier de données "
SINON
Der_don := Der_don + 1
D_don := 0
Recopier(Cle, 0, 10)
Recopier(Chaine(N), 10, 2)
Ecrire_bloc(Fdon, Der_don, Buf_don)
SI B - (12+N*20) >:= 32
Nbr_entreestlibre:= Nbr_entreestlibre+1
Tlibre[ Nbr_entreestlibre-1].Bloc := Der_don
Tlibre[Nbr_entreestlibre-1].Deplacement:= 12+N*20
FSI
{ Pour l'insertion dans le fichier d'index }
Triplet.Num := Der_don
Triplet.Depl:= D_don
D_don := 12 + N*20
FSI
FSI
Triplet.Cle := Cle
Inser_index(Triplet, Milieu, Binf)
SINON
"Clé existe"
FSI
Calculs
Taille maximale du fichier :
Nombre moyen d'articles par bloc : B / (12+5*20) = 36
Valeur maximale de Taille_don : Fb_libre*10=5120 blocs
Taille maximale = 36 * 5120 = 184 320 articles
Tailles minimale et maximale pour avoir au plus 6 accès :
5 accès sur le fichier d'index, donc au plus 32 blocs d'index.
32 * Fb_index * 70% < X < 32 * Fb_index
6540 < X < 9344