CHAPITRE 2 : LA DÉFINITION, ET SES DEUX CONVENTIONS

Un B-arbre n'est pas un arbre binaire élargi au hasard. C'est une structure gouvernée par quatre règles strictes, dont découle tout le reste : y compris son équilibre, qu'il maintient sans jamais faire de rotation.

Un exemple avant la définition

Trois choses à remarquer immédiatement :

un nœud contient plusieurs clés, rangées par ordre croissant ;
un nœud à k clés possède k + 1 fils : ici la racine a 2 clés et 3 fils ;
toutes les feuilles sont au même niveau. Pas approximativement : exactement.

Les quatre propriétés

Voici la définition, énoncée avec le degré minimal t, la convention du livre de Cormen et celle qu'on rencontre le plus souvent à l'université.

Définition. Un B-arbre de degré minimal t (avec t ≥ 2) est un arbre vérifiant les quatre propriétés suivantes.

1. Contenu d'un nœud. Chaque nœud x porte :

x.n : son nombre de clés ;
x.cle₁ ≤ x.cle₂ ≤ … ≤ x.cle_n : ses clés, triées par ordre croissant ;
x.feuille : un booléen indiquant si x est une feuille ;
x.c₁, …, x.c_n+1 : ses n + 1 pointeurs de fils, si x n'est pas une feuille.

2. Propriété d'ordre. Si k_i désigne n'importe quelle clé du sous-arbre x.c_i, alors :

k₀ ≤ x.cle₁ ≤ k₁ ≤ x.cle₂ ≤ … ≤ x.cle_n ≤ k_n

Autrement dit, les clés du nœud découpent l'univers en n + 1 intervalles, et le i-ième fils contient exactement les clés du i-ième intervalle.

3. Équilibre parfait. Toutes les feuilles sont à la même profondeur, qui est la hauteur h de l'arbre.

4. Remplissage. Le nombre de clés d'un nœud est encadré :

t − 1 ≤ x.n ≤ 2t − 1

avec une seule exception : la racine, à qui l'on demande seulement d'avoir au moins une clé (la borne supérieure, elle, s'applique à tout le monde).

Lire la quatrième propriété

C'est la règle qui fait tout le travail, et elle mérite qu'on s'y arrête.

	Clés	Fils
Nœud au minimum	t − 1	t
Nœud au maximum (« plein »)	2t − 1	2t
Racine, au minimum	1	2

La borne inférieure garantit que l'arbre ne dégénère pas en filaments : aucun nœud ne peut être presque vide, donc l'arbre reste large, donc bas.

La borne supérieure garantit qu'un nœud tient dans une page du disque.

L'exception sur la racine est une nécessité pratique : un arbre contenant trois clés en tout ne peut pas avoir une racine à t − 1 clés si t vaut 100.

L'autre convention : l'ordre m

Beaucoup de cours, et une bonne partie de la littérature, n'emploient pas t mais l'ordre m, défini comme le nombre maximal de fils. Les propriétés s'énoncent alors ainsi :

tout nœud a au plus m fils, donc au plus m − 1 clés ;
tout nœud interne autre que la racine a au moins ⌈m/2⌉ fils ;
la racine, si elle n'est pas une feuille, a au moins 2 fils ;
un nœud à k fils porte exactement k − 1 clés ;
toutes les feuilles sont au même niveau.

Passer d'une convention à l'autre. Les deux disent la même chose pour m pair :

m = 2t t = ⌈m/2⌉

Un B-arbre de degré minimal t = 2 est donc un B-arbre d'ordre m = 4 : 2 à 4 fils, 1 à 3 clés. C'est exactement le schéma du début de ce chapitre.

La nuance apparaît pour m impair. Avec la convention t, le nombre maximal de clés 2t − 1 est toujours impair ; la convention m autorise aussi les valeurs paires. En pratique cela ne change ni les algorithmes ni les complexités, mais vérifiez toujours quelle convention votre sujet d'examen emploie : un même arbre peut être « d'ordre 4 » ou « de degré minimal 2 » selon qui rédige l'énoncé.

Un second exemple, plus large

Ici t = 3, donc chaque nœud autre que la racine porte entre 2 et 5 clés et possède entre 3 et 6 fils. Vérifions sur le schéma : A C D E en a 4, J K en a 2, R S T U V en a 5. Tout est dans les clous, et la racine a bien 4 clés pour 5 fils.

Équilibre sans rotation

Voilà ce qui distingue vraiment un B-arbre d'un AVL ou d'un arbre rouge-noir. Ces derniers rétablissent leur équilibre par des rotations, qui réorganisent localement les liens. Un B-arbre, lui, n'en fait jamais.

Un B-arbre ne grandit pas par le bas, mais par le haut : sa hauteur n'augmente que lorsque la racine éclate.

C'est ce mécanisme, l'éclatement, étudié au chapitre 6, qui maintient l'équilibre parfait exigé par la propriété 3. Les feuilles restent toutes au même niveau parce qu'elles descendent toutes d'un cran en même temps, le jour où la racine se partage.

À retenir

Clés triées dans le nœud ; un nœud à k clés a exactement k + 1 fils.
Les clés découpent l'univers en intervalles, un par sous-arbre.
Toutes les feuilles sont exactement au même niveau.
Entre t − 1 et 2t − 1 clés par nœud ; la racine échappe à la borne basse.
Deux conventions coexistent : degré minimal t et ordre m, avec m = 2t.

Exercices d'application

Exercice 1

Les arbres suivants sont-ils des B-arbres de degré minimal t = 2 ? Justifiez chaque réponse.
(a) une racine à 1 clé, avec deux feuilles de 1 clé chacune
(b) une racine à 1 clé, avec une feuille de 1 clé à gauche et une feuille de 1 clé à droite, elle-même ayant un fils
(c) une racine à 4 clés et 5 feuilles de 2 clés

Voir le corrigeMasquer le corrige

(a) Oui. Avec t = 2, un nœud non racine doit porter entre 1 et 3 clés : les deux feuilles à 1 clé respectent la borne basse. La racine a au moins 1 clé. Les deux feuilles sont au même niveau.

(b) Non. Deux propriétés sont violées. D'abord, les feuilles ne sont pas au même niveau : la propriété 3 est brisée. Ensuite, un nœud qui a un fils n'est pas une feuille et doit en avoir k + 1 pour k clés, donc 2 fils pour 1 clé, pas un seul.

(c) Non. Avec t = 2, le maximum est 2t − 1 = 3 clés. Une racine à 4 clés dépasse la borne supérieure, qui s'applique aussi à la racine. Elle serait en revanche licite pour t = 3 (maximum 5), où les feuilles à 2 clés atteindraient tout juste le minimum t − 1 = 2.

Exercice 2

Un B-arbre d'ordre m = 5 est donné. Combien de clés et combien de fils peut porter un nœud interne qui n'est pas la racine ?

Voir le corrigeMasquer le corrige

Avec la convention d'ordre m :

au plus m = 5 fils, donc au plus 4 clés ;
au moins ⌈m/2⌉ = ⌈2,5⌉ = 3 fils, donc au moins 2 clés.

Un nœud interne non racine porte donc 2, 3 ou 4 clés, et possède 3, 4 ou 5 fils.

Noter que m = 5 est impair : cet arbre ne correspond exactement à aucun degré minimal t. Avec t = 3 on aurait 2 à 5 clés, avec t = 2 on aurait 1 à 3 clés. C'est le cas où les deux conventions ne se superposent pas, et où il faut lire l'énoncé attentivement.

Exercice 3

Pourquoi la racine échappe-t-elle à la borne inférieure t − 1 ?

Voir le corrigeMasquer le corrige

Parce que l'exiger rendrait impossibles les petits arbres.

Prenons t = 100 et un index qui ne contient encore que trois clés. Si la racine devait porter au moins t − 1 = 99 clés, un tel arbre ne pourrait tout simplement pas exister.

L'exception a aussi une justification structurelle. La borne basse sert à garantir que l'arbre reste large, donc bas. Or la racine ne pèse que pour un niveau : qu'elle soit peu remplie ne dégrade pas la hauteur de façon significative. Le calcul du chapitre 4 en tient compte en la traitant à part.

C'est aussi pour cela que la racine est le seul nœud autorisé à disparaître : quand une fusion la vide complètement, son unique fils devient la nouvelle racine et l'arbre perd un niveau.

Cherchez avant d'ouvrir le corrige : c'est en butant sur les difficultes que l'on progresse.