LA STRUCTURE D'ARBRE-B

Institut National des Sciences Appliquées – Rouen

Département Architecture des Systèmes d’Information

LA STRUCTURE D'ARBRE-B

• A) RECHERCHE

• B) INSERTION

• C) SUPPRESSION

• D) INDEX PAR ARBRE-B+

• E) MEMOIRE SECONDAIRE

ARBRE-B• UN ARBRE-B D'ORDRE m EST UN

ARBRE /

1/ CHAQUE NOEUD CONTIENT k CLES TRIEES AVEC :

m k 2m (noeud non racine)1 k 2m (noeud racine)

2/CHAQUE CHEMIN DE LA RACINE A UNE FEUILLE EST DE MEME LONGUEUR h (HAUTEUR)

3/UN NOEUD EST :- SOIT TERMINAL (FEUILLE)- SOIT POSSEDE (k+1) FILS /

LES CLES DU ième FILS ONT DES VALEURS COMPRISES ENTRE LES

VALEURS DES (i-1)ème ET ième CLES DU PERE

STRUCTURE D'UN NŒUD (ARBRE-B D'ORDRE m)

-> k CLES AVEC k1 < k2 < ... < kn

-> (k+1) POINTEURS /- TOUS SONT DIFFERENTS DE NIL

SI LE NOEUD N'EST PAS UNE FEUILLE - TOUS A NIL SI LE NOEUD EST UNE FEUILLE

P0 K1 P1 K2 P2 PkKkPk-1

K < K1 K1 < K < K2 K2< K < K3 Kk-1 < K < Kk K > Kk

CAPACITE

• NOMBRE DE CLES

ARBRE-B d'ORDRE m , et de hauteur h

-> NbClesMin = 2*(m+1) - 1

-> NbClesMax = (2*m+1) - 1

m = 100, h = 2

==> NbClesMax = 8 000 000

• STOCKAGE SUR DISQUE

-> UN NOEUD = UNE PAGE

h+1

h

EXEMPLE (n°0)

• ARBRE-B D'ORDRE 2 -> CHAQUE NOEUD, SAUF LA

RACINE CONTIENT k CLES AVEC 2 k 4

-> LA RACINE CONTIENT k CLES AVEC 1 k 4

51

11 30 66 78

2 7 35 41 53 54 63 79 84 93

68 69 71 7612 15 22

RECHERCHE(D'UN ELEMENT DE CLE K)

• METHODEA PARTIR DE LA RACINE, POUR

CHAQUE NOEUD EXAMINE

- LA CLE K EST PRESENTE : SUCCES

- K < k1-> RECHERCHE DANS P0^

- K > k-> RECHERCHE DANS Pk^

- ki < K < ki+1-> RECHERCHE DANS Pi^

• SI UN DES POINTEURS VAUT NILLA RECHERCHE EST UN ECHEC

INSERTION D'UN ELEMENTDANS UN ARBRE-B

INSERTION DE LA CLE 75(Dans l'arbre-B de l'exemple 0)

• INSERTION DE 75 DANS UN NŒUD PLEIN => 5 CLES

• ECLATEMENT DU NOEUD EN 2 :- LES 2 PLUS PETITES CLES RESTENT DANS LE NOEUD- LES 2 PLUS GRANDES CLES SONT INSEREES DANS UN NOUVEAU NOEUD

• REMONTEE DE LA CLE MEDIANE (71) DANS LE NOEUD PERE

51

11 30 66 78

2 7 35 41 53 54 63 79 84 93

68 69 71 7612 15 22

INSERTION DE LA CLE 75 (2)

• L'ARBRE-B DEVIENT

51

11 30 66 78

2 7 35 41 53 54 63 79 84 93

68 69

71

7612 15 22

75

EXEMPLE (n°1)

• ARBRE-B D'ORDRE 2

5 11 16 21

1 2 3 4

6 7 8 10

12 13 14 15

17 18 19 20

22 23 24 25

INSERTION DE LA CLE 9

• Eclatement du noeud par l'arrivée de la clé 9 

-> Remontée de la clé 8 au noeud père

• Eclatement du noeud 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

6 7 8 10

5 11 16 21

ETAPE INTERMEDIAIRE

5 11 16 21

1 2 3 4

6 7

12 13 14 15

17 18 19 20

22 23 24 25

8

9 10

ZONE MEMOIRE TAMPON

11

5 8 16

1 2 9 10 1213 14

17 18

21

23

6 7

2243

19 20

15 24 25

PRINCIPE DE L'INSERTION DANS UN ARBRE-B D'ORDRE

m• RECHERCHE DE LA FEUILLE

D'INSERTION

Si LA FEUILLE N'EST PAS PLEINEAlors

INSERER LA CLE "A SA PLACE"

Sinon/*La feuille est pleine 2m clés*/LAISSER LES m PLUS PETITES

CLES DANS LE NOEUDALLOUER UN NOUVEAU NOEUD ET Y PLACER LES m PLUS GRANDES CLESREMONTER LA CLE MEDIANE DANS

LE NOEUD PEREAPPLICATION RECURSIVE DE CE

PRINCIPEEVENTUELLEMENT JUSQU'A LA RACINE

Finsi

SUPPRESSION D'UN ELEMENT DANS UN ARBRE-B

EXEMPLE (n°2)

• ARBRE B D'ORDRE 2

• SUPPRESSION DE LA CLE 25

-> SUPPRESSION DANS UNE FEUILLE -> LE NOMBRE D'ELEMENT DEVIENT <

2 -> COMBINAISON AVEC UN NŒUD VOISIN-> DESCENTE DE LA CLE (ICI 15)-> SUPPRESSION DU NOEUD

20 25

10

15

27

12 14 20

10 15 27

12 14 20 25

EXEMPLE (n°3)

• D'ARBRE B D'ORDRE 2 

• SUPPRESSION DE LA CLE 6  (SUPPRESSION DANS UNE FEUILLE)

-> LE NOMBRE D'ELEMENT < 2-> COMBINAISON AVEC UN NOEUD VOISIN  -> DESCENTE DE LA CLE (ICI 4)-> NOMBRE DE CLES > 4-> REDISTRIBUTION AVEC REMONTEE DE LA CLE MEDIANE (ICI 3)

4 8

1 2 6 73

4

8

1 2 7

3

EXEMPLE (n°4)

• ARBRE-B D'ORDRE 2 (ETAT INITIAL)

• SUPPRESSION DE LA CLE 4

• FINAL

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

11

3 8

1 2 4 7 9 10

16 21

11

3

8

1 2 7 9 10

16 21

11

3

8

1 2 7 9 10

16 21

EXEMPLE (n°5)

• D'ARBRE-B D'ORDRE 2

• SUPPRESSION DE LA CLE 5(SUPPRESSION DANS UN NOEUD NON FEUILLE)

-> RECHERCHE D'UNE CLE ADJACENTE DE LA CLE : ON PREND LA PLUS GRANDE CLE DU SOUS-ARBRE GAUCHE DE LA

CLE -> REMPLACEMENT DE LA CLE PAR LA

CLE ADJACENTE TROUVEE-> SUPPRESSION DE LA CLE TROUVEE DANS

UN NOEUD FEUILLE

5 8

1 2 3 4 6 7 9 10

4 8

1 2 3 6 7 9 10

EXEMPLE EN CASCADE

• SUPPRESSION DE LA CLE 5

11

5 8 16

1 2 9 10 1213 14

17 18

21

23

6 7

2243

19 20

15 24 25

11

8 16

1 2 9 10 1213 14

17 18

21

23

6 7

22

4

3

19 20

15 24 25

EXEMPLE EN CASCADE (2)

• SUPPRESSION DE LA CLE 6

• SUPPRESSION DE LA CLE 4

11

8 16

1 2 9 10 1213 14

17 18

21

237 223

19 20

15 24 25

11

8 16

1 2 9 10 1213 14

17 18

21

23

7

22

4

3

19 20

15 24 25

EXEMPLE EN CASCADE (3)

• ETAT FINAL

118 16

1 2

9 10 1213 14

17 18

21

23

7

22

3

19 20

15 24 25

PRINCIPE DE LA SUPPRESSION

• CAS n°1SUPPRESSION DANS UNE FEUILLE

- LE NOMBRE DE CLES EST ≥ m-> TASSER LES CLES DANS LE NOEUD 

 

- LE NOMBRE DE CLE DEVIENT < m-> COMBINER AVEC UN NOEUD ADJACENT CE QUI ENTRAINE LA DESCENTE D'UNE CLE DU NOEUD PERE AVEC EVENTUELLEMENT UNE REORGANISATION LOCALE

LA REDUCTION DU NOEUD PERE AVEC MOINS DE m CLES ENTRAINE LA

COMBINAISON DE CE NOEUD PERE AVEC UN NOEUD VOISIN DU MEME

NIVEAU REMONTEE EVENTUELLE JUSQU'A LA RACINE

PRINCIPE DE LA SUPPRESSION (2)

• CAS n°2SUPPRESSION DANS UN NOEUD

NON FEUILLE  - RECHERCHER une CLE ADJACENTE

à la clé à SUPPRIMER- SOIT LA PLUS PETITE DU SOUS

ARBRE DROIT- SOIT LA PLUS GRANDE DU SOUS ARBRE GAUCHE

-REMPLACER LA CLE A SUPPRIMER PAR LA CLE ADJACENTE TROUVEE

- SUPPRIMER LA CLE ADJACENTE (EQUIVALENT A LA SUPPRESSION DANS UNE FEUILLE)

INDEX PAR ARBRE B+

STRUCTURE D'ARBRE B+

•  DEFINITIONUN ARBRE B+ EST UN ARBRE B OU

LES FEUILLES CONTIENNENT TOUTES LES CLES

• SCHEMA D'UN NOEUD :

• SUPPRESSION D'UNE CLE : UNIQUEMENT DANS UNE FEUILLE

• UTILISATIONSERT EN PRATIQUE A LA PLACE DES

ARBRES B POUR L'ORGANISATION DES DONNEES SUR DISQUE

P0 K1 P1 K2 P2 PkKkPk-1

K K1 K1 < K K2 K2< K K3 Kk-1 < K Kk K > Kk

CREATION : INDEX ARBRE B+

• RELATION VINS (NV, CRU, MIL, DEG)

-> NON PLACEE

• CREATION D'UN INDEX UNIQUE SUR NV

-> ARBRE B+ D'ORDRE 2

 

(NON PLACANT)

51

11 30 51 66 76

11 66 76 30 51

INDEX SUR NV EN ARBRE B+

PAGES DE LA RELATION VINS

INDEX NON GROUPANT

PLACEMENT PAR ARBRE B+

• RELATION VINS (NV, CRU, MIL, DEG)

-> PLACEE PAR ARBRE B+ D'ORDRE 2 SUR L'ATTRIBUT NV UNIQUE

(PLACANT)

125

110 125 142 156

101

INDEX SUR NV

PAGES DE LA RELATION VINS

INDEX GROUPANT

156

106 110 115 125

103

104

106

107

109

110

111

112

115

118

120

121

125

ARBRE B+• INDEX ORGANISE EN ARBRE B

+ENSEMBLE DE FEUILLES CONTENANT

LES CLES

• CONSEQUENCES- ECLATEMENT D'UNE FEUILLE : UNE COPIE

DE LA CLE MEDIANE EST REMONTEE- SUPPRESSION D'UNE CLE : UNIQUEMENT

DANS UNE FEUILLE

=> RECHERCHE JUSQU'AUX FEUILLES

INDEX

CLES

ACCES DIRECT

ACCES SEQUENTIEL

CRITIQUE PLACEMENT ARBRE B+

• AVANTAGES-> ACCES SEQUENTIEL TRIE SUR

CLE-> ACCES SELECTIF SUR CLE-> QUESTIONS INTERVALLE-> ADAPTE AUX RELATIONS

VOLUMINEUSES A FORTE CROISSANCE

• INCONVENIENTS-> TRAVERSEE INDEX POUR

ACCES SELECTIF-> MAJ COUTEUSE SI : Eclatement page (INSERTION)

Fusion page (SUPPRESSION)

PLACEMENT DES DONNEES SUR MEMOIRE SECONDAIRE

PAR ARBRE B

PLACEMENT DES RELATIONSPAR ARBRE B

• HYPOTHESES1 RELATION = 1 FICHIER1 TUPLE = 1 ENREGISTREMENT1 ATTRIBUT = 1 CHAMP

CLE DE PLACEMENT : MONO ATTRIBUT(CORRESPOND A LA CLE PRIMAIRE DE LA

RELATION DEFINIE LORS DE LA CONCEPTION DU SCHEMA)

• LA STRUCTURE D'ARBRE B SERT POUR L'ORGANISATION DES DONNEES SUR DISQUE

PLACEMENT (2)

• FICHIER ORGANISE SOUS FORME D'ARBRE B

-> A CHAQUE CLE K, DANS TOUT NOEUD DE L'ARBRE B, EST ASSOCIEE LA VALEUR DE

L'ELEMENT DE CLE K

• FICHIER INDEXE PAR ARBRE B

-> A CHAQUE CLE K, DANS L'INDEX ORGANISE EN ARBRE B, EST ASSOCIE UN POINTEUR

VERS L'ELEMENT DE CLE K

FICHIER ORGANISE EN ARBRE B

•  EXEMPLE : ARBRE B D'ORDRE 1

 • INCONVENIENTS-> 1 NOEUD = 1 BLOC DISQUE

LIMITATION DE L'ORDREAUGMENTATION HAUTEUR

-> RECHERCHE,LECTURE D'INFORMATIONS INUTILES

-> PARCOURS SEQUENTIEL DU FICHIER PARCOURS ARBRE B

51 Données

11 Données 30 Données

66 Données 76 Données

FICHIER INDEXE PAR ARBRE B

• INDEX = ARBRE B (DENSE)SEQUENTIEL TRIE PAR PARCOURS

D'ARBRE

• DONNEES : SEQUENTIEL NON TRIE

• EXEMPLE (avec arbre B d'ordre 1)

11 30 66 76

51

51 Données 11 Données 66 Données 76 Données 30 Données

PLACEMENT DES DONNEES SUR MEMOIRE SECONDAIRE

PAR ARBRE B+

L'ORGANISATION INDEXE IS3• INDEX = ARBRE B+ : DENSE ET TRIE• DONNEES = SEQUENTIEL NON TRIE • EXEMPLE : index = arbre B+ d'ordre 2

• Pointeurs vers des fichiers de données séquentiels et non triés51

11 30 66 76

2

7

11

12

15

22

30

35

41

51

53

54

63

66

68

69

71

76

79

84

93

L'ORGANISATION VSAM• ORGANISATION : SEQUENTIELLE

INDEXEE REGULIERE

• Ensemble index + données organisé sous la forme d'arbre B+

• Index est un ensemble des nœuds non feuilles : trié, non dense 

• Données est un ensemble de feuilles triées

• TOUTES LES CLES SONT DANS LES FEUILLES

INDEX

DONNEES

EXEMPLE DE FICHIER VSAM

• LE FORMAT DES FEUILLES EST DIFFERENT DU FORMAT DES NON

FEUILLES

• CREATION INITIALE DU FICHIER : CLES DONNEES DANS L'ORDRE ZONE

DATA REMPLIE A 75 %

125

110 125 142 156

101

INDEX

Données

156

106 110 115 125

103

104

106

107

109

110

111

112

115

118

120

121

125

ACCES A UNE RELATION

• CLE DE PLACEMENT : PLACEMENT PAR METHODE INDEXEE

• INDEX SECONDAIRE

RELATION PLACEE, DEUX FORMES

• INDEX SECONDAIRE EST LUI MEME ORGANISE SOUS LA FORME PAR EXEMPLE, D'UN ARBRE B

Valeur de la clé de placement

Adresse du TUPLE

Valeur de la clé secondaire

Adresse du TUPLE

Valeur de la clé de placement

Valeur de la clé secondaire

ou