View
106
Download
0
Category
Preview:
Citation preview
11/04/23 © Robert Godin. Tous droits réservés. 1
8 Organisations unidimentionnelles : indexage et hachage
Sélection basée sur une clé d'accès – recherche associative
– Ex: Chercher le plant dont le noCatalogue = 10 Sériel
– lire tout le fichier en pire cas
– O(N)
Indexage– O(log(N))
– sélection par intervalle
Hachage– ~O(1)
11/04/23 © Robert Godin. Tous droits réservés. 2
8.1 Indexage Index et clé d'index (index key)
– valeur de la clé =>adresse de(s) l'enregistrementNum érode bloc
Num érod'enregistrem ent
relatif
0
1
0
1
2
3
4
5
6
7
8
9
10 Cèdre en boule 10.99
40
90
60
50
Epinette bleue
Pom m ier
Erable argenté
Chêne
25.99
25.99
15.99
22.99
26.99
12.99
10.99
15.99
Poirier
Sapin
Herbe à puce
Génév rier
80
20
70
95
25.99Catalpa81
10 0
20 8
40 1
50 4
60 3
70 7
80 9
81 5
90 2
95 6
Index
Index dense secondaire
11/04/23 © Robert Godin. Tous droits réservés. 3
Fichier séquentiel indexé
Non dense
Index plus petit
Accès séquentiel rapide
Primaire
10 0
70 1
IndexNum érode bloc
Num érod'enregistrem ent
relatif
0
1
0
1
2
3
4
5
6
7
8
9
10 Cèdre en boule 10.99
20
40
50
60
Sapin
Epinette bleue
Chêne
Erable argenté
12.99
25.99
22.99
15.99
15.99
25.00
25.99
26.99
Génév rier
Pom m ier
Catalpa
Poirier
95
90
81
80
10.99Herbe à puce70
11/04/23 © Robert Godin. Tous droits réservés. 4
Index séquentiel hiérarchique
Ex: ISAM de IBM Zone de débordement
Réorganisations chroniques
10 Cèdre en boule 10.99
20
40
50
Sapin
Epinette bleue
Chêne
12.99
25.99
22.99
60 Erable argenté 15.99
10.99Herbe à puce70
25.99
26.99
Catalpa
Poirier
81
80
15.99
25.00
Génév rier
Pom m ier
95
90
10
40
Niveau 2d'index
60
80
90
... ...
10
80
... ...
Niveau 1d'index
11/04/23 © Robert Godin. Tous droits réservés. 5
8.1.1 Indexage par Arbre-B et variantes Arbre-B (B-arbre, B-tree)
– forme d ’index hiérarchique
– équilibré
– O(log(N)) en pire cas
Réorganisation dynamique
– division/fusion des blocs
– taux d ’occupation minimum de 50%
11/04/23 © Robert Godin. Tous droits réservés. 6
8.1.2 Arbre-B+
Hypothèse initiale : clé simple et unique
Nœud = bloc
10
Bloc 0
20
25 40 45
Bloc 2
25
Bloc 3
30 40
Bloc 1
43 44 60
Bloc 4
7050
Bloc 5
53
60
Bloc 6
50
Bloc 7
45 48
Bloc 8
11/04/23 © Robert Godin. Tous droits réservés. 7
Structure d ’une feuille
1. Remplie à moitié au minimum FBMf/2 ≤ n = nombre de clés ≤ FBMf
2. Clés triées : i < j Ci < Cj
3. Clés d'une feuille < clés de la suivante
4. Au même niveau (équilibré)
Ci : Clé
Ri : reste de l'enregistrement ou référence
S : Pointeur sur le bloc suivant dans la liste des feuilles
C 1 R 1 ... C n R n SEspace
libre
11/04/23 © Robert Godin. Tous droits réservés. 8
Structure d’un bloc interne
1. Remplie à moitié au minimum:
– OrdreI /2 ≤ n = nombre de pointeurs ≤ OrdreI
2. Clés triées : i < j Ci < Cj
3. Ci-1 <= Clés sous Pi-1 < Ci
P 1 C 1 ... P n-1 C n-1 P nP 2 ... C i-1 P i-1 C i
C i-1 <= C < C i
Espacelibre
C < C 1 C n-1 <= C
11/04/23 © Robert Godin. Tous droits réservés. 9
8.1.2.1 Recherche dans un arbre-B+
RechercherClé (noBloc, clé, indice)
EntréenoBloc : typeNuméroBloc {numéro du bloc à chercher; racine au premier appel}clé : typeClé {la clé à chercher}
SortienoBloc : typeNuméroBloc {numéro du bloc où est la clé }indice : 1..FBMf { si clé trouvée, indice de la clé dans le tableauClés du bloc}valeur de retour : BOOLÉEN;{vrai si clé a été trouvée}
Pré-condition : arbre n'est pas vide
DÉBUTlireBloc(fichierArbre-BPlus, noBloc, bloc);TANT QUE bloc n'est pas une feuille
indice := l'indice de la plus petite clé de tableauClés plus grande que clé (ou n);noBloc:= tableauEnfants[indice];lireBloc(fichierArbre-BPlus, noBloc, bloc);
FIN TANT QUE;SI la clé est présente dans tableauClés
indice := l'indice de la clé dans le tableauClés;retourner VRAI;
SINONretourner FAUX
FIN SIFIN
11/04/23 © Robert Godin. Tous droits réservés. 10
Rechercher 43
10
Bloc 0
20
25 40 45
Bloc 2
25
Bloc 3
30 40
Bloc 1
43 44 60
Bloc 4
7050
Bloc 5
53
60
Bloc 6
50
Bloc 7
45 48
Bloc 8
11/04/23 © Robert Godin. Tous droits réservés. 11
8.1.2.2 Complexité de la recherche et hauteur de l'arbre
FBMf = 20 et OrdreI = 200 Hauteur = nombre de niveaux Hauteur 2 N 2 * 10 = 20 clés (pire cas) Hauteur 3 N 2 * 100 * 10 = 2 000 clés Hauteur 4 N 2 * 100 * 100 * 10 = 200 000 clés Hauteur 5 N 2 * 100 * 100 * 100 * 10 = 20 000 000
clés
Hauteur H N 2*OrdreI /2H-2 * FBMf/2 pour H 2
H 2 + log OrdreI /2 (N /(2*FBMf/2))– O(log N)
11/04/23 © Robert Godin. Tous droits réservés. 12
Hauteur moyenne
H ~ 1 + log OrdreMoyenI (N / FBf)
– OrdreMoyenI = 2/3 OrdreI
– FBf = 2/3 FBMf
Index secondaire
– FBf ~ OrdreMoyenI
– H = log OrdreMoyenI (N)
11/04/23 © Robert Godin. Tous droits réservés. 13
8.1.2.3 Insertion dans un arbre-B+
FBM = 3, OrdreI = 4
40 ...
B loc 0
20 ... 40 ...
B loc 0
20 ... 40 ... 60 ...
B loc 0
11/04/23 © Robert Godin. Tous droits réservés. 14
Débordement et division
Insertion de 30 Débordement et la division du bloc 0 40 est promue Nouvelle racine
20 ... 40 ... 60 ...
B loc 0
20 ... 30 ...
B loc 0
40 ... 60 ...
B loc 1
40
Bloc 2
11/04/23 © Robert Godin. Tous droits réservés. 15
Insertion de 25
20 ... 30 ...
B loc 0
40 ... 60 ...
B loc 1
40
Bloc 2
40
Bloc 2
20
Bloc 0
25 30 40
Bloc 1
60
11/04/23 © Robert Godin. Tous droits réservés. 16
Insertion de 10
40
Bloc 2
20
Bloc 0
25 30 40
Bloc 1
60
10
Bloc 0
20
25 40
Bloc 2
25
Bloc 3
30 40
Bloc 1
60
Débordement et la division du bloc 0 25 est promue
11/04/23 © Robert Godin. Tous droits réservés. 17
Insertion de 70
10
Bloc 0
20
25 40
Bloc 2
25
Bloc 3
30 40
Bloc 1
60
10
Bloc 0
20
25 40
Bloc 2
25
Bloc 3
30 40
Bloc 1
60 70
11/04/23 © Robert Godin. Tous droits réservés. 18
Insertion de 50
10
Bloc 0
20
25 40
Bloc 2
25
Bloc 3
30 40
Bloc 1
60 70
10
Bloc 0
20
25 40 60
Bloc 2
25
Bloc 3
30 40
Bloc 1
50 60
Bloc 4
70
Débordement et la division du bloc 1 60 est promue
11/04/23 © Robert Godin. Tous droits réservés. 19
Insertion de 53
10
Bloc 0
20
25 40 60
Bloc 2
25
Bloc 3
30 40
Bloc 1
50 60
Bloc 4
70
10
Bloc 0
20
25 40 60
Bloc 2
25
Bloc 3
30 40
Bloc 1
50 53 60
Bloc 4
70
11/04/23 © Robert Godin. Tous droits réservés. 20
Insertion de 45
10
Bloc 0
20
25 40 60
Bloc 2
25
Bloc 3
30 40
Bloc 1
50 53 60
Bloc 4
70
10
Bloc 0
20
25 40
Bloc 2
25
Bloc 3
30 40
Bloc 1
45 60
Bloc 4
7050
Bloc 5
53
60
Bloc 6
50
Bloc 7
Division du bloc 1 50 est promue Division de la racine
11/04/23 © Robert Godin. Tous droits réservés. 21
8.1.2.4Suppression dans un arbre-B+ Cas simple
– minimum préservé– pas la première
10
Bloc 0
20
25 40
Bloc 2
25
Bloc 3
30 40
Bloc 1
60 70
10
Bloc 0
20
25 40
Bloc 2
25
Bloc 3
30 40
Bloc 1
60
11/04/23 © Robert Godin. Tous droits réservés. 22
Première clé du bloc et pas la première feuille Remplacer dans le parent (si pas «
aîné »)
10
Bloc 0
20
25 40
Bloc 2
25
Bloc 3
30 40
Bloc 1
60 70
10
Bloc 0
20
25 60
Bloc 2
25
Bloc 3
30 60
Bloc 1
70
11/04/23 © Robert Godin. Tous droits réservés. 23
Première clé du bloc et pas la première feuille Remonter tant que l'enfant est l ’«
aîné »
10
Bloc 0
20
25 40 45
Bloc 2
25
Bloc 3
30 40
Bloc 1
43 44 60
Bloc 4
7050
Bloc 5
53 55
60
Bloc 6
50
Bloc 7
45 48
Bloc 8
10
Bloc 0
20
25 40 45
Bloc 2
25
Bloc 3
30 40
Bloc 1
43 44 60
Bloc 4
7053
Bloc 5
55
60
Bloc 6
53
Bloc 7
45 48
Bloc 8
11/04/23 © Robert Godin. Tous droits réservés. 24
Violation du minimum : redistribution si possible Ajuster séparateur40
Bloc 2
20
Bloc 0
25 30 40
Bloc 1
60
30
Bloc 2
20
Bloc 0
25 30
Bloc 1
60
11/04/23 © Robert Godin. Tous droits réservés. 25
Violation du minimum : fusion
Fusion des deux frères
10
Bloc 0
20
25 60
Bloc 2
25
Bloc 3
30 60
Bloc 1
70
10
Bloc 0
25 30
60
Bloc 2
60
Bloc 1
70
Violation de larègle du minimum
11/04/23 © Robert Godin. Tous droits réservés. 26
Cas de fusion de feuilles et de redistribution au niveau du parent
10
Bloc 0
20
25 40
Bloc 2
25
Bloc 3
30 40
Bloc 1
45 60
Bloc 4
7050
Bloc 5
53
60
Bloc 6
50
Bloc 7
Violation de larègle du minimum
10
Bloc 0
20
25 40
Bloc 2
25
Bloc 3
30 40
Bloc 1
45 50
Bloc 5
60 70
60
Bloc 6
50
Bloc 7
Violation de larègle du minimum
Redistribution
Fusion des deux frères
11/04/23 © Robert Godin. Tous droits réservés. 27
Cas de fusion de feuilles et de redistribution au niveau du parent (suite)
10
Bloc 0
20
25 40
Bloc 2
25
Bloc 3
30 40
Bloc 1
45 50
Bloc 5
60 70
60
Bloc 6
50
Bloc 7
Violation de larègle du minimum
Redistribution
10
Bloc 0
20
25
Bloc 2
25
Bloc 3
30 40
Bloc 1
45 50
Bloc 5
60 70
50
Bloc 6
40
Bloc 7
11/04/23 © Robert Godin. Tous droits réservés. 28
Cas de fusion en cascade
Fusion des deux frères
10
Bloc 0
20
25
Bloc 2
25
Bloc 3
30 40
Bloc 1
45 50
Bloc 5
60 70
50
Bloc 6
40
Bloc 7
Violation de larègle du minimum
Fusion des deux frères
10
Bloc 0
25 30
25
Bloc 2
40
Bloc 1
45 50
Bloc 5
60 70
50
Bloc 6
40
Bloc 7Violation de la
règle du minimum
11/04/23 © Robert Godin. Tous droits réservés. 29
Cas de fusion en cascade (suite) : réduction de la hauteur
Fusion des deux frères
10
Bloc 0
25 30
25
Bloc 2
40
Bloc 1
45 50
Bloc 5
60 70
50
Bloc 6
40
Bloc 7Violation de la
règle du minimum
10
Bloc 0
25 30
40 50
Bloc 2
40
Bloc 1
45 50
Bloc 5
60 70
11/04/23 © Robert Godin. Tous droits réservés. 30
8.1.3 Arbre-B
40
25 60
30 50 53 7010 20
Bloc 0 Bloc 3 Bloc 1 Bloc 4
Bloc 2 Bloc 5
Bloc 6
10
Bloc 0
20
25 40 60
Bloc 2
25
Bloc 3
30 40
Bloc 1
50 53 60
Bloc 4
70
Arbre-B
Arbre-B+
Clés non dupliquées Ordre < Hauteur >
11/04/23 © Robert Godin. Tous droits réservés. 31
8.1.4 Autres variantes du concept d'arbre-B Redistribuer plutôt que diviser
– occupation moyenne 67% => 86% Diviser deux en trois
– Arbre-B* Ordre variable
– clés de taille variable Arbre B préfixe
– comprimer les clés diminue la hauteur Algorithme de chargement en lot
– feuilles consécutives– taux de remplissage prédéterminé
11/04/23 © Robert Godin. Tous droits réservés. 32
Cas d'une clé non unique
Arbre-B+ primaire sur une clé non unique– IDE difficile
Arbre B+ secondaire avec clés répétées– clé d ’accès + pointeur (unique)
Arbre B+ secondaire avec collection de références– listes inversées dans les feuilles
Arbre B+ secondaire avec référence à une collection d'enregistrements– Index groupant (“ clustering index ”)
organisation primaire par grappe et index secondaire sur même clé
Arbre B+ secondaire avec référence à collection de références– listes inversées à part
Arbre B+ avec vecteurs booléens– index « bitmap »
11/04/23 © Robert Godin. Tous droits réservés. 33
8.1.5 Réalisation de l'accès par IDE à l'aide d'une organisation par index
Index primaire– IDE = id_fichier, valeur de la clé
unique– nécessite le passage par l ’index
IDE logique– index secondaire– clé d ’index = IDE
11/04/23 © Robert Godin. Tous droits réservés. 34
8.1.6 Sélection par intervalle ou préfixe Arbre B+
– recherche de la valeur minimale– parcours des feuilles jusqu ’à la valeur maximale
...
...
...
...
.........
Feuilles à transférer
11/04/23 © Robert Godin. Tous droits réservés. 35
8.1.7 Index sur une clé composée Clé composée ~ clé simple formée
de la concaténation des champs Sélection par préfixe de la clé
composée
11/04/23 © Robert Godin. Tous droits réservés. 36
indice noPermis sexe couleurYeux bitmapsexe = M
bitmapsexe = F
bitmapcouleurYeux= bleu
bitmapcouleurYeux= brun
bitmapcouleurYeux= rouge
1 G111 M brun 1 0 0 1 02 G555 M bleu 1 0 1 0 03 G222 F brun 0 1 0 1 04 G888 M brun 1 0 0 1 05 G777 F brun 0 1 0 1 06 G666 M rouge 1 0 0 0 17 G333 F bleu 0 1 1 0 08 G444 F brun 0 1 0 1 0
8.1.8 Index bitmap
couleurYeux = brun et sexe = M– 10111001 ET 11010100 = 10010000
11/04/23 © Robert Godin. Tous droits réservés. 37
8.2Arbre digital (trie)
Chaque niveau : position d'un symbole de la clé vue comme une séquence de symboles s1s2…sn
«ACB»
A B C
«A»
A C
«AA»
A B
«ACA»
«BA»
A
«C»
B
«BB»
11/04/23 © Robert Godin. Tous droits réservés. 38
8.3 Hachage Hachage ou adressage dispersé (hashing)
Fonction h(clé de hachage) => l'adresse d'un paquet
Fichier = tableau de paquets (bucket)
– ~ARRAY paquet [0..TH-1]
– TH : taille de l'espace d'adressage primaire
Habituellement paquet = bloc
Pas d ’index à traverser : O(1) en meilleur cas
Sélection par égalité (pas intervalle)
11/04/23 © Robert Godin. Tous droits réservés. 39
8.3.1 Hachage statique
60 Erable argenté 15.99
90 Pom m ier 25.99
81 Catalpa 25.99
70 Herbe à puce 10.99
40 Epinette bleue 25.99
10 Cèdre en boule 10.99
20 Sapin 12.99
50 Chêne 22.99
95 Génév rier 15.99
80 Poirier 26.99
0
1
2
clé = 10
h (10) = 10 M O D 3 = 1
11/04/23 © Robert Godin. Tous droits réservés. 40
8.3.1.1 Problème de débordement dû aux collisions
Méthode de résolution des collisions– Adressage ouvert
AC+1, AC+2,....., n-1, 0, 1, ....AC-1– Chaînage
60 Erable argenté 15.99
90 Pom m ier 25.99
81 Catalpa 25.99
70 Herbe à puce 10.99
40 Epinette bleue 25.99
10 Cèdre en boule 10.99
43 Magnolia 28.99
20 Sapin 12.99
50 Chêne 22.99
95 Génév rier 15.99
80 Poirier 26.99
0
1
2
52 Pin 18.99
Hachage Cuckoo
Combiner 2 organisations par hachage– - 2 fonctions différentes
Si collision– Prendre la place– Pousser la clé déjà présente dans l’autre organisation
Répéter au besoin Si plus de place
– Réorganiser … Garantie de 2 accès
– Occupation sous 50%
11/04/23 © Robert Godin. Tous droits réservés. 41
11/04/23 © Robert Godin. Tous droits réservés. 42
Fonction de hachage
Répartition uniforme des clés dans [0..TH-1] – h(clé) = clé MOD TH
TH est premier
– h(clé) = clé p MOD TH TH et p sont relativement premiers
– h(clé) = (∑ si) MOD TH si est une sous-séquence des bits de la clé
Clé non numérique– représentation binaire vue comme un entier
11/04/23 © Robert Godin. Tous droits réservés. 43
Hachage vs indexage
O(1) en meilleur cas vs O(log(N)) Pas d ’espace supplémentaire d ’index Gaspillage d ’espace si TH trop > Performance dégradée si TH trop < Gestion plus délicate
– déterminer h et TH– maintenance : réorganisations
Clé non numérique ?– représentation binaire vue comme un entier
Connaissances à priori sur les clés Calculer une fonction de hachage
adaptée Hachage parfait Hachage minimal parfait Hachage qui préserve l’ordre
11/04/23 © Robert Godin. Tous droits réservés. 44
11/04/23 © Robert Godin. Tous droits réservés. 45
Calcul d ’espace
Heuristique : Taux d ’occupation moyen ~ 80%– TauxOccupation = N/(TH FB) 0.8
Taux de débordement moyen sous distribution uniforme [Merrett, 1984 #217] :– FB = 1 ~ 30%– FB = 10 ~ 5%– FB = 100 ~1%
11/04/23 © Robert Godin. Tous droits réservés. 46
8.3.2 Hachage dynamique
Adaptation de TH et h aux variations du volume des données
~ arbre-B– division et fusion de paquets (blocs)
Deux variantes de base – linéaire– extensible
11/04/23 © Robert Godin. Tous droits réservés. 47
8.3.2.1Hachage linéaire
Adaptation de TH– suite d ’expansions
Début de dième expansion, d {0, 1, …}– TH passera de 2d à 2d+1
– adresse du paquet : hd(clé) = bd-1, bd-2,…, b1, b0
101002 11101 2
00001 2
110102 011112
110112
002 012 102 112
p
d = 2
11/04/23 © Robert Godin. Tous droits réservés. 48
Insertion de h(clé) = 101012
10100 2 11101 2
00001 2
11010 2 01111 2
11011 2
002 012 102 112
p
11101 2
00001 2
11010 2 01111 2
11011 2
0002 012 102 112
p
10101 2
10100 2
Zône primaire Zône d'expansion
1002
Division du b loc 00 2
Bloc #012 déborde
Division du bloc p = #002 (pas #012)
p := p+1
FONCTION AdresseLinéaire (clé)DÉBUT
SI hd(clé) >= p Retourner hd(clé)SINON Retourner hd+1(clé) FINSI
FIN
11/04/23 © Robert Godin. Tous droits réservés. 49
Insertion de h(clé) = 101112
111012
000012
110102 011112
110112
0002 012 102 112
p
101012
10100 2
1002
Bloc #112 déborde
00001 2 11010 2 01111 2
11011 2
000 2 001 2 10 2 11 2
p
10111 2
10100 2
Zône primaire Zône d'expansion
100 2
Division du bloc 01 2 (p = 01 2)
10101 2
11101 2
101 2
11/04/23 © Robert Godin. Tous droits réservés. 50
Insertion de 110002, 110012 et 101102
00001 2 11010 2 01111 2
11011 2
000 2 0012 102 112
p
10111 2
10100 2
100 2
10101 2
11101 2
101 2
11000 2 00001 2
11001 2
11010 2
10110 2
01111 2
11011 2
000 2 0012 102 112
p
10111 2
10100 2
Zône primaire Zône d'expansion
100 2
10101 2
11101 2
101 2
11/04/23 © Robert Godin. Tous droits réservés. 51
Insertion de 100102
11000 2 00001 2
11001 2
11010 2
10010 2
01111 2
11011 2
0002 0012 0102 112
p
10111 2
10100 2
Zône primaire Zône d'expansion
1002
Division du b loc 10 2 (p = 10 2)
10101 2
11101 2
1012
10110 2
1102
11000 2 00001 2
11001 2
11010 2
10110 2
01111 2
11011 2
000 2 0012 102 112
p
10111 2
10100 2
100 2
10101 2
11101 2
101 2
Bloc #102 déborde et est divisé
11/04/23 © Robert Godin. Tous droits réservés. 52
Insertion de 011012
110002 000012
110012
110102
100102
011112
110112
0002 0012 0102 112
p
101112
10100 2
1002
101012
111012
1012
101102
1102
Bloc #1012 déborde– zone d ’expansion !
Fin de l ’expansion p := 0 d := d+1 = 3
11000 2 00001 2
11001 2
11010 2
10010 2
11011 2
000 2 0012 010 2 0112
p
10100 2
Zone primaire
100 2
Division du b loc 11 2
10101 2
11101 2
101 2
10110 2
1102
01101 2
01111 2
10111 2
1112
d = 3
11/04/23 © Robert Godin. Tous droits réservés. 53
8.3.2.1.1 Variantes du hachage linéaire Variante du contrôle de la division
– algorithme de base débordement => division : taux d ’occupation ~ 60%
– division/fusion contrôlée par taux d ’occupation Variante de gestion des débordements
– hachage linéaire au niveau suivant Variante de division
– biais dans les chaînages (à droite de p)– expansions partielles
diviser n blocs en n+1– fonction de hachage exponentielle
Gestion de l ’espace d ’adressage primaire– préserver la contiguïté de l ’espace malgré expansions ?
11/04/23 © Robert Godin. Tous droits réservés. 54
8.3.2.2 Hachage extensible
Ajoute un niveau d ’indirection Répertoire d'adresses de paquets
– espace supplémentaire– accès disque supplémentaire pour
répertoire antémémoire
Bloc qui déborde est divisé– pas de dégradation due au chaînage– pire cas : 2 transferts
11/04/23 © Robert Godin. Tous droits réservés. 55
Analogie avec arbre digital
Répertoire vu comme arbre digital Chemin = suffixe
Pas de lien direct entre suffixe et #bloc
101002
110002
0 1
010102
011102
0 110001 2
11101 2
Bloc 0
B loc 1
B loc 2
11/04/23 © Robert Godin. Tous droits réservés. 56
Insertion de h(clé) = 100112
Débordement et division du bloc #1 Utilisation d ’un bit de plus
101002
110002
0 1
010102
011102
0 110001 2
11101 2
Bloc 0
B loc 1
B loc 2
101002
110002
0 1
010102
011102
0 1
100012
111012
Bloc 0 B loc 1B loc 2
0 1
100112
Bloc 3
11/04/23 © Robert Godin. Tous droits réservés. 57
«Remplacer» l'arbre digital par un répertoire
101002
110002
0 1
010102
011102
0 110001 2
11101 2
Bloc 0
B loc 1
B loc 2
101002
110002
0 1
010102
011102
0 1
100012
111012
Bloc 0 B loc 1B loc 2
0 1
« Compléter » l ’arbre
11/04/23 © Robert Godin. Tous droits réservés. 58
Arbre digital => un répertoire
101002
110002
0 1
010102
011102
0 1
100012
111012
Bloc 0 B loc 1B loc 2
0 1
Bijection chemin <-> indice
101002
110002
Bloc 0
2100012
111012
Bloc 1
1010102
011102
Bloc 2
2
2
002 012 102 112
Profondeurglobale du
répertoire (d)
Profondeurlocale du
bloc
Sens de lecture des indices
11/04/23 © Robert Godin. Tous droits réservés. 59
Insertion de h(clé) = 100112
avec répertoire
10100 2
11000 2
Bloc 0
210001 2
11101 2
Bloc 1
101010 2
01110 2
Bloc 2
2
2
002 012 102 112
Profondeurglobale du
répertoire (d)
Profondeurlocale du
bloc
101002
110002
Bloc 0
2100012
111012
Bloc 1
2010102
011102
Bloc 2
2
2
002 012 102 112
Profondeurglobale du
répertoire (d)
Profondeurlocale du
bloc100112
Bloc 3
2
11/04/23 © Robert Godin. Tous droits réservés. 60
Cas de dédoublement de répertoire : insertion de h(clé) = 101102
10100 2
11000 2
Bloc 0
210001 2
11101 2
Bloc 1
101010 2
01110 2
Bloc 2
2
2
002 012 102 112
Profondeurglobale du
répertoire (d)
Profondeurlocale du
bloc101002
110002
0 1
010102
011102
0 110001 2
11101 2
Bloc 0
B loc 1
B loc 2
101002
110002
0 1
0 1100012
111012
Bloc 0
Bloc 1
010102 011102
101102
0 1
Bloc 2 Bloc 3
10100 2
11000 2
0 1
0 1
10001 2
11101 2
Bloc 0 B loc 1
01010 2 01110 2
10110 2
0 1
Bloc 2 B loc 3
0 10 1
0 1
0 1101002
110002
Bloc 0
2100012
111012
Bloc 1
1010102
Bloc 2
3
3
0002 0012 0102 0112 1002 1012 1102 1112
011102
101102
Bloc 3
3
Profondeur locale dépasse profondeur globale
11/04/23 © Robert Godin. Tous droits réservés. 61
Hachage extensible (suite)
Occupation d ’espace– comportement oscillatoire assez
prononcé entre .53 et .94 moyenne : ln 2 = .69
Variation– contrôle de la division par taux
d ’occupation– gestion des débordements
11/04/23 © Robert Godin. Tous droits réservés. 62
8.3.3 Réalisation de l'accès par IDE avec le hachage
Hachage statique– bloc d ’ancrage fixe– IDE = idFichier, #blocAncrage,
#séquence HASH CLUSTER d ’Oracle
– applicable dans le cas non unique Cas d ’une clé de hachage unique
– IDE = id_fichier, valeur de la clé unique– nécessaire avec hachage dynamique
11/04/23 © Robert Godin. Tous droits réservés. 63
8.3.4 Hachage sur une clé non unique et effet de grappe
Regroupement des mêmes valeurs de clé– v1 = v2 h(v1) = h(v2)
60 Erable argenté 15.99
90 Pom m ier 25.99
81 Catalpa 25.99
70 Herbe à puce 10.99
40 Epinette bleue 25.99
10 Cèdre en boule 10.99
43 Magnolia 28.99
20 Sapin 12.99
50 Chêne 22.99
95 Génév rier 15.99
80 Poirier 26.990
1
2
15
20
1
6
20
6
15
1
15
1
5
52 Pin 18.99 15
h (ta ille ) = ta ille M O D 3
ta ille
11/04/23 © Robert Godin. Tous droits réservés. 64
8.3.5 Hachage secondaire
Hachage sur– (clé de hachage, IDE)
11/04/23 © Robert Godin. Tous droits réservés. 65
8.4 Tableau comparatif des organisations
Critère Sériel Arbre-B+ primaire
Arbre-B+ secondaire
Hachage statique
Hachage dynamique
Sélection par égalité sur clé unique
O(N/ FB) Cas moyen : O(N/ FB/ 2)
O(log (N)) O(log (N)) Meilleur cas :O(1) Pire cas : O(N/ FB)
Meilleur cas :O(1) Pire cas : O(N/ FB)
Sélection par égalité sur clé non unique
O(N/ FB) O(log (Card(clé))+ Sel/ FB)
Approche par duplication O(log (N)+ Sel)
Meilleur cas : O(Sel/ FB) Pire cas : O(N/ FB)
Meilleur cas : O(Sel/ FB) Pire cas : O(N/ FB)
Sélection par intervalle O(N/ FB) O(log (Card(clé))+ Sel/ FB)
O(log (N)+ Sel)
O(N/ FB) O(N/ FB)
Itération sérielle O(N/ FB) O(N/ FB) O(N/ FB) O(N/ FB) Itération séquentielle O(tri) O(N/ FB) O(N) O(tri) O(tri) Insertion/ suppression O(1) O(log N) O(log N) Meilleur cas
:O(1) Pire cas : O(N/ FB)
Meilleur cas :O(1) Pire cas : O(N/ FB)
Taux d'occupation mémoire secondaire
Maximal approche 100%
En moyennne : 66% (2/ 3)
Ajouter à l'organisation primaire
~80% À ajuster Pire cas non borné
~69% (ln 2) Peut augmenter au prix d'une diminution de performance.
Autres considérations Support difficile de l'accès par IDE et donc des organisations secondaires
Peut y avoir plusieurs index secondaires sur la même table
Distribution des clés par fonction de hachage ? Problème avec tables volatiles Stress du DBA
Disponibilité restreinte
Recommended