418
A Rappels algorithmiques
Le tableau clés qui contient les clés d’un nœud donné est trié en ordre croissant.
Si n est le nombre de clés contenues dans un nœud, seules les cases d’indices 1 à n
du tableau clés, et les cases d’indices 1 à n + 1 du tableau fils lorsque le nœud n’est
pas une feuille, contiennent une valeur.
Dans ce qui suit, nous utilisons deux fonctions charger et sauver qui prennent
en charge les transferts entre la mémoire secondaire où est stocké l’arbre et la
mémoire principale où s’exécute l’algorithme. L’unité de transfert est le nœud
stocké dans une page mémoire (figures A.18 et A.19).
Fig. A.18 Un arbre-B prudent de paramètre m = 2 ; les feuilles, qui représentent les possibilités
d’insertion et ne contiennent pas de clés, sont omises
Fig. A.19 Un nœud lors de la recherche de la clé X : n ≤ 2m − 1 est le nombre de clés du nœud,
l’algorithme de recherche a testé les i − 1 premières clés sans trouver X, et va comparer la i-ième
clé Y à X
A Rappels algorithmiques
Le tableau clés qui contient les clés d’un nœud donné est trié en ordre croissant.
Si n est le nombre de clés contenues dans un nœud, seules les cases d’indices 1 à n
du tableau clés, et les cases d’indices 1 à n + 1 du tableau fils lorsque le nœud n’est
pas une feuille, contiennent une valeur.
Dans ce qui suit, nous utilisons deux fonctions charger et sauver qui prennent
en charge les transferts entre la mémoire secondaire où est stocké l’arbre et la
mémoire principale où s’exécute l’algorithme. L’unité de transfert est le nœud
stocké dans une page mémoire (figures A.18 et A.19).
Fig. A.18 Un arbre-B prudent de paramètre m = 2 ; les feuilles, qui représentent les possibilités
d’insertion et ne contiennent pas de clés, sont omises
Fig. A.19 Un nœud lors de la recherche de la clé X : n ≤ 2m − 1 est le nombre de clés du nœud,
l’algorithme de recherche a testé les i − 1 premières clés sans trouver X, et va comparer la i-ième
clé Y à X