28
base Management Systems 3ed, R. Ramakrishnan and J. Gehrke Indexes à Arbres et Indexes à Hachage Sections sélectionnées des Chapitres 10 & 11

Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke1 Indexes à Arbres et Indexes à Hachage Sections sélectionnées des Chapitres 10 & 11

Embed Size (px)

Citation preview

Page 1: Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke1 Indexes à Arbres et Indexes à Hachage Sections sélectionnées des Chapitres 10 & 11

Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke 1

Indexes à Arbres et Indexes à Hachage

Sections sélectionnées des Chapitres 10 & 11

Page 2: Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke1 Indexes à Arbres et Indexes à Hachage Sections sélectionnées des Chapitres 10 & 11

Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke 2

Introduction Rappel des 3 alternatives d’entrées des données

k*: un enregistrement de données avec une valeur de clé k une paire <k, rid> une paire <k, liste de rids>

Le choix dépend de la technique d’index utilisée pour localiser les entres des données k*.

Les indexes à arbres supportent à la fois la recherche des plages de valeurs (‘’range search’’) ainsi que les recherches d’egalités (‘’equality search’’).

ISAM: structure statique; B+ tree: dynamique, s’ajuste gracieusement aux insertions et effacements.

Indexes à Hachage : meilleurs pour les recherches d’égalité; ne peuvent supporter les recherches des valeurs des plages.

Page 3: Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke1 Indexes à Arbres et Indexes à Hachage Sections sélectionnées des Chapitres 10 & 11

Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke 3

Intuition Derrière les Indexes à Arbres

``Trouvez tous les étudiants avec un gpa > 3.0’’ Si les données sont stockées dans un fichier trié,

faire la recherche binaire pour trouver le premier de ces étudiants, et de là faire un scannage pour trouver les autres.

Le coût de la recherche binaire peut être prohibitif ! Il est en effet proportionnel au # de pages puisées.

Solution: Créer un fichier d’indexes

Une recherche binaire est faisable sur de petits fichiers d’indexes!

Page 1 Page 2 Page NPage 3 Fichier de données

k2 kNk1Fichier d’indexes

Page 4: Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke1 Indexes à Arbres et Indexes à Hachage Sections sélectionnées des Chapitres 10 & 11

Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke 4

ISAM

Le fichier d’indexes peut être très large. On peut cependant appliquer l’idée de fichier d’indexes de manière répétée!

Les pages feuilles contiennent les entrées des données.

P0

K1 P

1K 2 P

2K m

P m

Entrée d’index

Pages

internes

feuilles

Page de débordement

Pages primaires

Pages

Page 5: Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke1 Indexes à Arbres et Indexes à Hachage Sections sélectionnées des Chapitres 10 & 11

Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke 5

ISAM (Suite) Création du fichier: les feuilles (pages de

données) sont allouées séquentiellement et triées selon la clé de recherche; ensuite les pages de débordement sont crées.

Entrées d’indexes: <valeur de la clé, page id>; orientent la recherche vers les entrées de données se trouvant dans les pages feuilles.

Recherche: Commence à la racine; compare des clés pour aller vers la feuille appropriée. Coût log F N ; F = # entrées/pg index, N = # feuilles

Insertion: Trouver la feuille à la quelle appartient l’entrée de donnée et l’y mettre.

Effacement: Trouver et enlever l’entrée de la feuille; désaffecter une page de débordement vide. Structure statique: les changements n’affectent que les feuilles.

Pages de données

Pages des indexes

Pages de débordement

Page 6: Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke1 Indexes à Arbres et Indexes à Hachage Sections sélectionnées des Chapitres 10 & 11

Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke 6

Exemple d’un Arbre ISAM Chaque nœud peut contenir 2 entrées; il

n’y a pas besoin de pointeurs liant les pages entre elles (Pourquoi ???)

10* 15* 20* 27* 33* 37* 40* 46* 51* 55* 63* 97*

20 33 51 63

40

Racine

Page 7: Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke1 Indexes à Arbres et Indexes à Hachage Sections sélectionnées des Chapitres 10 & 11

Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke 7

Après l’Insertion de 23*, 48*, 41*, 42* ...

10* 15* 20* 27* 33* 37* 40* 46* 51* 55* 63* 97*

20 33 51 63

40

Racine

23* 48* 41*

42*

Pages de

débordement

primaires

Pages de l’index

Feuilles

Page 8: Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke1 Indexes à Arbres et Indexes à Hachage Sections sélectionnées des Chapitres 10 & 11

Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke 8

... Ensuite Effacement de 42*, 51*, 97*

Notez que 51* apparaît au niveau de la page de l’index, mais pas dans la feuille!

10* 15* 20* 27* 33* 37* 40* 46* 55* 63*

20 33 51 63

40

Racine

23* 48* 41*

Page 9: Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke1 Indexes à Arbres et Indexes à Hachage Sections sélectionnées des Chapitres 10 & 11

Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke 9

Arbre B+: L’Index le plus Usuel Insertion/effacement avec coût log F N; Garde la

hauteur balancée. (F = ‘’fanout’’, N = # feuilles) Taux d’occupation minimum de 50%(sauf pour la

racine). Chaque nœud contient d <= m <= 2d entrées. Le paramètre d est appelé l’ordre de l’arbre.

Supporte efficacement les recherches des plages de valeurs et les recherches d’égalités.

Entrées de l’index

Entrées de données("Sequence set")

(orientent la recherche)

Page 10: Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke1 Indexes à Arbres et Indexes à Hachage Sections sélectionnées des Chapitres 10 & 11

Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke 10

Exemple d’Arbre B+ La recherche commence à la racine et les

comparaisons des clés l’orientent vers une page (similaire à la méthode ISAM).

Recherchez 5*, 15*, …, toutes entrées de données >= 24* ...

Racine

17 24 30

2* 3* 5* 7* 14* 16* 19* 20* 22* 24* 27* 29* 33* 34* 38* 39*

13

Page 11: Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke1 Indexes à Arbres et Indexes à Hachage Sections sélectionnées des Chapitres 10 & 11

Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke 11

Arbre B+ en Pratique Ordre typique: 100. Remplissage typique: 67%.

Sortance (‘’fanout’’) moyenne = 133 Capacités typiques:

Hauteur 4: 1334 = 312,900,700 enreg.’s Hauteur 3: 1333 = 2,352,637 enreg.’s

Les niveaux supérieurs de l’arbre peuvent souvent tenir en mémoire principale (‘’buffer pool’’): Niveau 1 = 1 page = 8 Kbytes Niveau 2 = 133 pages = 1 Mbyte Niveau 3 = 17,689 pages = 133 MBytes

Page 12: Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke1 Indexes à Arbres et Indexes à Hachage Sections sélectionnées des Chapitres 10 & 11

Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke 12

Insertion d’une Entrée de Données Trouver la feuille appropriée L. Mettre l’entrée de données dans L.

Si L a assez d’espace, fin! Sinon, on doit partager L (en L et un nouveau nœud L2)

• Redistribuer les entrées de manière égale, copier la clé du milieu vers le haut.

• Insérer l’entrée d’index pointant vers L2 dans le parent de L.

Ceci peut arriver de manière récursive Pour partager nœud d’index, redistribuer les entrées de

manière égale, mais pousser la clé du milieu vers le haut. (Contrastez ceci avec le partage des feuilles !!)

Les partages font croître l’arbre; le partage de la racine augmente sa hauteur. Croissance de l’arbre: devient plus large ou d’ un niveau

plus élevé à la racine.

Page 13: Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke1 Indexes à Arbres et Indexes à Hachage Sections sélectionnées des Chapitres 10 & 11

Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke 13

Insertion de 8* dans l’Exemple

Veuillez noter la différence entre copier vers le haut et pousser vers le haut. (Pourquoi fait-on cette différence????)

2* 3* 5* 7* 8*

5

Entrée à insérer dans le nœud parent.(Notez que 5 est copié vers le haut et

continue d’apparaître dans la feuille.)

n’apparaît qu’une fois dans l’index.

5 24 30

17

13

Entrée à insérer dans le nœud parent.(17 est poussé vers le haut et

Page 14: Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke1 Indexes à Arbres et Indexes à Hachage Sections sélectionnées des Chapitres 10 & 11

Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke 14

Exemple d’Arbre B+ Après l’Insertion de 8*

La racine a été partagée; d’où augmentation de la hauteur. En fait, nous pouvons redistribuer ici au lieu de partager; cependant cela n’est pas usuel dans la pratique.

2* 3*

Racine

17

24 30

14* 16* 19* 20* 22* 24* 27* 29* 33* 34* 38* 39*

135

7*5* 8*

Page 15: Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke1 Indexes à Arbres et Indexes à Hachage Sections sélectionnées des Chapitres 10 & 11

Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke 15

Effacement d’une Entrée de Donnée

Commencer à la racine, trouver la feuille L à laquelle l’entrée appartient.

Enlever l’entrée. Si L est au moins à moitié vide, fin! Sinon L a seulement d-1 entrées,

• Essayer de redistribuer, empruntant des cousins .• Sinon, fusionner L et un cousin.

Si une fusion a lieu, on doit effacer l’entrée (d’indexe) pointant (vers L ou le cousin) à partir du parent de L.

La fusion peut se répercuter jusqu’à la racine, décroissant ainsi la hauteur de l’arbre.

Page 16: Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke1 Indexes à Arbres et Indexes à Hachage Sections sélectionnées des Chapitres 10 & 11

Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke 16

Notre Arbre Après l’Insertion de 8*, Suivie de l’Effacement de 19* et 20* ...

Effacer 19* est facile. Effacer 20* est fait via une redistribution.

Noter comment la clé du milieu est copiée vers le haut après la redistribution.

2* 3*

Racine

17

30

14* 16* 33* 34* 38* 39*

135

7*5* 8* 22* 24*

27

27* 29*

Page 17: Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke1 Indexes à Arbres et Indexes à Hachage Sections sélectionnées des Chapitres 10 & 11

Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke 17

... Et Ensuite Après l’Effacement de 24*

On doit fusionner. A droite, on fait un

`échange’ d’entrée d’index.

Ci bas, on `tire une entrée vers le bas’.

30

22* 27* 29* 33* 34* 38* 39*

2* 3* 7* 14* 16* 22* 27* 29* 33* 34* 38* 39*5* 8*

Racine30135 17

Page 18: Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke1 Indexes à Arbres et Indexes à Hachage Sections sélectionnées des Chapitres 10 & 11

Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke 18

Exemple de Redistribution Interne

A l’opposé du cas précédant, ici on peut redistribuer une entrée de l’enfant gauche de la racine vers l’enfant droit.

Racine

135 17 20

22

30

14* 16* 17* 18* 20* 33* 34* 38* 39*22* 27* 29*21*7*5* 8*3*2*

Page 19: Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke1 Indexes à Arbres et Indexes à Hachage Sections sélectionnées des Chapitres 10 & 11

Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke 19

Après la Redistribution

Intuitivement, les entrées sont redistribuées en `poussant l’entrée partageante vers ’ le noeud parent.

Il suffit de redistribuer l’entrée d’index avec clé 20; on a aussi redistribué 17 pour illustration.

14* 16* 33* 34* 38* 39*22* 27* 29*17* 18* 20* 21*7*5* 8*2* 3*

Root

135

17

3020 22

Page 20: Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke1 Indexes à Arbres et Indexes à Hachage Sections sélectionnées des Chapitres 10 & 11

Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke 20

Chargement en Vrac d’un Arbre B+

Si l’on a une large collection d’enreg.’s et que l’on veut créer un indexe à arbre B+ avec une clé donnée, le faire enregistrement par enregistrement est très inefficace.

Solution: ‘’Bulk Loading’’ (chargement en vrac). Initialisation:

Trier toutes les entrées de données et les diviser en page;

créer une page racine vide; et insérer un pointeur de la racine vers la 1ère page des

données.

3* 4* 6* 9* 10* 11* 12* 13* 20* 22* 23* 31* 35* 36* 38* 41* 44*

Pages d’entrées de données triées; non encore mises dans l’arbre B+

Racine

Page 21: Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke1 Indexes à Arbres et Indexes à Hachage Sections sélectionnées des Chapitres 10 & 11

Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke 21

Chargement en Vrac (Suite) Les entrées d’index

pour les feuilles sont toujours créées dans la page d’index la plus à droite située juste au dessus du niveau des feuilles. Si cette dernière est pleine, elle est partagée. (Ce processus peut se répéter récursivement

3* 4* 6* 9* 10*11* 12*13* 20*22* 23* 31* 35*36* 38*41* 44*

Racine

Pages de données

à mettre sur l’arbre3523126

10 20

3* 4* 6* 9* 10* 11* 12*13* 20*22* 23* 31* 35*36* 38*41* 44*

6

Racine

10

12 23

20

35

38

Page 22: Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke1 Indexes à Arbres et Indexes à Hachage Sections sélectionnées des Chapitres 10 & 11

Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke 22

Hachage Statique Pages primaires en nombre fixe et

affectées séquentiellement; jamais désaffectées; pages de débordement si nécessaire.

h(k) mod M = bucket où mettre l’entrée des données dont la clé est k. (M = # de buckets)

h(key) mod N

hkey

Pages (bucket) primaires

Pages de débordement

20

N-1

Page 23: Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke1 Indexes à Arbres et Indexes à Hachage Sections sélectionnées des Chapitres 10 & 11

Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke 23

Hachage Statique (Suite) Les buckets contiennent les entrées des

données. La fonction de hachage utilise le champ de la

clé de recherche de l’enregistrement r. Les valeurs des clés doivent être distribuées sur une plage allant de 0 à M-1. Les fonctions de hachage ont été

abondamment étudiées. Défaut: possible développement de longues

chaînes de débordement qui peuvent entraver la performance. Hachage extensible et haching linéaire: Techniques

dynamiques pour résoudre ce problème.

Page 24: Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke1 Indexes à Arbres et Indexes à Hachage Sections sélectionnées des Chapitres 10 & 11

Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke 24

Hachage Extensible Situation: un bucket (page primaire) se

remplit. Pourrait-on réorganiser le fichier en doublant le # de buckets? Lire et écrire toutes les pages est très coûteux! Solution: Utiliser un répertoire de pointeurs vers

les buckets; doubler le # de buckets en doublant la taille du répertoire, tout en ne partageant que les buckets en débordement!

Le répertoire est bien plus petit que le fichier lui-même, d’où doubler le répertoire est moins coûteux. Plus besoin de pages de débordement!

Page 25: Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke1 Indexes à Arbres et Indexes à Hachage Sections sélectionnées des Chapitres 10 & 11

Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke 25

Exemple Le répertoire est de taille 4. Pour trouver un bucket pour r,

prendre un # de bits à la fin de h(r) équivalent à la `profondeur globale’; p.ex. Si h(r) = 5 (= binaire 101), r

est dans le bucket vers le quel pointe 01.

Insertion: Si le bucket est plein, le partager (affecter une n’lle page, et redistribuer).

Si nécessaire, doubler le répertoire. (En fait, partager un bucket n’entraîne pas nécessairement le doublement du répertoire; un doublement n’est nécessaire que si la profondeur globale ne correspond plus a la profondeur locale.)

13*00

01

10

11

2

2

2

2

2

PROFONDEUR LOCALE

PROFONDEUR GLOBALE

REPERTOIRE

Bucket A

Bucket B

Bucket C

Bucket D

PAGES DE DONNEES

10*

1* 21*

4* 12* 32* 16*

15* 7* 19*

5*

Page 26: Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke1 Indexes à Arbres et Indexes à Hachage Sections sélectionnées des Chapitres 10 & 11

Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke 26

Insertion de h(r)=20 (Cause un Doublement)

20*

00

01

10

11

2 2

2

2

PROFONDEUR LOCALE2

2

REPERTOIRE

PROFONDEUR GLOBALEBucket A

Bucket B

Bucket C

Bucket D

Bucket A2(`image'de Bucket A)

1* 5* 21*13*

32*16*

10*

15* 7* 19*

4* 12*

19*

2

2

2

000

001

010

011

100

101

110

111

3

3

3DIRECTORY

Bucket A

Bucket B

Bucket C

Bucket D

Bucket A2(`image'de Bucket A)

32*

1* 5* 21*13*

16*

10*

15* 7*

4* 20*12*

PROFONDEUR LOCALE

PROFONDEUR GLOBALE

Page 27: Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke1 Indexes à Arbres et Indexes à Hachage Sections sélectionnées des Chapitres 10 & 11

Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke 27

Insertion de h(r)=20 (Suite) 20 = binaire 10100. Derniers 2 bits (00) indiquent

que r appartient au bucket A qui est déjà plein! On divise A en A et A2. mais on a besoin des 3 derniers bits pour décider. Profondeur Globale du répertoire: Max # de bits

nécessaires pour décider du bucket auquel une entrée appartient.

Profondeur Locale d’un bucket: # de bits utilisés pour déterminer si une entrée appartient à ce bucket.

Quand double-t-on le répertoire? Avant insertion p.l. du bucket = p.g.. L’insertion entraîne

p.l. > p.g.; le répertoire est doublé par copie (‘’copying over’’) et réarrangement des pointeurs.

Page 28: Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke1 Indexes à Arbres et Indexes à Hachage Sections sélectionnées des Chapitres 10 & 11

Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke 28

Résumé

Index en arbre: ISAM, arbres B+ ISAM est une structure statique

Seules les feuilles sont modifiées; pages de débordement nécessaires

Défaut: chaînes de débordements Arbres B+ est une structure dynamique.

Insertion et effacement laissent l’arbre balancé coût de log F N Pas de chaînes de débordement

‘’Bulk loading’’ des arbres B+ Index à hachage: Hachage statique vs. extensible