Arbre b (par EL HACHEM Marwan et RICHA Elias)

Présenté par: Elias Richa

Marwan El Hachem

Arbre B et B+

2

PLAN• Arbre B

– Définition– Structure – Propriétés– Recherche– Insertion– Suppression

• Arbre B+– Définition– Structure – Propriétés– Recherche– Insertion– Suppression

3

Arbre B

4

Définition

• Un arbre B (ou B-Tree) est un arbre binaire de recherche équilibré

• Chaque chemin de la racine à une feuille est de la même longueur h (hauteur)

• Stocke les données sous une forme triée• Permet une exécution des opérations

d'insertion et de suppression

5

Structure de nœud d'un arbre B

• K clés avec k1 < k2 < ... < kk

• (k+1) pointeurs

6

Propriétés

• La racine, si elle n’est pas une feuille, doit avoir au minimum deux fils

• Chaque nœud contient k clés avec– 1 ≤ k ≤ 2m (nœud racine)– m ≤ k ≤ 2m (nœud non racine)

• Toutes les clés d’un nœud sont triées (i.e. k1< k2 < · · · < kk pour k clés)

7

Exemple d’arbre B d’ordre m = 2

• Chaque nœud, sauf la racine, contient k clés (2 ≤ k ≤ 4)

• La racine contient k clés (1 ≤ k ≤ 4)

8

Recherche dans arbre B

• A partir de la racine, pour chaque nœud on examine :– La clé est présente succès– K < k1 recherche dans P0

– K > k recherche dans Pk

– ki < K < ki+1 recherche dans Pi

9

Recherche de 15

10

• Nombre de clé dans un Arbre B d’ordre m, et de hauteur h– Nb clés min = 2*(m+1) h - 1– Nb clés max = (2*m+1) h+1 - 1

o Par exemple si m = 100, h = 2– Nb clés min = 20401 et – Nb clés max =8 120 600

11

Insertion dans un arbre B d’ordre m

• Recherche de la feuille d’insertion• Si la feuille n’est pas pleine insérer la clé a sa

place• Sinon (la feuille est pleine)

– Laisser les m plus petites clés dans le nœud– Allouer un nouveau nœud et y placer les m plus

grandes clés– Remonter la clé médiane dans le nœud père – Application récursive de ce principe jusqu’à la racine

Principe :

12

Insertion d’un élément dans un arbre B• Exemple 1 : Insertion de la clé 75 dans l’arbre B d’ordre 2

13

• Éclatement du nœud en 2• Les 2 plus petites clés restent dans le nœud

(68 et 69)• Les 2 plus grandes clés sont insérées dans un

nouveau nœud (75 et 76)• Remontée de la clé médiane (71) dans le

nœud père

14

Insertion d’un élément dans un arbre B• Exemple 2 : Insertion de la clé 9 dans l’arbre B d’ordre 2

15

• Éclatement du nœud par l'arrivée de la clé 9• Remontée de la clé 8 au nœud père• Éclatement du nœud par l'arrivée de la clé 8• Création d'une nouvelle racine avec la clé 11• Augmentation d'une unité de la hauteur

16

Principe

• Cas 1 : suppression dans un nœud feuille

– Le nombre de clé est m tasser les clés dans le nœud – Le nombre de clé devient < m combiner avec un

nœud adjacent ce qui entraine la descente d’une clé du nœud père avec éventuellement une réorganisation locale

– La réduction du nœud père avec moins de m clés entraine la combinaison de ce nœud père avec un nœud voisin du même niveau remontée éventuelle jusqu’à la racine

Suppression d’un élément dans un arbre B

17

Principe

• Cas 2 : suppression dans un nœud non feuille– Rechercher une clé adjacente à la clé à

supprimer – Soit la plus petite du sous arbre droit– Soit la plus grande du sous arbre gauche– Remplir la clé à supprimer par la clé adjacente

trouvée– Supprimer la clé adjacente (Équivalent à la

suppression dans une feuille)

Suppression d’un élément dans un arbre B

18

Suppression d’un élément dans un arbre B

• Exemple 1 : suppression de la clé 25 de la table B d’ordre 2

19

• Suppression dans une feuille le nombre d’élément devient <2

• Combinaison avec un nœud voisin• Descente de la clé(15) • Suppression du nœud (20,25)

20

Suppression d’un élément dans un arbre B

• Exemple 2 : suppression de la clé 4 de la table B d’ordre 2

21

• Suppression dans une feuille le nombre d’élément devient <2

• Combinaison avec un nœud voisin• Descente de la clé(3) • Suppression du nœud (4,7)

22

• La hauteur de l'arbre est passée de 2 à 1

• le nombre d’élément devient <2 (8)• Combinaison avec un nœud voisin(16,21)• Descente de la clé(11)

23

Suppression dans un nœud non feuille

• Exemple 1 : suppression de la clé 5 de la table B d’ordre 2

• Recherche d’une clé adjacente de la clé on prend la plus grande clé du sous arbre gauche de la clé(4)

• Remplacement de la clé par la clé adjacente trouvée• Suppression de la clé trouvée dans un nœud feuille

24

Suppression dans un nœud non feuille

• Exemple 2 : Suppression de la clé 5

25

Suppression dans un nœud non feuille

• Exemple 3 : Suppression de la clé 4

26

L’arbre devient

27

Arbre B+

28

Définition

• Un arbre B + est un arbre B ou les feuilles contiennent toutes les clés

• C’est un arbre équilibré où chaque chemin de la racine à une feuille est de même longueur H (hauteur)

• Chaque nœud (bloc) contient n pointeurs et n-1 valeurs (clés), où n est l’ordre de l’arbre

29

Structure de nœud d'un arbre B+

Valeurs < C1 Valeurs >=C1 et < C2

• n-1 clés avec C1 < C2 < ... < Cn-1

• n pointeurs

P1 C1 P2 C2 … P n-1 C n-1 Pn

30

Propriétés

• Racine a au moins 2 fils (sauf si elle est feuille)• Chaque nœud sauf la racine a entre [n/2 ] et

[n] pointeurs (ex. pour n=4, on a entre 2 et 4 pointeurs)

• Chaque feuille contient entre [n-1/2 ] et [n-1] clés (ex. pour n=4, on a entre 2 et 3 clés)

31

Exemple d’un arbre B+ pour n=4

32

Recherche dans arbre B+

33

Recherche de 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

34

Insertion dans arbre B+

• Insertion simple• Débordement et division du bloc

• Division de la racine • Division de feuille• Division de feuille et racine

35

Insertion simple

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

• Insertion de 25

36

Débordement et division (Racine)• 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

37

Débordement et division (Feuille)• Insertion de 10• Débordement et la division du bloc 0 (Nouvelle feuille)• 25 est promue

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

38

Débordement et division (Feuille, Racine)• Insertion de 45• Débordement et division du bloc 1 (Nouvelle feuille)• 50 est promue• Division de la racine

10

Bloc 0

20

25 40 60

Bloc 2

25

Bloc 3

30 40

Bloc 1

50 53 60

Bloc 4

70

10Bloc 0

20

25 40Bloc 2

25Bloc 3

30 40Bloc 1

45 60Bloc 4

7050Bloc 5

53

60Bloc 6

50Bloc 7

39

Suppression dans arbre B+• Uniquement dans une feuilleTypes:• Suppression simple• Suppression et redistribution au niveau nœud

racine • Suppression par violation du minimum• Cas de fusion de feuilles et de redistribution

au niveau nœud racine

40

Suppression simple

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

• Suppression de 70

41

Suppression et redistribution au niveau nœud racine

• Suppression de 50

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

42

Violation du minimum : redistribution si possible

40Bloc 2

20Bloc 0

25 30 40Bloc 1

60

30Bloc 2

20Bloc 0

25 30Bloc 1

60

• Suppression de 40

43

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

• Suppression de 53

44

Cas de fusion de feuilles et de redistribution au niveau du parent (suite)

10Bloc 0

20

25 40Bloc 2

25Bloc 3

30 40Bloc 1

45 50Bloc 5

60 70

60Bloc 6

50Bloc 7

Violation de la règle du minimum

Redistribution

10Bloc 0

20

25Bloc 2

25Bloc 3

30 40Bloc 1

45 50Bloc 5

60 70

50Bloc 6

40Bloc 7

45

Références• [1] Dr.Mounir GRARI. LA STRUCTURE D'ARBRE-B. Institut

National des Sciences Appliquées– Rouen. 40 diapos. Accédé le 10/12/2013.

• [2] Sofian MAABOUT. Arbre-B+. Laboratoire Bordelais de Recherche en Informatique. 21 diapos. Accédé le 10/12/2013.

www.labri.fr/perso/maabout/L3M/index.ppt

• [3] Pr. Eamonn Keogh. Chapter 9 of DBMS – B-Tree. 37 diapos. Accédé le 9/12/2013.

www.cs.ucr.edu/~eamonn/teaching/cs166materials

46