CHAPITRE 3 : ANATOMIE D'UN NŒUD

Un nœud de B-arbre n'est pas une boîte abstraite : c'est une page du disque, dont chaque octet est compté. Voyons comment elle s'organise.

Clés et pointeurs s'alternent

La structure se lit de gauche à droite comme une alternance :

c1  |  a1  |  c2  |  a2  |  c3  |  a3  |  c4
 ^      ^
 |      cle
 pointeur vers un sous-arbre

Trois clés, quatre pointeurs. Et surtout, une règle de lecture limpide :

Sous-arbre	Contient les clés
c₁	strictement inférieures à a₁
c₂	comprises entre a₁ et a₂
c₃	comprises entre a₂ et a₃
c₄	strictement supérieures à a₃

C'est exactement la généralisation de l'arbre binaire de recherche, qui n'avait qu'une clé et donc deux intervalles : « plus petit » et « plus grand ».

En code

class Noeud:
    def __init__(self, t, feuille=True):
        self.t = t                # degre minimal
        self.cles = []            # au plus 2t-1 cles, triees
        self.fils = []            # au plus 2t pointeurs
        self.feuille = feuille

    def n(self):
        return len(self.cles)

    def plein(self):
        return len(self.cles) == 2 * self.t - 1

    def minimal(self):
        return len(self.cles) == self.t - 1

Deux invariants se vérifient à tout instant sur un nœud correct :

# 1. les cles sont triees
assert all(noeud.cles[i] <= noeud.cles[i+1]
           for i in range(len(noeud.cles) - 1))

# 2. une feuille n'a pas de fils ; un noeud interne en a n+1
if noeud.feuille:
    assert noeud.fils == []
else:
    assert len(noeud.fils) == len(noeud.cles) + 1

Le second invariant est le piège classique. Quand on implémente l'insertion, il est facile d'ajouter une clé sans ajouter le fils correspondant, ou l'inverse. L'arbre reste alors utilisable un moment, puis provoque un IndexError apparemment inexplicable plusieurs opérations plus tard. Vérifier cet invariant après chaque modification fait gagner des heures.

Ce qu'il y a vraiment dans une page

Sur le disque, un nœud contient davantage que des clés. Un format réaliste ressemble à ceci :

Champ	Taille	Rôle
Nombre de clés	2 o	le `n` du nœud
Drapeau feuille	1 o	faut-il lire des fils ?
Remplissage	qq o	alignement mémoire
Clés	n × taille_clé	le contenu utile
Pointeurs de fils	(n+1) × 8 o	numéros de page
Espace libre	le reste	pour les insertions futures

Noter le dernier poste : un nœud n'est presque jamais plein. L'espace libre est ce qui permet d'insérer sans tout réorganiser.

Choisir le degré

Le degré ne se choisit pas au hasard : il se calcule à partir de la taille d'une page.

taille_page      = 4096   octets
taille_cle       =    8   octets (un entier 64 bits)
taille_pointeur  =    8   octets (un numero de page)
entete           =    8   octets

n cles + (n+1) pointeurs doivent tenir :
   8n + 8(n+1) + 8 <= 4096
   16n          <= 4080
   n            <= 255

donc 2t - 1 = 255, soit t = 128

Vérifions ce que cela donne en hauteur :

Hauteur	Clés contenues, au minimum
1	255
2	≈ 32 000
3	≈ 4 millions
4	≈ 536 millions
5	≈ 68 milliards

Avec t = 128, quatre niveaux suffisent pour un demi-milliard de clés. La racine restant en mémoire, trois accès disque suffisent à retrouver n'importe laquelle.

Clés seules ou clés et données ?

Deux façons de ranger les données associées aux clés :

Données dans les nœuds. Chaque clé est accompagnée de son enregistrement. Simple, mais les enregistrements sont gros, donc on met moins de clés par page, donc l'arbre est plus haut.
Données hors des nœuds. Le nœud ne contient que la clé et un pointeur vers l'enregistrement. L'arbre reste très plat, au prix d'un accès supplémentaire à la fin.

C'est cette seconde solution que retiennent les bases de données, et le chapitre 8 montrera comment les B+ arbres la poussent à son terme en ne gardant aucune donnée dans les nœuds internes.

À retenir

Un nœud alterne pointeurs et clés : n clés, n + 1 pointeurs.
Chaque pointeur mène au sous-arbre d'un intervalle délimité par les clés voisines.
Le degré se calcule depuis la taille d'une page, pas au jugé.
Invariant à vérifier sans cesse : une feuille n'a pas de fils, un nœud interne en a exactement n + 1.

Exercices d'application

Exercice 1

Une page fait 8 ko. Les clés sont des chaînes de 32 octets, les pointeurs font 8 octets et l'en-tête 16 octets. Calculez le degré minimal t, puis la hauteur nécessaire pour un milliard de clés.

Voir le corrigeMasquer le corrige

Nombre de clés par nœud :

32n + 8(n+1) + 16 <= 8192
40n + 24          <= 8192
40n               <= 8168
n                 <= 204

On prend n = 203 pour que 2t − 1 soit impair : t = 102.

Hauteur : le théorème du chapitre suivant donne h ≤ log_t((n+1)/2).

log_102((10^9 + 1) / 2) = ln(5x10^8) / ln(102)
                        = 20,03 / 4,62
                        = 4,3

Donc 5 niveaux au plus, et en pratique 4 : la borne du théorème est pessimiste puisqu'elle suppose tous les nœuds au minimum.

Exercice 2

Un collègue propose de stocker directement les enregistrements complets (512 octets chacun) dans les nœuds, pour éviter un accès disque supplémentaire. Évaluez son idée sur une page de 4 ko.

Voir le corrigeMasquer le corrige

Calculons combien de clés tiendraient alors par nœud :

520n + 8(n+1) <= 4096      (512 d'enregistrement + 8 de cle)
528n          <= 4088
n             <= 7

On passe de 255 clés par nœud à 7, soit t = 4. L'effet sur la hauteur est brutal :

t = 128 : log_128(5x10^8) = 4,1  ->  5 niveaux
t =   4 : log_4(5x10^8)   = 14,4 ->  15 niveaux

Son idée économise un accès et en coûte dix. Elle est donc mauvaise ici.

Elle serait défendable si les enregistrements étaient minuscules, quelques octets, ou si l'on faisait surtout des parcours séquentiels plutôt que des recherches ponctuelles. C'est le raisonnement qui mène aux B+ arbres du chapitre 8 : garder les nœuds internes maigres, et reléguer toutes les données dans les feuilles.

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