1 Organisations unidimentionnelles : indexage et hachage Sélection basée sur une clé d'accès recherche associative Ex: Chercher le plant dont le

1

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)

2

Indexage

Index et clé d'index (index key) valeur de la clé =>adresse de(s) l'enregistrement

Num é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

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


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

4

Index séquentiel hiérarchique

Ex: ISAM de IBM Zone de débordement

Réorganisations chroniques


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

5

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%

6

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

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

8

Structure d’un bloc interne

1. Rempli à 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

9

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

10

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,000clé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

Hauteur moyenne

H ~ 1 + log OrdreMoyenI (N / FBf) OrdreMoyenI = 2/3 OrdreI

FBf = 2/3 FBMf

Index secondaire FBf ~ OrdreMoyenI

H = logOrdreMoyenI (N)

12

Insertion dans un arbre-B+

FBM = 3, OrdreI = 4

40 ...

B loc 0

20 ... 40 ...

B loc 0

20 ... 40 ... 60 ...

B loc 0

13

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

14

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

15

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

16

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

17

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

18

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

19

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

20

Suppression 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

21

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

22

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

23

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

24

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

25

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


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


Redistribution


26

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


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

27

Cas de fusion en cascade


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



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

28

Cas de fusion en cascade (suite) : réduction de la hauteur


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

29

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 >

30

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é

31

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 »

32

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

33

Sélection par intervalle ou préfixe

Arbre B+

recherche de la valeur minimale parcours des feuilles jusqu ’à la valeur maximale

...

...

...

...

.........

Feuilles à transférer

34

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

35

Arbre 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»

36

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)

37

Hachage statique


90 Pom m ier 25.99

81 Catalpa 25.99

70 Herbe à puce 10.99

40 Epinette bleue 25.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

38

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


90 Pom m ier 25.99

81 Catalpa 25.99




43 Magnolia 28.99

20 Sapin 12.99

50 Chêne 22.99


80 Poirier 26.99

0

1

2

52 Pin 18.99

39

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 relativements 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

40

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

41

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%

42

Fonction de hachage préservant la relation d'ordre

(tidy functions)

clé1 < clé2 h(clé1) < h(clé2)

Connaissances préalables au sujet de la distribution des clés

43

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

44

Hachage 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

45

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

46


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


100 2

Division du bloc 01 2 (p = 01 2)

10101 2

11101 2

101 2

47

Insertion de 110002, 110012 et 101102

000012 110102 011112

110112

0002 0012 102 112

p

101112

10100 2

1002

101012

111012

1012

11000 2 00001 2

11001 2

11010 2

10110 2

01111 2

11011 2

0002 0012 102 112

p

10111 2

10100 2


1002

10101 2

11101 2

1012

48

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


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é

49

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

50

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 contiguité de l ’espace malgré expansions ?

51

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

52

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

53


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

54

«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


0 1

« Compléter » l ’arbre

55

Arbre digital => un répertoire

101002

110002

0 1

010102

011102

0 1

100012

111012


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

56

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


répertoire (d)

Profondeurlocale du

bloc

101002

110002

Bloc 0

2100012

111012

Bloc 1

2010102

011102

Bloc 2

2

2

002 012 102 112


répertoire (d)

Profondeurlocale du

bloc100112

Bloc 3

2

57

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


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

58

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

59

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

60

Hachage sur une clé non unique et effet de grappe

Regroupement des mêmes valeurs de clé v1 = v2 h(v1) = h(v2)


90 Pom m ier 25.99

81 Catalpa 25.99




43 Magnolia 28.99

20 Sapin 12.99

50 Chêne 22.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

61

Hachage secondaire

Hachage sur (clé de hachage, IDE)

62

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) 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

Documents

1 Organisations unidimentionnelles : indexage et hachage Sélection basée sur une clé d'accès recherche associative Ex: Chercher le plant dont le