Cours de Bases de données








télécharger 391.04 Kb.
titreCours de Bases de données
page11/14
date de publication23.12.2016
taille391.04 Kb.
typeCours
ar.21-bal.com > droit > Cours
1   ...   6   7   8   9   10   11   12   13   14

XVI.LES INDEX



Un index est une structure annexe à un fichier. C’est très pratique pour la recherche mais il est difficile de faire les mises à jour lorsque l’on a beaucoup d’index.
Index :
Fichiers

Données


  • Il est caractérisé par une clé de recherche K,

  • Il contient un ensemble d'entrées que l'on notera K*.


Les entrées d'un index



Un enregistrement dans l'index constitue une entrée K* permettant de retrouver efficacement le(s) enregistrement(s) ayant la valeur K. Trois structures possibles pour les entrées :


  1. Enregistrement ayant la même structure que les enregistrements du fichier de données.

  2. Une paire < K, IdE >

  3. Une paire < K, liste_IdE >


Si la structure de l'index est 1 alors pas besoin d'avoir en plus un fichier de données séparé.

Propriétés des index



Dense vs clairsemé

2.1) Index ISAM


Indexed Sequential Access Method






2.2) Arbres B+



Appelé B comme « Balancé » (équilibré en fait).Un arbre-B+ est caractérisé par sa dimension d qui est le nombre minimal de clés devant se trouver dans chaque nœud. d est la moitié du nombre maximal de clés qu'un nœud peut contenir. La structure des nœuds "feuille" est différente de celle des nœuds internes.images\orga17.jpg


Les nœuds non terminaux sont des pointeurs vers des « feuilles » index et les feuilles sont des pointeurs vers les données. Les feuilles sont liées entres elles. La structure d’un nœud interne est :

Ptr0

clé1

Ptr1

clé2



Ptrn

Si t est la taille d’un couple < Ptr, clé > et si T est la taille d’une page de l’index alors on prend généralement d=T/2t (chaque nœud doit être à moitié rempli) sauf pour la racine.

Coût d’une recherche dans un fichier indexé par un arbre B+


Comme l’arbre est équilibré, si h est la profondeur de l’arbre (le nombre de niveaux), le nombre de lectures qu’on doit faire avant d’atteindre une feuille c’est h. Ensuite, on accède directement à la page de données. D’où un coût total de clés dans le fichier de données. Au maximum, ces N clés sont stockés sur N/d feuilles.

Avec chaque feuille contient 2xd clés au maximum et d clés au min. Le niveau h contient N/d feuilles au maximum et le niveau h- 1 contient (N/d)/d nœuds au maximum. On a N/d pointeurs au niveau h - 1 donc N/d paires . Ces N/d paires sont réparties au maximum sur (N/d)/d nœuds. Le niveau h-2 contient N/d3 nœuds au maximum.

Le niveau 1 contient un seul nœud au maximum.

dh-1=N  (h-1) log d = log N  h-1 = logd N  h= logd N+1.

Le coût de la recherche avec égalité en utilisant un arbre B+ est de l’ordre de logd N avec d qui est l’ordre de l’index et N le nombre de pages dans le fichier de données.

Exemple d'un arbre B+


images\orga18.jpg

Chaque nœud de l'index contient au moins 100 paires . La recherche d’un enregistrement nécessite le parcours en profondeur de l'index.

logd N lectures = log 1000 / log 100 = 3/2  2

L'éclatement d'une feuille implique une remontée de la plus petite clé se trouvant dans la nouvelle feuille (dans l'exemple, c'est la clé 5). L'éclatement d'un nœud interne provoque le déplacement de la plus petite clef du nouveau nœud vers le nœud parents (dans l'exemple, la clé 17 a été déplacée vers un nœud parent).

Insertion de 8




Suppression de 19




Suppression de 20



nœud f n'étant pas à moitié plein:

      1. 24 est ramené de fi vers f

L'entrée index 21 pointant vers fi remplace l'entrée 24 pointant vers fi

Dans cet exemple, la redistribution est possible car un des nœuds adjacents contient plus de d éléments.

Suppression de 24



voisin de f ne contient que 2 éléments, il n'est pas possible de faire de redistribution.
1) f est fusionné avec fi: 27* et 29* sont ramenées vers f

2) L'entrée index 27 pointant vers fi est supprimée du nœud m
Quand la fusion se fait avec le voisin à droite, ce sont les clés du voisin qui viennent dans f et l'entrée pointant vers fi est supprimée du nœud parent. Quand la fusion se fait avec le voisin gauche, ce Sont les clés de f qui Sont ramenées vers fi et l'entrée pointant vers f est supprimée du noeud parent.

Insertion


La dimension du B-arbre est d
1. Trouver la feuille f où k doit être insérée.

2. Si f n'est pas pleine alors y insérer k

Sinon /* f est remplacée par f et f1 */

mettre d entrées dans f et d+ 1 entrées dans f1

insérer la d + 1ère clé dans le noeud m parent de f (appel récursif)

le fils gauche pointe vers f

le fils droit pointe vers f1 Finsi
3. Au niveau du nœud index m, si m est plein alors remplacer m par m et m1

Soit k1,.. . ,kd,kd+1,kd+2,. . . ,k2d,k2d+1

mettre k1,... ,kd dans m

d

mettre kd+2,. .. ,k2d+1 dans m1

d

insérer kd+1 dans le noeud parent de m

Suppression



1. Soit f la feuille où k se trouve

2. Supprimer k de f

3. Si f contient au moins d clés, alors FIN

4. Sinon

Si la redistribution avec les nœuds adjacents (le même parent) est possible, alors

faire la redistribution

Finsi

Sinon /* redistribution pas possible */

fusionner f avec un des nœuds adjacents

Supprimer du parent m de f un clé /*appel récursif */

Finsi

Création d'un arbre B+



Nous avons un fichier F pour lequel on veut créer un index sur la clé K. La première manière de procéder est de parcourir F et utiliser l'algorithme d'insertion dans un arbre B+ pour chaque clé lue. Le coût approximatif de ce procédé est le coût du parcours de F (i.e N/d' avec d' le nombre d'enregistrements qu'on peut mettre dans une page), plus le coût de l'insertion de chaque clé.

Soit h la hauteur de l'arbre B+, l'insertion d'une clé consiste à parcourir l'arbre à partir de la racine jusqu'à une feuille (i.e h lectures), ensuite l'écriture dans une feuille et sa recopie sur le disque (1 écriture). S'il y a éclatement, on est obligé de remonter d'un niveau et au pire, on doit remonter jusqu'a la racine, i.e 3h écritures. Le coût global est donc majoré par N/d'+(N*3*h).

Une autre manière de procéder consiste à :
1. d'abord trier les clés à insérer,

2. insérer un pointeur dans la racine vers la page la plus à gauche,
La suite de la procédure est expliquée sur l'exemple


Les pages du fichier triées sont les feuilles de l'arbre. Elles sont rentrées de gauche à droite, et l'insertion d une telle feuille conduit à l'insertion d'une clé dans le niveau supérieur de l'arbre. Cette dernière insertion peut être suivie d'un éclatement d'un nœud et l'augmentation d'un niveau de l'arbre.
Cette méthode est plus rapide que les insertions répétées.

2.3) Tri externe



C'est une opération très utile


  • ORDER BY

  • Le tri est utilisé lors de la création d'arbres B+

  • Elimination de doublons (voir prochains cours)

  • Des algorithmes de jointures l'utilisent (voir prochains cours)


Par exemple, pour trier un fichier de 10 Go quand on a une RAM de l00 Mo

Tri par fusion simple



Utilise 3 zones tampons
1. première étape: lire une page, la trier, et le réécrire (une seule zone tampon est utilisée)

2. Les étapes suivantes : les 3 zones tampons sont utilisées


  • A chaque étape, nous lisons et écrivons chaque page du fichier.




  • Si N est le nombre de pages, alors le nombre d'étapes est égal a [log2N] + 1




  • ainsi, le coût total est de

2N ( [log2 N] + 1)

Tri par fusion général



Utiliser plus de 3 zones tampon (ce qui est généralement possible) pour trier un fichier a N pages quand on a B zones tampons.


  1. étape 1 : utiliser les B zones ce qui donne en sortie [N/B] "sous fichiers" triés et chacun ayant B pages (sauf peut être le dernier qui en contiendra moins).

  2. étapes suivantes, on fusionne B - 1 "sous fichiers".


Coût du tri par fusion général



Nombre d'étapes : 1+ [log B-l N]. Le coût est donc 2N* nombre d'étapes.
Par exemple, avec 5 tampons et un fichier de 108 pages :
1. 1ère étape : [108/5]  22 "sous fichiers" triés de 5 pages chacun (le dernier en contient 3).
2. 2ème étape : [22/4]  6 "sous-fichiers" de 20 pages chacun (le dernier en contient 8).
3. 3ème étape : 2 sous fichiers, un de 80 pages et l'autre ayant 28.
4. 4ème étape : 1 fichier trié de 108 pages.

Nombre d’étapes pour différentes valeurs de N et B :

N

B=3

B=5

B=9

B=17

B=129

B=257

100

7

4

3

2

1

1

1000

10

5

4

3

2

2

10000

13

7

5

4

2

2

100000

17

9

6

5

3

3

1000000

20

10

7

5

3

3

10000000

23

12

8

6

4

3

100000000

26

14

9

7

4

4

1000000000

30

15

10

8

5

4


Pour obtenir le coût, il suffit de multiplier le nombre d'étapes par 2N

EXERCICES

3.1) Soit l'arbre B+ d'ordre 1 suivant :





td orga 1.jpg


Donner les configurations consécutives de l'arbre après :

  1. l'insertion de la clé 23 puis

  2. la suppression de la clé 10.





1.

    1. répartition des clés {21, 22, 23} (ici d=1). Les d premières, on les garde dans l’ancienne feuille f. Les d+1 suivantes dans la nouvelle feuille f1.

d = (nombre max de clé par feuille) / 2

    1. Remontée de 22 (plus petite clé se trouvant dans f1).




20
Pointeur gauche : < pointeur droit : 

22

11



23

22

17

15

21

10


f f1

Les clés présentes au niveau du fichier données sont toutes présentes au niveau des feuilles de l’index. Les clés se trouvant dans les nœuds internes de l’index ne sont pas nécessairement présentes dans le fichier des données. Dans l’exercice, nous avons 11 qui apparaît dans un nœud interne mais pas au niveau des feuilles : on peut en conclure qu’à un certain moment, 11 a été inséré puis supprimé.
2. f contient moins de d clés. On va essayer de faire une répartition avec les feuilles adjacentes qui est f1. La répartition est possible : on déplace 15 vers f, on remplace 11 par 17.

(on évite de supprimer des feuilles).


20



22

17



23

22

17

21

15


f f1
3.2) Insertion d'une clé dans un autre arbre
L'arbre B+ ci-dessous a été obtenu suite à l'insertion d'une clé dans un autre arbre. On nous dit aussi que la dite insertion a provoqué l'éc1atement d'un nœud de l'arbre.

Donner une configuration possible de l'arbre d'origine avec la clé qui y aurait été insérée. Cette configuration est-elle unique ? Si ce n'est pas le cas, alors donner toutes les configurations possibles de l'arbre d'origine.
La valeur qu’on a inséré doit se trouver au niveau des feuilles : {1, 10, 15, 17, 19 ou 20}. Comme il y a eu un éclatement, on en déduit une remontée d’une clef se trouvant au niveau des feuilles {19}. On en conclut aussi que c’est la feuille f qui a été éclatée en deux. Lors de l’insertion, on s’est retrouvé avec les clés {17, 19, 20}. Initialement dans f, on aurait pu avoir


  1. 17 et 19 et insertion 20


16

8


17

19

15

10

1



  1. 19 et 20 et insertion 17


16

8


17

20

15

10

1



  1. 17 et 20 et insertion 19


16

8


19

20

15

10

1

3.3) Coût de création d’un arbre B+



Donner un estimation du coût de création d’un arbre B+ en fonction de N, de B et de M sachant que le coût comprend le coût de création et le coût du tri : 2M [1+ logB-1 (M/B)].

N : nombre d’enregistrements,

B : nombre de zones tampons,

M : nombre de pages du fichier.

La hauteur de l’arbre principal est donnée par logd N où d est la dimension. L’arbre final contient un nombre total de nœuds qui est approximativement égal à :

Nombre de nœuds feuilles = N/2d (toutes les feuilles sont pleines).

Nombre de nœuds au niveau supérieur (sachant que l’on a besoin de N/2d pointeurs et que chaque nœud contient au minimum d+1 pointeurs) = (N/2d) / (d+1).

Nombre de nœuds au niveau supérieur = (N/2d) / (d+1)²

Le nombre total de nœuds :

h

(N/2d) 1/(d+1)i

i=1
Transactions

1   ...   6   7   8   9   10   11   12   13   14

similaire:

Cours de Bases de données iconAdministrateur(trice) de bases de données / Intégrateur(trice) d’applications
«Accompagner les transitions agro-écologiques des systèmes et territoire d’élevage») et sur le pôle basmati («Bases de données, modèles...

Cours de Bases de données iconI ] Les différents modèles de bases de données

Cours de Bases de données iconUniversité Sidi Mohamed Ben Abdellah
«pose» sur le IaaS. IL permet d’externaliser l’infrastructure matérielle, mais également des applications middleware : bases de données,...

Cours de Bases de données iconC onsultant(e) système spécialiste O. S. et bases de données / Grenoble...

Cours de Bases de données iconProtection des logiciels et des bases de données

Cours de Bases de données iconM. Bilodeau est un professionnel dynamique, versé dans plusieurs...

Cours de Bases de données iconPour les projets de logiciels et/ou de bases de données, cette déclaration...

Cours de Bases de données iconCours : mat-4172-2 Collecte de données en contexte fondamental

Cours de Bases de données iconAccès sécurisés aux données partout dans le monde avec aprol
«parlantes» sont transférées à la base de données du cloud. Cette méthode basée sur les concepts du fog computing (informatique géodistribuée)...

Cours de Bases de données iconAu risque de refroidir les ardeurs de quelques dsi, le temps semble...
«humeur» des internautes. A nous les connexions vers les sites métiers pour remplir nos bases de données des informations professionnels...








Tous droits réservés. Copyright © 2016
contacts
ar.21-bal.com