Corrigé 32. Enoncé
1. Index secondaires dynamiques
Structures de Données
Structure du bloc du fichier de données.
TYPE Type_bloc_donnée = Tab1 : TABLEAU[1..B] DE Type_article
Type_article = STRUCTURE
Cp : Type_clép
X, Y, Z : Type_clés
FIN
Nous supposons que X, Y et Z sont de même type et que Type_Clép et Type_Clés sont munis
de relations d'ordre.
Structure de la table d'index secondaire
TYPE Adresse = POINTEUR(Type_index_s)
TYPE Type_index_s = TABLEAU[1..N] DE Type_couple_s
TYPE Type_couple_s = STRUCTURE
Cs : Type_clé_s
Cp : Type_clé_p
FIN
Variables globales utilisées :
B : capacité du bloc du fichier de données.
Buffer : buffer d'entrée/sortie pour le fichier de données.
Nbr_Blocs : nombre de blocs du fichier de données.
Nbr_Articles : nombre d'articles du fichier de données.
A tout moment Ax, Ay et Az désignent les adresses mémoires des index secondaires sur X,
Y et Z respectivement. Elles sont initialisées à NIL. De plus, KX, KY et KZ
représentent les nombres de clés secondaires respectives. Elles sont initialisées à 0.
Création automatique d'un index secondaire à l'aide de
l'opération INDEXER(attribut)
Soit une variable T de type Adresse ( contient l'adresse de la table d'index secondaire
allouée dynamiquement )
L'algorithme qui suit suppose qu'il y a suffisamment de place dans la table T pour ranger
toutes les clés secondaires.
Allouer_Index(T, Type_indes_s)
K := 0
POUR I =1, Nbr_blocs
Lirebloc(F, I, Buffer)
POUR J=1, Min(B, Nbr_articles - (I-1)*B)
{ Récupérer la clé
secondaire de l'article courant}
SI Attribut =
"X"
Cs := Buffer(J).X
SINON
SI Attribut = "Y"
Cs := Buffer(J).Y
SINON
SI Attribut = "Z"
Cs := Buffer(J).Z
FSI
FSI
FSI
{ Déterminer la
position o� la nouvelle clé secondaire sera insérée}
Bi := 1
Bs := K
Trouv := FAUX
TANTQUE Bi <= Bs ET
NON Trouv :
M := (Bi + Bs) DIV 2
SI T^(M).Cs = Cs
Trouv := VRAI
SINON
SI T^(M).Cs > Cs
Bs := M - 1
SINON
Bi := M + 1
FSI
FSI
FINTANTQUE
SI Trouv : L := M SINON
L := Bi FSI
{Décalage et
insertion}
POUR
P=K, L, -1 :
T^(P+1).Cs := T^(P).Cs
FINPOUR
T^(L).Cs := Cs
T^(L).Cp :=
Buffer(J).Cp
K := K + 1
FINPOUR
FINPOUR
SI Attribut = "X"
Ax := T; Kx := K
SINON
SI Attribut = "Y"
Ay := T ; Ky := K
SINON Az := T; Kz := K FSI
FSI
Recherche du plus petit indice L de la plus petite clé supérieure
ou égale à une clé A donnée dans l'index secondaire sur "attribut" créé
Rech(attribut, A, L) :
T := Adr(Attribut)
Bs := Long(Attribut)
Bi := 1
Trouv := FAUX
TANTQUE Bi <= Bs ET NON Trouv :
M := (Bi + Bs) DIV 2
SI T^(M).Cs = A
Trouv := VRAI
SINON
SI T^(M).Cs > A
Bs := M - 1
SINON
Bi := M + 1
FSI
FSI
FINTANTQUE
SI NON Trouv : L := Bi
SINON
SI M = 1
L := 1
SINON
SI T^(M-1) # A :
L := M
SINON
L := M-1
Arret := FAUX
TANTQUE L >= 1 ET NON Arret :
SI T^(L).Cs = A :
Sauv := L
L:=L-1
SINON
Arret := VRAI
FSI
FINTANTQUE
L := Sauv
FSI
FSI
FSI
Requête R1 : ensemble des articles ayant Cs comme clé secondaire
sur l'attribut Attribut.
Rech(Attribut, Cs, L)
T := Adr(Attribut)
K := Long(Attribut)
Arret := FAUX
TANTQUE L <= K ET NON Arret :
SI T^(L).Cs = Cs
Rd(T^(L).Cp, I) {
Recherche dichotomique }
SI NON Efface(I)
Lirebloc(F, Num_bloc(I), Buffer)
Ecrire(Buffer(Depl(I) )
FSI
L := L + 1
SINON
Arret := VRAI
FSI
FINTANTQUE
Requête R2 : ensemble des clés secondaires dans l'intervalle[A, B]
sur l'attribut Attribut1 et dans l'intervalle [C, D] sur l'attribut Attribut2.
Rech(Attribut1, A, L1)
Rech(Attribut2, C, L2)
T1 := Adr(Attribut1); K1 := Long(Attribut1)
T2 := Adr(Attribut2); K2 := Long(Attribut2)
Arret1 := ( FAUX OU L2 > K )
TANTQUE L1 <= K1 ET NON Arret1
SI T1^(L1).Cs > B :
Arret1 := VRAI
SINON
Cp := T1^(L1).Cp
Arret2 := FAUX; Trouv
:= FAUX
I := L2
TANTQUE I <= K2 ET
NON Arret2 ET NON Trouv :
SI T2^(I).Cs > D : Arret2 := VRAI
SINON
SI Cp = T2^(I).Cp
Trouv:= VRAI
Rd( Cp, J)
SI NON Efface(J)
Lirebloc(F, Num_bloc(J), Buffer)
Ecrire(Buffer.Depl(J))
FSI
SINON
I := I + 1
FSI
FSI
FINTANTQUE
L1 := L1 + 1
FSI
FINTANTQUE
Interprétation et Calcul
. Les articles fournis par R1 sont dans un plan de l'espace(X, Y, Z).
. Les articles fournis par R2 sont dans une région de l'espace(X, Y, Z). Cette région
est le parallélépipède de largeur = (B - A +1), hauteur = (D - C +1) et de longueur (la
plus grande clé secondaire - la plus petite clé secondaire selon l'attribut non
spécifié dans la requête)
. Quand tous les index sont présents en mémoire, la table d'index primaire occupe 50K.
Le nombre maximal d'articles que l'on peut avoir est donc (1024/8) * 50 = 6400