Arbre B

Arbre B

Exemple d'un 3-5 B-arbre

Découvreurs ou inventeurs	Rudolf Bayer,Edward M. McCreight
Date de découverte	1972
Problème lié	Structure de données
Structure des données	Arbre enraciné

Complexité en temps

Pire cas	$O(\log n)(insertion)$,$O(\log n)(suppression)$,$O(\log n)(recherche)$
Moyenne	$O(\log n)$,$O(\log n)$,$O(\log n)$

Complexité en espace

Pire cas	$O(n)$
Moyenne	$O(n)$

Eninformatique,unarbre B(appelé aussiB-arbrepar analogie au termeanglais«B-tree») est unestructure de donnéesenarbre équilibré.Les arbres B sont principalement mis en œuvre dans les mécanismes de gestion debases de donnéeset desystè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 toujourslogarithmique.

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 à unarbre binaire de recherchequi 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 leBcorrespond 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 parRudolf BayeretEdward M.McCreightdans les laboratoires de recherche deBoeing.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 enmémoire vive.Le premier articledécrivant le mécanisme des arbres B a été écrit en juillet et publié ennovembre 1970.

Structure

Structure générale

Unarbre étiquetéest unarbre(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 faiblement connexe et d'une fonction d'étiquetage des arbres qui attribue à chaque nœud une étiquette ou une clé. Parmi les arbres étiquetés, unarbre Bpos sắc 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 unL-U arbre Bde la manière suivante: chaque nœud, sauf la racine, pos sắc de unminimumde L−1 clés (appelées aussi éléments), unmaximumde U−1 clés et au plus U fils.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é. Sinest le nombre de fils, alors on parle den-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é ledegré minimalde 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éesc₁etc₂qui délimitent les clés de chaque sous-arbre: les clés du sous-arbre gauche seront inférieures àc₁;les clés du sous-arbre du milieu seront comprises entrec₁etc₂;les clés du sous-arbre droit seront supérieures àc₂.

Implémentation

Un arbre B est implémenté par un arbre enraciné. Un nœud$x$est étiqueté par:

• Un entier$n$qui correspond au nombre de clefs contenues dans le nœud$x$.
• $n$clefs notées$c_{1},\ldots,c_{n}$.
• Un booléen indiquant si$x$est une feuille ou non.
• $n+1$pointeurs notés$p_{1},\ldots,p_{n+1}$associés aux fils$f_{1},\ldots,f_{n+1}$de$x$.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$h$de l’arbre.
• Si$x$n’est pas une feuille:
  • Pour$2\leq i\leq n$,pour toute clef$k$du fils$f_{i}$:$c_{i-1}\leq k\leq c_{i}$.
  • pour toute clef$k$du fils$f_{1}$:$k\leq c_{1}$.
  • pour toute clef$k$du fils$f_{n+1}$:$c_{n}\leq k$.
• Si$x$n’est ni une feuille, ni la racine,$n$est compris entre L-1 et U-1.

Exemple de nœud enC++

template<typenameT,size_tU>
structNoeud{
size_tn;// nombre de clés utilisées
boolfeuille;// si ce nœud est une feuille
Noeud<T,U>*parent=nullptr;// connaître le parent peut être nécessaire dans certains algorithmes
Tcles[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’ordretest alors défini plus simplement par un arbre qui satisfait les propriétés suivantes:

1. Chaque nœud a au plus$2t-1$clés.
2. Chaque nœud qui n’est ni racine ni feuille pos sắc de au moins$t-1$clés.
3. Si l'arbre est non vide, la racine est aussi non vide.
4. Un nœud qui pos sắc dekfils contientk− 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 enO(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 unarbre binaire de recherche.Partant de la racine, on parcourtrécursivementl’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 à unerecherche 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é ($a==b$) entre éléments est remplacée par l'équivalence ($\neg (a<b)\wedge \neg (b<a)$). Il faut donc veiller à utiliser destypes de donnéesoù 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 pos sắc 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 pos sắc 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 auxarbres binaires de rechercheen 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 pos sắc 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 pos sắc 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 pos sắc 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 pos sắc de suffisamment de valeurs vers le nœud qui en manque. Cette redistribution est appeléerotation.Si aucun voisin ne peut fournir de valeur sans être lui même sous la limite, le nœud déficient doit êtrefusionné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 ($taille_{gauche}+taille_{droite}+1\leq U-1$). La valeur supplémentaire correspond au séparateur présent dans le parent. Cette opération est toujours possible si$U-1\geq 2\times L$avec$taille_{gauche}=L-2$et$taille_{droite}=L-1$ou le contraire, soit un nœud immédiatement sous la limite de$L-1$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$N$le nombre de clefs que contient l’arbre B. La hauteur$h$de l’arbre vérifie l’inégalité:

$h\leq \log _{L}\left({\frac {N+1}{2}}\right)$

Démonstration

La racine de l’arbre contient au moins 1 nœud, elle pos sắc de donc au moins 2 fils. Les nœuds de profondeur au moins 1 contiennent au minimum L-1 clefs et L fils. Par récurrence, pour$1\leq i\leq h$,on montre que le niveau$i$de l’arbre, c’est-à-dire l’ensemble des nœuds de profondeur$i$,contient au moins$2L^{i-1}$nœuds et donc au moins$2L^{i-1}(L-1)$clefs. Par conséquent, le nombre total de clefs dans l’arbre vérifie:

$N\geq 1+\sum _{i=0}^{h-1}2L^{i}(L-1)=1+2(L-1){\frac {L^{h}-1}{L-1}}=2L^{h}-1$

Donc$N+1\geq 2L^{h}$et$h\leq \log _{L}\left({\frac {N+1}{2}}\right)$.

Remarques

• Lesarbres 2-3-4sont 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 (enO(log n)) pour les opérations de base (recherche, insertion, suppression) que pour un arbre classique (où l'insertion est enO(h),avec h la hauteur de l'arbre, donc potentiellement enO(n)suivant l'implémentation choisie).

Variantes

L’arbreArbre 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)— pour lequel on exige que le taux de remplissage minimal des nœuds internes soit de 2/3 — ou l’arbre B*+(en)(qui combine les arbres B+ et B*).

Annexes

• (en)Rudolf Bayer,Binary B-Trees for Virtual Memory,ACM-SIGFIDET Workshop1971,San Diego, California, Session 5B,pp.219-235.
• (en)Rudolf BayeretMcCreight, E. M.Organization and Maintenance of Large Ordered Indexes.Acta Informatica1, 173-189,1972.

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 – EmulatoreJava BTree–BTree Java Emulator.
• (en)Slady.net:animation sous forme d’applet Javapermettant de construire visuellement des arbres B.