Structures de données IFT-2000 Abder Alikacem Semaine 11, 1 ère partie Les B-arbres Département dinformatique et de génie logiciel Édition septembre 2009

Structures de donnéesIFT-2000

Abder AlikacemAbder Alikacem

Semaine 11, 1ère partieLes B-arbres

Département d’informatique et de génie logiciel

Édition septembre 2009

! +

Plan

• Les arbres B• Les arbres B+

Retour aux arbres binairesInsertion :

• par une feuille• feuille après feuille• toutes les racines sont fixées trop tôt

Arbres-B

3 6 8 9 12

Idée :

• avoir un tampon (tableau)

• 2 types de gestion• nœuds plus grands (tableau)

• choisir la bonne racine (plus stable)

Arbres-B

3 6 8 9 12

Arbres-B

3 6 8 9 12

Arbres-B

3 6 8 9 12

Arbres-B

3 6 9 12

8

Arbres-B

3 6 9 12

8

Arbres-B

3 6 9 12

8

3 6 9 12

Arbres-B

8

3 6 9 12

Arbres-B

8

3 6 9 12

Arbres-B

8

3 6 9 12

Arbres-B

8

3 6 9 12

Arbre-B d’ordre m

définition :• la racine a au moins 2 enfants à moins que ce ne soit une

feuille• aucun nœud n’a plus de m enfants• tous les nœuds, sauf la racine et les feuilles, ont au moins

m/2 enfants• toutes les feuilles apparaissent au même niveau• tout nœud qui a k enfants a k-1 éléments

3 6 8 10 12p0 p1 p2 p3 p4

e1 e2 e3 e4

8 15

3 6 9 12 16 20

Arbres-B : recherche

p0 si x < e1

pi si ei < x < ei+1

pm-1 si em-1 < x

3 6 8 10 p0 p1 p2 p3 p4

e1 e2 e3 e4

Utilisation d’arbres-B

• + indirection vers les données

10 20

5 7 8 22 24 32 35 3813 15 18 42 45 46

26 27

25

30 40

Arbre-B d’ordre m

• Outils pour la gestion d’un fichier binaire• Nœud typique & en-tête du fichier index (B-arbre)• La mécanique de la construction d’un B-Arbre• La procédure de la subdivision d’un nœud

3 6 8 10 p0 p1 p2 p3 p4

e1 e2 e3 e4

struct BTPAGE{

short keycount; /* Le compteur de clefs. Indique quand le noeud est plein.

*/

struct uneCle key [MAXKEYS]; /* Le tableau des clef. */

short CHILD[MAXKEYS+1]; /* Le tableau qui contiendra les fils pointés */

};

Structure typique d’un arbre-B

+: 20,40,10,30,15,35,7,26,18,22,5,42,13,46,27,8,32,38,24,45,25

Ajout dans un arbre-B d’ordre 5

20

+: 20,40,10,30,15,35,7,26,18,22,5,42,13,46,27,8,32,38,24,45,25


20 40

+: 20,40,10,30,15,35,7,26,18,22,5,42,13,46,27,8,32,38,24,45,25


10 20 40

+: 20,40,10,30,15,35,7,26,18,22,5,42,13,46,27,8,32,38,24,45,25


+: 20,40,10,30,15,35,7,26,18,22,5,42,13,46,27,8,32,38,24,45,25

10 20 30 40


+: 20,40,10,30,15,35,7,26,18,22,5,42,13,46,27,8,32,38,24,45,25

10 15 20 30 40


+: 20,40,10,30,15,35,7,26,18,22,5,42,13,46,27,8,32,38,24,45,25

10 15 20 30 40


+: 20,40,10,30,15,35,7,26,18,22,5,42,13,46,27,8,32,38,24,45,25

20

10 15 30 40


+: 20,40,10,30,15,35,7,26,18,22,5,42,13,46,27,8,32,38,24,45,25

20

10 15 30 35 40


+: 20,40,10,30,15,35,7,26,18,22,5,42,13,46,27,8,32,38,24,45,25

20

7 10 15 30 35 40


+: 20,40,10,30,15,35,7,26,18,22,5,42,13,46,27,8,32,38,24,45,25

20

7 10 15 26 30 35 40


+: 20,40,10,30,15,35,7,26,18,22,5,42,13,46,27,8,32,38,24,45,25

20

7 10 15 18 26 30 35 40


+: 20,40,10,30,15,35,7,26,18,22,5,42,13,46,27,8,32,38,24,45,25

20

7 10 15 18 22 26 30 35 40


+: 20,40,10,30,15,35,7,26,18,22,5,42,13,46,27,8,32,38,24,45,25

20

7 10 15 18 22 26 30 35 40


+: 20,40,10,30,15,35,7,26,18,22,5,42,13,46,27,8,32,38,24,45,25

20 30

7 10 15 18 35 40 22 26


+: 20,40,10,30,15,35,7,26,18,22,5,42,13,46,27,8,32,38,24,45,25

20 30

5 7 10 15 18 35 40 22 26


+: 20,40,10,30,15,35,7,26,18,22,5,42,13,46,27,8,32,38,24,45,25

20 30

35 40 5 7 10 15 18 22 26


+: 20,40,10,30,15,35,7,26,18,22,5,42,13,46,27,8,32,38,24,45,25

10 20 30

35 40 5 7 22 26 15 18


+: 20,40,10,30,15,35,7,26,18,22,5,42,13,46,27,8,32,38,24,45,25

10 20 30

35 40 42 5 7 22 26 15 18


+: 20,40,10,30,15,35,7,26,18,22,5,42,13,46,27,8,32,38,24,45,25

10 20 30

35 40 42 5 7 22 26 13 15 18


+: 20,40,10,30,15,35,7,26,18,22,5,42,13,46,27,8,32,38,24,45,25

10 20 30

35 40 42 46 5 7 22 26 13 15 18


+: 20,40,10,30,15,35,7,26,18,22,5,42,13,46,27,8,32,38,24,45,25

10 20 30

35 40 42 46 5 7 22 26 27 13 15 18


+: 20,40,10,30,15,35,7,26,18,22,5,42,13,46,27,8,32,38,24,45,25

10 20 30

35 40 42 46 5 7 8 22 26 27 13 15 18


+: 20,40,10,30,15,35,7,26,18,22,5,42,13,46,27,8,32,38,24,45,25

10 20 30

32 35 40 42 46 5 7 8 22 26 27 13 15 18


+: 20,40,10,30,15,35,7,26,18,22,5,42,13,46,27,8,32,38,24,45,25

10 20 30

32 35 40 42 46 5 7 8 22 26 27 13 15 18


+: 20,40,10,30,15,35,7,26,18,22,5,42,13,46,27,8,32,38,24,45,25

10 20 30 40

32 35 42 46 5 7 8 22 26 27 13 15 18


+: 20,40,10,30,15,35,7,26,18,22,5,42,13,46,27,8,32,38,24,45,25

10 20 30 40

32 35 38 42 46 5 7 8 22 26 27 13 15 18


+: 20,40,10,30,15,35,7,26,18,22,5,42,13,46,27,8,32,38,24,45,25

10 20 30 40

32 35 38 42 46 5 7 8 22 24 26 27 13 15 18


+: 20,40,10,30,15,35,7,26,18,22,5,42,13,46,27,8,32,38,24,45,25

10 20 30 40

32 35 38 42 45 46 5 7 8 22 24 26 27 13 15 18


+: 20,40,10,30,15,35,7,26,18,22,5,42,13,46,27,8,32,38,24,45,25

10 20 30 40

5 7 8 22 24 25 26 27 32 35 3813 15 18 42 45 46


+: 20,40,10,30,15,35,7,26,18,22,5,42,13,46,27,8,32,38,24,45,25

10 20 30 40

5 7 8 22 24 25 26 27 32 35 3813 15 18 42 45 46


+: 20,40,10,30,15,35,7,26,18,22,5,42,13,46,27,8,32,38,24,45,25

10 20 30 40

5 7 8 22 24 25 26 27 32 35 3813 15 18 42 45 46


+: 20,40,10,30,15,35,7,26,18,22,5,42,13,46,27,8,32,38,24,45,25

10 20 25 30 40

5 7 8 22 24 32 35 3813 15 18 42 45 46

26 27


+: 20,40,10,30,15,35,7,26,18,22,5,42,13,46,27,8,32,38,24,45,25

10 20 25 30 40

5 7 8 22 24 32 35 3813 15 18 42 45 46

26 27


+: 20,40,10,30,15,35,7,26,18,22,5,42,13,46,27,8,32,38,24,45,25

10 20 25

5 7 8 22 24 32 35 3813 15 18 42 45 46

26 27

30 40


+: 20,40,10,30,15,35,7,26,18,22,5,42,13,46,27,8,32,38,24,45,25

10 20

5 7 8 22 24 32 35 3813 15 18 42 45 46

26 27

25

30 40


+: 20,40,10,30,15,35,7,26,18,22,5,42,13,46,27,8,32,38,24,45,25

10 20

5 7 8 22 24 32 35 3813 15 18 42 45 46

26 27

25

30 40


Arbres-B

Implantation

• Un B-arbre est une structure de données externe.• On parle de fichier index• Il s’agit d’un fichier binaire (ou structuré)

Les fichiers binaires

Principe

- un fichier est une séquence d'octets non interprétés

Interprétation des données binaires

- à la charge du programmeur - une séquence de n octets peut s'interpréter comme: un entier, un tableau, un enregistrement, ... Les outils

• Déclaration d’un pointeur de fichier• Ouverture et fermeture• Les différents modes d’ouverture• Lecture et écriture• Principe du numéro d’ordre relatif (rrn)• Accès direct..

Les fichiers binaires

#include <fstream>#include <iostream>

//3 classes:ifstream: pour lire dans des fichiersofstream: pour écrire dans des fichiersfstream: pour lire et écrire dans des fichiers

fstream f;f.open("toto.txt", ios::in|ios::out);

mode d'ouverture: ios::in // ouverture en lectureios::out // ouverture en écritureios::app // ajout en fin de fichierios::ate // se position à la finios:: binary // mode binaireios::trunc // tronque le fichier à 0

fstream

Accès direct avec fseek..()

f.seekg (rrn*sizeof(Personne), ios_base::beg)

déplacement par rapport à origine

ios_base::begdébut de f

ios_base::curposition courante

Ios_base::endfin de f

struct Personne {

int age; char nom[40];

};

Personne p; fstream f;…

• Ecriture dans le fichier f.open(nomFich, ios::in|ios::out)f.write (reinterpret_cast<char*>&p, sizeof(Personne));

• Lecture du fichier f.read (reinterpret_cast<char*>&p, sizeof(Personne));

• f.tellg(); //retourne Position courante du pointeur dans le fichier, en nombre d'octets

• Accès direct pour lire ou écrire:

Organisations et modes d’accès des fichiers

Mode d’organisation

Séquentiel Relatif ou direct Séquentiel indexé

Mode d’accès

séquentiel

Mode d’accès direct

Hashing

Mode d’accès séquentiel

Mode d’accès indexé

Arbre-B d’ordre m

Exemple et algorithme d’insertion détaillé (B-arbre d’ordre 3)

I, K, A, Z, M, B, W, L, C, J, O

3 6 8 10 p0 p1 p2 p3 p4

e1 e2 e3 e4

struct BTPAGE{

short keycount; /* Le compteur de clefs. Indique quand le noeud est plein.

*/

struct uneCle key [MAXKEYS]; /* Le tableau des clef. */

short CHILD[MAXKEYS+1]; /* Le tableau qui contiendra les fils pointés */

};

Structure typique d’un arbre-B

/* --------------------------------------------------------*//*

**** Driver.cpp ****

Le "pilote" pour la création et la manipulation d’arbres-B.Crée ou ouvre un fichier arbre-B.

Obtient la clef suivante et appelle la fonction insert pour l'insérer dans l'arbre. Au besoin, driver peut créer une nouvelle racine pour l'arbre.*/

Ajout dans un B-arbre

File StructuresMichael J. Folk and all.

Ajout dans un B-arbre

template <typename T>void BTree:: driver(){ ……

/* ouverture du fichier index*/if btOpen() root = getRoot();else { btfd.open("btree.dat", ios::binary|ios::out|

ios::in);key = getClef(); /*première clé*/root = createRoot(key, NIL, NIL);

}

key = getClef(); /*une clé à insérer*/do{ promoted = insert(root, key, &promoRrn, &promoKey); if (promoted) root = bt.createRoot(promoKey, root,

promoRrn);key = getClef();

} while( /*il y a une clé*/ );

}

/* **** insert.cpp ****

Contient la fonction insert() qui insère une clef dans un arbre-B. S'appelle de manière récursive tant que le bas de l'arbre n'est pas atteint. Alors, insert() insère une clef dans une feuille de l ’arbre. Si le noeud est plein,

- appelle split() pour scinder le noeud- promouvoit la clef du milieu et le rrn du nouveau nœudet essaie d’insérer la clé promue lors de ses remontées

d’appel*//*

insert()Arguments:rrn: Le rrn de la page dans laquelle on fait l'insertion*promoRchild: Le fils promu vers le prochain niveaukey: La clef à être insérée*promoKey: La clef promue vers le prochain niveau

*/

insert (short rrn, T key, short *promoRchild, clef *promoKey){ ….

if (rrn == NIL) { *promoKey = key;

*promoRchild = NIL; return (VRAI);

}btread(rrn, &page);found = searchNode(key, page, &pos);if (found) {

printf("Erreur: clé dupliquée);return (FAUX);

}promoted = insert(page.child[pos], key, &pBrrn, &pBkey);if (!promoted) return (FAUX); if (page.keycount < MAXKEYS)

{insInPage( pBkey, pBrrn, &page); btWrite(rrn, page); return (FAUX);

}else { split( pBkey, pBrrn, &page, promoKey, promoRchild,

&newPage);btwrite(rrn, page);btwrite(*promoRchild, newPage); return (VRAI);

}}

8 15

3 6 9 12 16 20

Arbres-B : recherche

p0 si x < e1

pi si ei < x < ei+1

pm-1 si em-1 < x

3 6 8 10 p0 p1 p2 p3 p4

e1 e2 e3 e4

RECHERCHE (RRN, CL, TROUV_RRN, TROUV_POS)si RRN == NIL alors /* condition d'arrêt de la récursion */

retourner NON TROUVEsinon

lire page RRN dans PAGE regarder à travers la PAGE pour trouver CLmettre POS égale à la position où KEY apparaît ou devrait apparaître. si CL est trouvé alors /* RRN contient la clef */

TROUV_RRN = RRNTROUV_POS = POS retourner TROUVE

sinon /* le FILS suivant fait référence à un niveau plus bas*/return (RECHERCHE(PAGE.FILS[POS], CL, TROUV_RRN, TROUV_POS)finsi

finsi

Recherche dans un arbre-B

/* RRN_FichPrin est le numéro du bloc dans le fichier de données (FichPrin) où se trouve toutes les données de l'enregistrement trouvé. Chaque clé est accompagnée par l'adresse où se trouve la donnée correspondante dans un autre fichier que le fichier index B-Arbre.*/

template <typename T>bool BTree::searchBTree(int rrn, T key, int *trouvRRN, short *trouvPos) { short pos; Bool found; BTPAGE page;

if (rrn == NIL) { return FAUX; } else { btread(rrn,&page); /*lecture d'un noeud (une page) dans le fichier B-Arbre*/ found = searchNode(key, page, &pos); /*recherche dans la page lue */ if (found) { *trouvRRN = page.key[pos].RRN_FichPrin; return VRAI; } else { return(search(page.child[pos],key,trouvRRN,trouvPos)); }

} }

3 6 8 10

Visite d’un arbre-B

visite symétrique du B-arbre pour afficher les clés triées,rrn est l'adresse de la page racine du B-arbre.

Cette fonction retourne un flag pour contrôler son exécutionBTPAGE est la structure typique du B-arbre:

struct BTPAGE {

short keycount;struct uneCle key [MAXKEYS];short CHILD[MAXKEYS+1];

};

template <typename T>int BTree:: visiteSymetriqueB_Arbre(short rrn) {

BTPAGE page;

if (rrn == NIL){

return (-1); //arbre vide}

btRead(rrn, &page);

for(short pos = 0; pos < page.keycount; pos++){

//appel récursif pour chaque sous-arbresvisiteSymetriqueB_Arbre(page.child[pos]);cout << page.key[pos].nom;

}

//dernier appel récursif pour le sous-arbrequi se trouve à droite de la dernière clé

visiteSymetriqueB_Arbre(page.child[pos]);

return 0;}

Enlèvement dans un arbre-B

-: 25,24,22,20

10 20

5 7 8 22 24 32 35 3813 15 18 42 45 46

26 27

25

30 40

-: 25,24,22,20

10 20

5 7 8 22 24 32 35 3813 15 18 42 45 46

26 27

25

30 40

x


-: 25,24,22,20

10 20

5 7 8 22 24 32 35 3813 15 18 42 45 46

26 27

25

30 40

x


-: 25,24,22,20

10 20

5 7 8 22 32 35 3813 15 18 42 45 46

26 27

24

30 40


-: 25,24,22,20

10 20

5 7 8 22 32 35 3813 15 18 42 45 46

26 27

24

30 40



-: 25,24,22,20

10 20

5 7 8 22 32 35 3813 15 18 42 45 46

26 27

24

30 40

x


-: 25,24,22,20

10 20

5 7 8 22 32 35 3813 15 18 42 45 46

26 27

24

30 40

x

-: 25,24,22,20

10 20

5 7 8 32 35 3813 15 18 42 45 46

26 27

22

30 40


-: 25,24,22,20

10 20

5 7 8 32 35 3813 15 18 42 45 46

26 27

22

30 40



-: 25,24,22,20

10 18

5 7 8 32 35 3813 15 42 45 46

26 27

22

30 40

20


-: 25,24,22,20

10 18

5 7 8 32 35 3813 15 42 45 46

26 27

22

30 40

20

x

-: 25,24,22,20

10 18

5 7 8 32 35 3813 15 42 45 46

26 27

22

30 40

20

x



-: 25,24,22,20

10 18

5 7 8 32 35 3813 15 42 45 46

26 27

20

30 40

-: 25,24,22,20

10 18

5 7 8 32 35 3813 15 42 45 46

26 27

20

30 40


18

-: 25,24,22,20

10 15

5 7 8 32 35 3813 42 45 46

26 27

20

30 40


18

-: 25,24,22,20

10 15

5 7 8 32 35 3813 42 45 46

26 27

20

30 40

x


18

-: 25,24,22,20

10 15

5 7 8 32 35 3813 42 45 46

26 27

20

30 40

x


-: 25,24,22,20

10 15

5 7 8 32 35 3813 42 45 46

26 27

18

30 40



-: 25,24,22,20

10 15

5 7 8 32 35 3813 42 45 46

26 27

18

30 40


-: 25,24,22,20

10

5 7 8 32 35 3813 15 42 45 46

26 27

18

30 40

-: 25,24,22,20

10

5 7 8 32 35 3813 15 42 45 46

26 27

18

30 40


-: 25,24,22,20

10

5 7 8 32 35 3813 15 42 45 46

26 27

18

30 40


-: 25,24,22,20

10 18

5 7 8 32 35 3813 15 42 45 46

26 27

30 40


-: 25,24,22,20

10 18

5 7 8 32 35 3813 15 42 45 46

26 27

30 40 +


-: 25,24,22,20

10 18 30 40

5 7 8 32 35 3813 15 42 45 46

26 27


1. Si la clé à supprimer ne se trouve pas dans une feuille, la remplacer par son prédécesseur ou successeur se trouvant dans une feuille.

2. Supprimer la clé. 3. Si la feuille a le nombre requis de clés, ne rien faire.4. Si la feuille contient moins de clés que requis, regarder à sa droite et à sa gauche

pour trouver la cible.1. Si la cible a le nombre requis de clés, redistribution2. Si la cible n’a pas le nombre requis de clés, concaténation

5. Si la feuille a subi la concaténation, appliquer 3. à 6. au père de cette feuille.6. Si la dernière clé de la racine a été déplacée, mettez à jour la racine.

Algorithme


Utilisation d’arbres-B

• + indirection vers les données

10 20

5 7 8 22 24 32 35 3813 15 18 42 45 46

26 27

25

30 40

Arbres-B d’ordre m

Désavantages :• gestion plus complexe

• 2 types de structures à gérer pour chaque opération• espace perdu

• les nœuds (tableaux) contiennent de l’espace inutilisé• quel impact a le choix de m :

• sur le temps de recherche d’une information ?• sur le temps d’ajout d’une information ?• sur le temps de traitement d’intervalles ?

• comment choisir m ?

Arbres-B d’ordre m

Désavantages :• gestion plus complexe

• 2 types de structures à gérer pour chaque opération• espace perdu

• les nœuds (tableaux) contiennent de l’espace inutilisé• quel impact a le choix de m :

• sur le temps de recherche d’une information ?• sur le temps d’ajout d’une information ?• sur le temps de traitement d’intervalles ?

• comment choisir m ?• souvent selon la taille des secteurs disque• selon les caractéristiques et besoins de l’application

Les arbres-B+

Définitions:• c ’est un B-arbre• + duplications des clés• + chaînage de toutes les feuilles

Insérer 65

65

Exemple

Construction d’un arbre-B+

Insérer 25

25 65

Insérer 50

25 50 65

Insérer 30

25 30 50 65

Insérer 85

85

85

25 30 50 65

25 30 50 65

50

25 30 50 65 85

Insérer 75

50

25 30 50 65 75 85

Insérer 80 50

25 30 50 65 7585

80

50

25 30 50 65 75 80 85

50

25 30 50 65 75 80 85

50 75

25 30 50 65 75 80 85

Suppression

60

25 50 7585

50 55 75 805 10 15

25 28 30 60 65 70

85 90 95

Supprimer 70 (Cas 1)

60

25 50 7585

50 55 75 805 10 15 20

25 28 30 60 65 70

85 90 95 Sans violation70 n’appartient pas à une page interne

Suppression

60

25 50 7585

50 55 75 805 10 15 20

25 28 30 60 65

85 90 95

Suppression

Supprimer 25 (Cas 1)

60

25 50 7585

50 55 75 805 10 15 20

25 28 30 60 65

85 90 95 Sans violation

25 appartient à une page interne

60

28 50 7585

50 55 75 805 10 15 20

28 30 60 65

85 90 95

Suppression

Supprimer 60 (Cas 2 et 3)

60

28 50 7585

50 55 75 805 10 15 20

28 30 60 65

85 90 95 Violation


60

28 50 7585

50 55 75 805 10 15 20

28 30 60 65

85 90 95 Fusionner


60

28 50 7585

50 55 75 805 10 15 20

28 30 60 65

85 90 95

On peut fusionner avec l’autre frère

Cas 2 Fusion


65

28 50 7585

50 55 5 10 15 20

28 30

65 75 80

85 90 95


65

28 50 85

50 55 5 10 15 20

28 30

65 75 80

85 90 95

Violation


65

28 50 85

50 55 5 10 15 20

28 30

65 75 80

85 90 95

Fusionner


65

28 50 85

50 55 5 10 15 20

28 30

65 75 80

85 90 95

Fusionner


2850 65 85

50 55 5 10 15 20

28 30

65 75 80

85 90 95

Site Web du Cours, semaine 12

Lecture complémentaires :

• Une synthèse sur les arbres AVL ainsi que sur les B-arbre et B-arbre+. • Une trace des algorithmes d'ajout et de suppression dans un B-arbre. • La même chose en ce qui concerne les B-arbre+.

http://www.ift.ulaval.ca/ift%2D10541/Semainier/Semaine12/B-arbre.pdf

http://www.ift.ulaval.ca/ift%2D10541/Semainier/Semaine12/FichIndBArbre.ppt

http://www.ift.ulaval.ca/ift%2D10541/Semainier/Semaine12/FichIndBArbrePlus.ppt

Documents

Structures de données IFT-2000 Abder Alikacem Semaine 11, 1 ère partie Les B-arbres Département dinformatique et de génie logiciel Édition septembre 2009