Arbre B

Un article de Wikipédia, l'encyclopédie libre.

Les arbres B (appelés aussi B-arbres par calque du terme anglais B-trees ) sont des arbres équilibrés qui sont principalement utilisés dans l'implémentation de bases de données et de systèmes de fichiers. Ils gardent les données sous forme triée et permettent une insertion et une suppression en temps d'exécution amorti logarithmique.

Le principe général est de permettre aux nœuds de posséder plus d'une clé, ce qui minimise la taille de l'arbre et réduit le nombre opérations d'équilibrage. De plus les B-arbres grandissent à partir de la racine contrairement aux arbres binaires de recherche qui poussent à partir des feuilles.

Le créateur des arbres B, Rudolf Bayer, n'a pas expliqué la signification du "B". L'explication la plus fréquente est que le B signifie "balancé", cependant il pourrait aussi signifier "Bayer" ou "Boeing", car il travaillait alors pour Boeing Scientific Research Labs.

Sommaire

[modifier] Structure d'arbre B

Soient L et U deux entiers naturels non nuls tels que L ≤ U. On définit alors un L-U arbre B de la manière suivante : chaque nœud sauf la racine contient un minimum de L-1 clés (ou éléments), un maximum de U-1 clés, et possède un maximum de U fils. Pour chaque nœud interne (qui n'est pas une feuille), le nombre de fils est toujours le nombre de clés plus un : si n est le nombre de fils, on parle alors de n-nœud : un L-U arbre ne contient que des n-nœuds avec L ≤ n ≤ U. Souvent, on prend L=t et U=2×t, et on appelle t le degré minimal de l'arbre B.

De plus la construction des arbres B implique qu'un arbre B est toujours équilibré. Chaque clé d'un nœud interne est en fait une borne qui divise les sous-arbres de ce nœud. Par exemple, si un nœud a 3 fils (racines de trois sous-arbres), alors il a 2 clés notées c1 et c2 qui délimitent les clés de chaque sous-arbre : chaque clé du sous-arbre gauche sera inférieure à c1, toutes les clés du sous-arbre du milieu seront comprises entre c1 et c2, et enfin toutes les clés du sous-arbre droit seront supérieures à c2.

[modifier] Opérations

[modifier] Recherche

La recherche est effectuée de la même manière que dans un arbre binaire de recherche. En partant de la racine, on parcourt récursivement l'arbre, en choisissant pour chaque nœud le sous-arbre fils dont les clés seront comprises entre les mêmes bornes que celles de la clé recherchée.

[modifier] 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 le fait qu'un nœud ait trop de clés ou pas : s'il possède un nombre acceptable de clés, on ne fait rien, sinon on le transforme en deux nœuds, chacun possédant un minimum de clés, et on fait « remonter » la clé du milieu : on l'insère dans le nœud père. Le nœud père peut alors posséder trop de fils : le procédé continue donc 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, qui aura alors pour fils les deux nœuds crées à partir de l'ancienne racine de la même manière que précédemment. Pour que l'opération soit possible, on remarque qu'il faut que U ≥ 2L sinon les nouveaux nœuds n'auront pas assez de clés.

[modifier] 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 similairement aux arbres binaires de recherche en recherchant la clé la plus à gauche dans le sous-arbre droit de la clé à supprimer ou la plus à droite dans le sous-arbre gauche: celle-ci appartient à une feuille et 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 ce nœud est une feuille, soit il possède encore suffisamment de clés et l'algorithme termine, soit il a moins de L-1 clés et alors :
    • 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 amener le père a ne pas 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é père, puis la clé 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.

[modifier] Remarques

  • La plupart du temps, on a U=2L : on parle alors d'arbre B d'ordre L.
  • Les arbres 2-3-4 sont l'implémentation la plus utilisée des arbres B : ce sont en fait des 2-4 arbres B ou arbres B d'ordre 2.

[modifier] Variantes

L'arbre B+ diffère légèrement de l'arbre B, en ceci que toutes les données sont stockées exclusivement dans des feuilles. Il existe d'autres variantes également, tel que l'arbre B*.

[modifier] Références

  • (en) Rudolf Bayer, Binary B-Trees for Virtual Memory, ACM-SIGFIDET Workshop 1971, San Diego, California, Session 5B, p. 219-235.
  • (en) Rudolf Bayer et McCreight, E. M. Organization and Maintenance of Large Ordered Indexes. Acta Informatica 1, 173-189, 1972.

[modifier] Voir aussi

Arbre de fouille

[modifier] Lien externe