AccueilđŸ‡«đŸ‡·Chercher

Arbre B

En informatique, un arbre B (appelĂ© aussi B-arbre par analogie au terme anglais « B-tree ») est une structure de donnĂ©es en arbre Ă©quilibrĂ©. Les arbres B sont principalement mis en Ɠuvre dans les mĂ©canismes de gestion de bases de donnĂ©es et de systĂšmes de fichiers. Ils stockent les donnĂ©es sous une forme triĂ©e et permettent une exĂ©cution des opĂ©rations d'insertion et de suppression en temps toujours logarithmique.

Arbre B
Exemple d'un 3-5 B-arbre
DĂ©couvreurs ou inventeurs
Date de découverte
ProblÚme lié
Structure des données
Complexité en temps
Pire cas
, ,
Moyenne
, ,
Complexité en espace
Pire cas
Moyenne

Le principe est de permettre aux nƓuds parents de possĂ©der plus de deux nƓuds enfants : c'est une gĂ©nĂ©ralisation de l’arbre binaire de recherche. Ce principe minimise la taille de l'arbre et rĂ©duit le nombre d'opĂ©rations d'Ă©quilibrage. De plus un arbre B grandit Ă  partir de la racine, contrairement Ă  un arbre binaire de recherche qui croĂźt Ă  partir des feuilles.

Le créateur des arbres B, Rudolf Bayer, n'a pas explicité la signification du « B ». L'explication la plus fréquente est que le B correspond au terme anglais « balanced » (en français : « équilibré »). Cependant, il pourrait aussi découler de « Bayer », du nom du créateur, ou de « Boeing », du nom de la firme pour laquelle le créateur travaillait (Boeing Scientific Research Labs).

Origine

Les arbres B ont Ă©tĂ© inventĂ©s en 1970 par Rudolf Bayer et Edward M.McCreight dans les laboratoires de recherche de Boeing. Le but Ă©tait de pouvoir gĂ©rer les pages d'index de fichiers de donnĂ©es, en tenant compte du fait que le volume des index pouvait ĂȘtre si grand que seule une fraction des pages pouvait ĂȘtre chargĂ©e en mĂ©moire vive. Le premier article[2] dĂ©crivant le mĂ©canisme des arbres B a Ă©tĂ© Ă©crit en juillet et publiĂ© en .

Structure

Structure générale

Un arbre Ă©tiquetĂ© est un arbre (au sens informatique du terme) tel qu'Ă  chaque nƓud on associe une Ă©tiquette ou clĂ© (ou bien plusieurs Ă©tiquettes ou clĂ©s dans le cas des arbres B) prise(s) dans un ensemble donnĂ©. Donc formellement un arbre Ă©tiquetĂ© est un couple formĂ© d'un graphe orientĂ©, acyclique et connexe et d'une fonction d'Ă©tiquetage des arbres qui attribue Ă  chaque nƓud une Ă©tiquette ou une clĂ©. Parmi les arbres Ă©tiquetĂ©s, un arbre B possĂšde quelques propriĂ©tĂ©s spĂ©cifiques supplĂ©mentaires.

Soient L et U deux entiers naturels non nuls tels que L ≀ U. En toute gĂ©nĂ©ralitĂ©, on dĂ©finit alors un L-U arbre B[3] de la maniĂšre suivante : chaque nƓud, sauf la racine, possĂšde un minimum de L−1 clĂ©s (appelĂ©es aussi Ă©lĂ©ments), un maximum de U−1 clĂ©s et au plus U fils[4]. Pour chaque nƓud interne — nƓud qui n’est pas une feuille —, le nombre de fils est toujours Ă©gal au nombre de clĂ©s augmentĂ© d’une unitĂ©. Si n est le nombre de fils, alors on parle de n-nƓud. Un L-U arbre ne contient que des n-nƓuds avec L ≀ n ≀ U. Souvent on choisit la configuration L = t et U = 2 × t : t est appelĂ© le degrĂ© minimal de l’arbre B.

De plus, la construction des arbres B garantit qu’un arbre B est toujours Ă©quilibrĂ©. Chaque clĂ© d’un nƓud interne est en fait une borne qui distingue les sous-arbres de ce nƓud. Par exemple, si un nƓud a 3 fils — lesquels constituent les racines respectives de trois sous-arbres : sous-arbre gauche, sous-arbre du milieu et sous-arbre droit —, alors il a 2 clĂ©s notĂ©es c1 et c2 qui dĂ©limitent les clĂ©s de chaque sous-arbre : les clĂ©s du sous-arbre gauche seront infĂ©rieures Ă  c1 ; les clĂ©s du sous-arbre du milieu seront comprises entre c1 et c2 ; les clĂ©s du sous-arbre droit seront supĂ©rieures Ă  c2.

Implémentation

Un arbre B est implĂ©mentĂ© par un arbre enracinĂ©[5]. Un nƓud est Ă©tiquetĂ© par :

  • Un entier qui correspond au nombre de clefs contenues dans le nƓud .
  • clefs notĂ©es .
  • Un boolĂ©en indiquant si est une feuille ou non.
  • pointeurs notĂ©s associĂ©s aux fils de . Une feuille ne contient pas de pointeurs.

De plus, un arbre B vérifie ces propriétés :

  • Toutes les feuilles ont la mĂȘme profondeur, Ă  savoir la hauteur de l’arbre.
  • Si n’est pas une feuille :
    • Pour , pour toute clef du fils : .
    • pour toute clef du fils : .
    • pour toute clef du fils : .
  • Si n’est ni une feuille, ni la racine, est compris entre L-1 et U-1.

Exemple de nƓud en C++

template<typename T, size_t U>
struct Noeud {
    size_t n;           // nombre de clés utilisées
    bool feuille;       // si ce nƓud est une feuille
    Noeud<T, U>* parent = nullptr;  // connaĂźtre le parent peut ĂȘtre nĂ©cessaire dans certains algorithmes
    T cles[U-1];          // tableau des clés
    Noeud<T, U>* branches[U];   // tableau des branches, si ce n'est pas une feuille
};

En pratique

La plupart du temps, la configuration est telle que U = 2 L. On parle alors d’arbre B d'ordre L.

Un arbre B d’ordre t est alors dĂ©fini plus simplement par un arbre qui satisfait les propriĂ©tĂ©s suivantes :

  1. Chaque nƓud a au plus clĂ©s.
  2. Chaque nƓud qui n’est ni racine ni feuille possĂšde au moins clĂ©s.
  3. Si l'arbre est non vide, la racine est aussi non vide.
  4. Un nƓud qui possùde k fils contient k − 1 clefs.
  5. Toutes les feuilles se situent Ă  la mĂȘme hauteur.

Opérations

Comme on le verra par la suite, la hauteur d'un B-arbre est logarithmique en le nombre d'Ă©lĂ©ments. Ainsi, les opĂ©rations de recherche, insertion et suppression sont implĂ©mentables en O(log n) dans le pire cas, oĂč n est le nombre d'Ă©lĂ©ments.

Recherche

La recherche est effectuĂ©e de la mĂȘme maniĂšre que dans un arbre binaire de recherche. Partant de la racine, on parcourt rĂ©cursivement l’arbre ; Ă  chaque nƓud, on choisit le sous-arbre fils dont les clĂ©s sont comprises entre les mĂȘmes bornes que celles de la clĂ© recherchĂ©e grĂące Ă  une recherche dichotomique.

Pseudo-code

fonction Rechercher(noeud, x):
    i = 0
    tant que i < noeud.taille et x > noeud.cles[i]:
        i += 1
    si noeud.feuille:
        retourner i < noeud.taille et x == noeud.cles[i]
    sinon:
        si i < noeud.taille et x == noeud.cles[i]:
            retourner Vrai
        sinon:
            retourner Rechercher(noeud.branches[i], x)

Dans de nombreuses implĂ©mentations, l'Ă©galitĂ© () entre Ă©lĂ©ments est remplacĂ©e par l'Ă©quivalence (). Il faut donc veiller Ă  utiliser des types de donnĂ©es oĂč deux Ă©lĂ©ments Ă©quivalents sont considĂ©rĂ©s comme Ă©gaux.

Insertion

L’insertion nĂ©cessite tout d’abord de chercher le nƓud oĂč la nouvelle clĂ© devrait ĂȘtre insĂ©rĂ©e, et l’insĂ©rer. La suite se dĂ©roule rĂ©cursivement, selon qu’un nƓud ait ou non trop de clĂ©s : s’il possĂšde un nombre acceptable de clĂ©s, on ne fait rien ; autrement on le transforme en deux nƓuds, chacun possĂ©dant un nombre minimum de clĂ©s, puis on fait « remonter » la clĂ© du milieu qui est alors insĂ©rĂ©e dans le nƓud pĂšre. Ce dernier peut du coup se retrouver avec un nombre excessif de fils ; le procĂ©dĂ© se poursuit ainsi jusqu’à ce que l’on atteigne la racine. Si celle-ci doit ĂȘtre divisĂ©e, on fait « remonter » la clĂ© du milieu dans une nouvelle racine, laquelle gĂ©nĂšrera comme nƓuds fils les deux nƓuds crĂ©Ă©s Ă  partir de l’ancienne racine, Ă  l’instar de l'Ă©tape prĂ©cĂ©dente. Pour que l’opĂ©ration soit possible, on remarque qu’il faut que U ≄ 2 L ; sinon les nouveaux nƓuds ne possĂšderont pas suffisamment de clĂ©s.

Une variante consiste Ă  Ă©clater prĂ©ventivement chaque nƓud « plein » (possĂ©dant le nombre maximal de clĂ©s) rencontrĂ© lors de la recherche du nƓud oĂč se rĂ©alisera l'insertion. De cette maniĂšre on Ă©vite une remontĂ©e dans l'arbre, puisque l'on assure que le pĂšre d'un nƓud Ă  scinder en deux peut accueillir une clĂ© supplĂ©mentaire. La contrepartie en est une lĂ©gĂšre augmentation de la hauteur moyenne de l'arbre.

Pseudo-code

fonction Inserer(x,c)
    n = nombre de clefs du noeud x
    Soit i tel que x.clef[i] > c ou i >= n
    Si x est une feuille :
        Inserer c dans x.clef a la i-ieme place
    Sinon:
        Si x.fils[i] est complet:
            Scinder x.fils[i]
            Si c > x.clef[i]:
                i := i+1
            FinSi
        FinSi
        Inserer(x.fils[i],c)
    FinSi
FinFonction

Suppression

On doit d’abord chercher la clĂ© Ă  supprimer et la supprimer du nƓud qui la contient.

  • Si le nƓud est interne, on procĂšde de maniĂšre similaire aux arbres binaires de recherche en recherchant la clĂ© k la plus Ă  gauche dans le sous-arbre droit de la clĂ© Ă  supprimer ou la plus Ă  droite dans le sous-arbre gauche. Cette clĂ© k appartient Ă  une feuille. On peut la permuter avec la clĂ© Ă  supprimer, que l’on supprime ensuite. Comme elle appartient Ă  une feuille, on se ramĂšne au cas suivant.
  • Si le nƓud est une feuille, soit il possĂšde encore suffisamment de clĂ©s et l’algorithme termine, soit il dispose de moins de L−1 clĂ©s et on se trouve dans l’une des deux situations suivantes :
    • soit un de ses frĂšres Ă  droite ou Ă  gauche possĂšde suffisamment de clĂ©s pour pouvoir en « passer » une Ă  la feuille en question : dans ce cas cette clĂ© remplace la clĂ© qui sĂ©pare les deux sous-arbres dans l’arbre pĂšre, qui va elle-mĂȘme dans la feuille en question ;
    • soit aucun de ses frĂšres n’a suffisamment de clĂ©s : dans ce cas, le pĂšre fait passer une de ses clĂ©s dans un des deux (ou le seul) frĂšres pour permettre Ă  la feuille de fusionner avec celui-ci. Ceci peut cependant conduire le pĂšre Ă  ne plus avoir suffisamment de clĂ©s. On rĂ©itĂšre alors l’algorithme : si le nƓud a un frĂšre avec suffisamment de clĂ©s, la clĂ© la plus proche va ĂȘtre Ă©changĂ©e avec la clĂ© du pĂšre, puis la clĂ© du pĂšre et ses nouveaux descendants sont ramenĂ©s dans le nƓud qui a besoin d’une clĂ© ; sinon on effectue une fusion Ă  l’aide d’une clĂ© du pĂšre et ainsi de suite. Si l’on arrive Ă  la racine et qu’elle possĂšde moins de L Ă©lĂ©ments, on fusionne ses deux fils pour donner une nouvelle racine.

Équilibrage

Notamment aprĂšs une suppression, l'arbre peut ĂȘtre rĂ©Ă©quilibrĂ©. Cette opĂ©ration consiste Ă  rĂ©partir Ă©quitablement les valeurs dans les diffĂ©rents nƓuds de l'arbre et Ă  rĂ©tablir les propriĂ©tĂ©s de remplissage minimum des nƓuds.

Le rĂ©Ă©quilibrage commence au niveau des feuilles et progresse vers la racine, jusqu'Ă  celle-ci. La redistribution consiste Ă  transfĂ©rer un Ă©lĂ©ment d'un nƓud voisin qui possĂšde suffisamment de valeurs vers le nƓud qui en manque. Cette redistribution est appelĂ©e rotation. Si aucun voisin ne peut fournir de valeur sans ĂȘtre lui mĂȘme sous la limite, le nƓud dĂ©ficient doit ĂȘtre fusionnĂ© avec un voisin. Cette opĂ©ration provoque la perte d'un sĂ©parateur dans le nƓud parent, celui-ci peut alors ĂȘtre en dĂ©ficit et a besoin d'ĂȘtre Ă©quilibrĂ©. La fusion et redistribution se propage jusqu'Ă  la racine, seul Ă©lĂ©ment oĂč la dĂ©ficience en valeurs est tolĂ©rĂ©e.

Un algorithme d'Ă©quilibrage simple consiste Ă :

  • Si le nƓud voisin gauche existe et dispose de suffisamment de valeurs pour pouvoir en offrir une, rĂ©aliser une rotation gauche.
  • Sinon, si le nƓud voisin droite existe et dispose de suffisamment d'Ă©lĂ©ments, rĂ©aliser une rotation droite.
  • Sinon, le nƓud dĂ©ficient doit ĂȘtre fusionnĂ© avec un de ses voisins tel que la somme du nombre de leurs clĂ©s plus 1 soit infĂ©rieure ou Ă©gale Ă  la capacitĂ© maximale (). La valeur supplĂ©mentaire correspond au sĂ©parateur prĂ©sent dans le parent. Cette opĂ©ration est toujours possible si avec et ou le contraire, soit un nƓud immĂ©diatement sous la limite de clĂ©s et un nƓud exactement Ă  la limite.
    1. copier le sĂ©parateur Ă  la fin du nƓud de gauche
    2. ajouter tous les Ă©lĂ©ments du nƓud de droite Ă  la fin du nƓud de gauche
    3. effacer le nƓud de droite et effacer le sĂ©parateur du parent puis vĂ©rifier qu'il contient assez d'Ă©lĂ©ments. Si ce n'est pas le cas, rĂ©Ă©quilibrer le parent avec ses voisins.

Rotation gauche

La rotation à gauche d'un cran entre deux nƓuds voisins se fait en

  1. dĂ©plaçant le sĂ©parateur, prĂ©sent dans le parent, Ă  la fin du nƓud de gauche
  2. dĂ©plaçant le premier Ă©lĂ©ment du nƓud de droite en tant que sĂ©parateur dans le parent

Ce genre d'opĂ©ration peut ĂȘtre Ă©galement utilisĂ© pour compresser l'arbre: un arbre destinĂ© Ă  la lecture seule peut ĂȘtre vidĂ© d'un maximum de cases mĂ©moires inutilisĂ©es en remplissant au maximum un minimum de nƓuds.

Hauteur dans le pire des cas

Soit le nombre de clefs que contient l’arbre B. La hauteur de l’arbre vĂ©rifie l’inĂ©galitĂ© :

Remarques

  • Les arbres 2-3-4 sont les structures de donnĂ©es d’arbre B les plus utilisĂ©es : ils correspondent en fait Ă  des 2-4 arbres B ou arbres B d’ordre 2.
  • Les B-arbres prĂ©sentent l'avantage d'ĂȘtre Ă©quilibrĂ©s (toutes les feuilles sont Ă  la mĂȘme hauteur), ce qui permet d'obtenir une majoration de la hauteur et donc de meilleures complexitĂ©s (en O(log n)) pour les opĂ©rations de base (recherche, insertion, suppression) que pour un arbre classique (oĂč l'insertion est en O(h), avec h la hauteur de l'arbre, donc potentiellement en O(n) suivant l'implĂ©mentation choisie).

Variantes

L’arbre Arbre B+ (en) diffĂšre lĂ©gĂšrement de l’arbre B, en ceci que toutes les donnĂ©es sont stockĂ©es exclusivement dans des feuilles, et celles-ci sont reliĂ©es entre elles.

D’autres variantes existent Ă©galement, telles que l’arbre B* (en).

Annexes

Références

  1. R. Bayer et E. McCreight, « Organization and maintenance of large ordered indices », SIGFIDET '70: Proceedings of the 1970 ACM SIGFIDET (now SIGMOD) Workshop on Data Description, Access and Control, ACM,‎ , p. 107-141 (ISBN 978-1-4503-7941-0, DOI 10.1145/1734663.1734671)
  2. (en) R. Bayer et E. McCreight, « Organization and maintenance of large ordered indices », Proceedings of the 1970 ACM SIGFIDET (now SIGMOD) Workshop on Data Description, Access and Control - SIGFIDET '70, ACM Press,‎ , p. 107 (DOI 10.1145/1734663.1734671, lire en ligne, consultĂ© le )
  3. L-U arbre B doit se lire « L U arbre B », car L-U représente une expression composée, et non pas la soustraction de deux nombres.
  4. « L−1 » et « U−1 » figurent ici des expressions de soustraction.
  5. (en) Thomas H.Cormen, Introduction to algorithms, 1989, pp.485-504.

Voir aussi

Liens externes

  • (en) cs.usfca.edu : animation permettant d'insĂ©rer et de supprimer visuellement des Ă©lĂ©ments dans un arbre B
  • (it) (en) B-tree GUI : Spataro Fabrizio e Todaro Michelangelo – Emulatore Java BTree – BTree Java Emulator.
  • (en) Slady.net : animation sous forme d’applet Java permettant de construire visuellement des arbres B.
Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplĂ©mentaires peuvent s’appliquer aux fichiers multimĂ©dias.