70
3 Arbres, algorithmes et données
Fig. 3.7 Un exemple d’insertion dans un arbre-B optimiste. Ici m = 2, les nœuds contiennent
entre 2 et 4 clés. La clé médiane en rouge est prise parmi les 4 clés du nœud plein et la nouvelle
clé, et elle remonte vers le nœud parent
pleins, et est analogue à celui présenté plus haut pour les arbres 2–3 de recherche.
Il est décrit par exemple dans le livre de Kruse et Ryba [162]. Dans cet algorithme,
une feuille pleine donne naissance à deux feuilles contenant m clés, comme dans la
figure 3.7.
Dans les deux cas (arbre optimiste comme arbre prudent), la hauteur de l’arbre-B
ne croît que lors de l’éclatement de la racine de l’arbre.
D’un point de vue informatique, ces arbres sont utilisés pour stocker des bases
de données en mémoire externe, ou secondaire. Le nombre maximal de clés, ou
plus exactement d’enregistrements, 6 dans un nœud est alors déterminé par la taille
d’une page de la mémoire externe, la page étant l’élément atomique de transfert
entre mémoires interne et externe.
Le nombre d’accès à des nœuds de l’arbre-B, lors d’une recherche ou d’une mise
à jour, donne le nombre d’accès à la mémoire externe, et donc le temps nécessaire à
l’opération (le temps de traitement interne étant considéré comme négligeable dans
ce contexte). La mesure de complexité la plus pertinente pour les algorithmes de
recherche ou de mise à jour sur les arbres-B est ici, non le nombre d’opérations sur
les clés, opérations qui se font en mémoire interne, mais le nombre d’accès à la
mémoire externe, i.e., le nombre de pages visitées. C’est aussi le nombre de nœuds
sur un chemin allant de la racine à un nœud interne ; ce nombre est majoré par
1+ la hauteur de l’arbre et est donc d’ordre log m n (cf. la section 4.4.2). C’est la
certitude de cette hauteur logarithmique qui fait tout l’intérêt pratique des arbres-B.
Donnons un exemple numérique : une valeur du paramètre m = 50 nécessite un
arbre de hauteur 2 pour stocker 100 000 clés ; le nombre maximal de clés pouvant
être stockées dans un arbre de hauteur 4, et donc accessibles en au plus 5 accès
mémoire, est de l’ordre de 10 10 . En pratique, la valeur de m dans les bases de
données réelles m est fréquemment de l’ordre de plusieurs centaines, et il est donc
possible d’accéder à un très grand nombre de clés, avec un coût d’accès (compté en
nombre de nœuds visités) faible, et des performances « raisonnables ».
6 Chaque enregistrement comprend une clé qui l’identifie de manière unique, et d’autres champs
qui contiennent les informations associées, et dont la nature exacte dépend de l’utilisation précise
qui est faite de ces informations.
3 Arbres, algorithmes et données
Fig. 3.7 Un exemple d’insertion dans un arbre-B optimiste. Ici m = 2, les nœuds contiennent
entre 2 et 4 clés. La clé médiane en rouge est prise parmi les 4 clés du nœud plein et la nouvelle
clé, et elle remonte vers le nœud parent
pleins, et est analogue à celui présenté plus haut pour les arbres 2–3 de recherche.
Il est décrit par exemple dans le livre de Kruse et Ryba [162]. Dans cet algorithme,
une feuille pleine donne naissance à deux feuilles contenant m clés, comme dans la
figure 3.7.
Dans les deux cas (arbre optimiste comme arbre prudent), la hauteur de l’arbre-B
ne croît que lors de l’éclatement de la racine de l’arbre.
D’un point de vue informatique, ces arbres sont utilisés pour stocker des bases
de données en mémoire externe, ou secondaire. Le nombre maximal de clés, ou
plus exactement d’enregistrements, 6 dans un nœud est alors déterminé par la taille
d’une page de la mémoire externe, la page étant l’élément atomique de transfert
entre mémoires interne et externe.
Le nombre d’accès à des nœuds de l’arbre-B, lors d’une recherche ou d’une mise
à jour, donne le nombre d’accès à la mémoire externe, et donc le temps nécessaire à
l’opération (le temps de traitement interne étant considéré comme négligeable dans
ce contexte). La mesure de complexité la plus pertinente pour les algorithmes de
recherche ou de mise à jour sur les arbres-B est ici, non le nombre d’opérations sur
les clés, opérations qui se font en mémoire interne, mais le nombre d’accès à la
mémoire externe, i.e., le nombre de pages visitées. C’est aussi le nombre de nœuds
sur un chemin allant de la racine à un nœud interne ; ce nombre est majoré par
1+ la hauteur de l’arbre et est donc d’ordre log m n (cf. la section 4.4.2). C’est la
certitude de cette hauteur logarithmique qui fait tout l’intérêt pratique des arbres-B.
Donnons un exemple numérique : une valeur du paramètre m = 50 nécessite un
arbre de hauteur 2 pour stocker 100 000 clés ; le nombre maximal de clés pouvant
être stockées dans un arbre de hauteur 4, et donc accessibles en au plus 5 accès
mémoire, est de l’ordre de 10 10 . En pratique, la valeur de m dans les bases de
données réelles m est fréquemment de l’ordre de plusieurs centaines, et il est donc
possible d’accéder à un très grand nombre de clés, avec un coût d’accès (compté en
nombre de nœuds visités) faible, et des performances « raisonnables ».
6 Chaque enregistrement comprend une clé qui l’identifie de manière unique, et d’autres champs
qui contiennent les informations associées, et dont la nature exacte dépend de l’utilisation précise
qui est faite de ces informations.