CHAPITRE 4 : LA HAUTEUR, ET POURQUOI ELLE RESTE MINUSCULE

Tout l'intérêt du B-arbre tient dans un seul résultat : sa hauteur est bornée par un logarithme en base t. Comme t vaut couramment une centaine, cette hauteur est ridiculement petite. Démontrons-le.

L'énoncé

Avant de le démontrer, mesurons ce qu'il dit. Pour n = 1 000 000 de clés :

Deux niveaux pour un million de clés. C'est cela, le gain.

L'idée de la démonstration

Pour majorer la hauteur, on cherche à minorer le nombre de clés : on se demande quel est le plus petit nombre de clés que peut contenir un B-arbre de hauteur h. Si même le plus dégarni des arbres de hauteur h contient beaucoup de clés, alors un arbre contenant peu de clés ne peut pas être haut.

On majore la hauteur en minorant le remplissage. C'est le raisonnement type pour toutes les structures équilibrées.

Compter les nœuds, niveau par niveau

Plaçons-nous dans le cas le plus défavorable : chaque nœud contient le minimum de clés autorisé.

• La racine a au moins 1 clé, donc au moins 2 fils.
• Tout autre nœud a au moins t − 1 clés, donc au moins t fils.

Comptons alors les nœuds à chaque profondeur :

La racine donne 2 fils ; ensuite chaque nœud en donne t, d'où la puissance qui démarre à i = 1.

Du nombre de nœuds au nombre de clés

Chaque nœud de profondeur ≥ 1 porte au moins t − 1 clés, et la racine en porte au moins 1. Donc :

n ≥ 1 + (t − 1) · Σ_i=1^h 2 tⁱ⁻¹

Développons la somme géométrique :

somme_{i=1}^{h} 2 t^(i-1)  =  2 (1 + t + t^2 + ... + t^(h-1))

                           =  2 (t^h - 1) / (t - 1)

En reportant :

n  >=  1 + (t - 1) x 2 (t^h - 1) / (t - 1)

   >=  1 + 2 (t^h - 1)

   >=  2 t^h - 1

Conclure

De n ≥ 2t^h − 1, on isole t^h :

t^h ≤ (n + 1) / 2

Puis on passe au logarithme de base t, qui est croissant :

h ≤ log_t ( (n + 1) / 2 )    ∎

Pourquoi la base du logarithme compte

Au chapitre sur la complexité, on apprend qu'on néglige la base d'un logarithme, puisque changer de base revient à multiplier par une constante. C'est vrai, et ici, c'est précisément cette constante qui nous intéresse.

log_t(n) = log_2(n) / log_2(t)

t = 2   : on divise par 1       -> aucun gain
t = 128 : on divise par 7       -> 7 fois moins de niveaux
t = 1024: on divise par 10      -> 10 fois moins de niveaux

Un facteur 7 serait anecdotique sur des opérations à 10 nanosecondes. Sur des accès à 10 millisecondes, il fait passer une requête de 0,2 seconde à 0,03 seconde.

La théorie dit « c'est la même complexité ». L'ingénierie dit « c'est sept fois moins de disque ». Les deux ont raison, et c'est la seconde qu'on paie.

La borne est pessimiste

Le théorème suppose tous les nœuds au minimum de remplissage. En pratique, après des insertions quelconques, les nœuds sont remplis à environ 70 % en moyenne, et la hauteur réelle est souvent inférieure d'un niveau à la borne.

On peut d'ailleurs encadrer la hauteur des deux côtés. Dans le meilleur cas, tous les nœuds sont pleins avec 2t − 1 clés, et :

log_2t(n + 1) ≤ h ≤ log_t((n + 1)/2)

2 t^(i-1) x t = 2 t^i = 2 t^((i+1)-1)

n >= 2 x 50^3 - 1 = 2 x 125 000 - 1 = 249 999

nb_noeuds = 1 + 100 + 10 000 + 1 000 000 = 1 010 101
n_max     = 99 x 1 010 101 = 99 999 999

degre maximal = 2t = 256 fils
nb_noeuds = 1 + 256 + 256^2 + 256^3 = 16 843 009
n_max     = 255 x 16 843 009 = 4 294 967 295