Structures de données IFT-2000 Abder Alikacem Semaine 12 (2 ième partie) Les B-arbres Département...

Structures de donnéesIFT-2000

Abder AlikacemAbder Alikacem

Semaine 12 (2ième partie)

Les B-arbres

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

Édition septembre 2009

! +

Plan

Les arbres BDéfinitionNotions de structures de données externesOpérations d’ajout Opérations d’enlèvement

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)

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 binaireNœud typique & en-tête du fichier index (B-arbre)La mécanique de la construction d’un B-ArbreLa 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

Ajout dans un arbre-B d’ordre 5

20 40

+: 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

10 20 40

+: 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,40,10,30,15,35,7,26,18,22,5,42,13,46,27,8,32,38,24,45,25

10 20 30 40

Ajout dans un arbre-B d’ordre 5

+: 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

Ajout dans un arbre-B d’ordre 5

+: 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

Ajout dans un arbre-B d’ordre 5

+: 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   

Ajout dans un arbre-B d’ordre 5

+: 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   

Ajout dans un arbre-B d’ordre 5

+: 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   

Ajout dans un arbre-B d’ordre 5

+: 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   

Ajout dans un arbre-B d’ordre 5

+: 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   

Ajout dans un arbre-B d’ordre 5

+: 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   

Ajout dans un arbre-B d’ordre 5

+: 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   

Ajout dans un arbre-B d’ordre 5

+: 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  

Ajout dans un arbre-B d’ordre 5

+: 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  

Ajout dans un arbre-B d’ordre 5

+: 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  

Ajout dans un arbre-B d’ordre 5

+: 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  

Ajout dans un arbre-B d’ordre 5

+: 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  

Ajout dans un arbre-B d’ordre 5

+: 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  

Ajout dans un arbre-B d’ordre 5

+: 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  

Ajout dans un arbre-B d’ordre 5

+: 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  

Ajout dans un arbre-B d’ordre 5

+: 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  

Ajout dans un arbre-B d’ordre 5

+: 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  

Ajout dans un arbre-B d’ordre 5

+: 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  

Ajout dans un arbre-B d’ordre 5

+: 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  

Ajout dans un arbre-B d’ordre 5

+: 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  

Ajout dans un arbre-B d’ordre 5

+: 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  

Ajout dans un arbre-B d’ordre 5

+: 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  

Ajout dans un arbre-B d’ordre 5

+: 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   

Ajout dans un arbre-B d’ordre 5

+: 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   

Ajout dans un arbre-B d’ordre 5

+: 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   

Ajout dans un arbre-B d’ordre 5

+: 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  

Ajout dans un arbre-B d’ordre 5

+: 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  

Ajout dans un arbre-B d’ordre 5

+: 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   

Ajout dans un arbre-B d’ordre 5

+: 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   

Ajout dans un arbre-B d’ordre 5

+: 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   

Ajout dans un arbre-B d’ordre 5

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::binary|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::binary|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:

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 méthode 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

*/

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

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

*promoRchild = NIL; return (true);

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

std::cout<<"Erreur: clé dupliquée";return (false);

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

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

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

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

}}

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

/* 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 false; } 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 true; } 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

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   

x

Enlèvement dans un arbre-B

-: 25,24,22,20

10 20   

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

26 27  

24

30 40   

Enlèvement dans un arbre-B

-: 25,24,22,20

10 20   

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

26 27  

24

30 40   

Enlèvement dans un arbre-B

Enlèvement dans un arbre-B

-: 25,24,22,20

10 20   

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

26 27  

24

30 40   

x

Enlèvement dans un arbre-B

-: 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   

Enlèvement dans un arbre-B

-: 25,24,22,20

10 20   

5 7 8 32 35 3813 15 18   42 45 46   

26 27  

22

30 40   

Enlèvement dans un arbre-B

Enlèvement dans un arbre-B

-: 25,24,22,20

10 18   

5 7 8 32 35 3813 15   42 45 46   

26 27  

22

30 40   

20

Enlèvement dans un arbre-B

-: 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

Enlèvement dans un arbre-B

Enlèvement dans un arbre-B

-: 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   

Enlèvement dans un arbre-B

18

-: 25,24,22,20

10 15   

5 7 8 32 35 3813   42 45 46   

26 27  

20

30 40   

Enlèvement dans un arbre-B

18

-: 25,24,22,20

10 15   

5 7 8 32 35 3813   42 45 46   

26 27  

20

30 40   

x

Enlèvement dans un arbre-B

18

-: 25,24,22,20

10 15   

5 7 8 32 35 3813   42 45 46   

26 27  

20

30 40   

x

Enlèvement dans un arbre-B

-: 25,24,22,20

10 15   

5 7 8 32 35 3813   42 45 46   

26 27  

18

30 40   

Enlèvement dans un arbre-B

Enlèvement dans un arbre-B

-: 25,24,22,20

10 15   

5 7 8 32 35 3813   42 45 46   

26 27  

18

30 40   

Enlèvement dans un arbre-B

-: 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   

Enlèvement dans un arbre-B

-: 25,24,22,20

10   

5 7 8 32 35 3813 15   42 45 46   

26 27  

18

30 40   

Enlèvement dans un arbre-B

-: 25,24,22,20

10 18   

5 7 8 32 35 3813 15   42 45 46   

26 27  

30 40   

Enlèvement dans un arbre-B

-: 25,24,22,20

10 18   

5 7 8 32 35 3813 15   42 45 46   

26 27  

30 40   +

Enlèvement dans un arbre-B

-: 25,24,22,20

10 18 30 40   

5 7 8 32 35 3813 15   42 45 46   

26 27  

Enlèvement dans un arbre-B

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

Enlèvement dans un arbre-B

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