Les INDEX de FICHIERS

à BASE de B-ARBRES

Accéder rapidement aux données

 

L'intérêt des gestionnaires de fichiers tient à leur capacité à retrouver de manière efficace les données répondant à certains critères (par exemple, tous les clients habitant telles villes et dont les commandes dépassent un certain montant). Avec l'augmentation régulière des capacités de stockage des périphériques d'ordinateurs (disques durs, CD-ROM, etc.), les données à extraire peuvent être stockées dans des fichiers de très grande taille. L'algorithme de recherche utilisé joue donc un rôle essentiel dans la performance globale du système.

La méthode habituelle pour faciliter ce type de recherche consiste à construire un index qui est automatiquement mis à jour lors de chaque modification d'un enregistrement. Cet index est généralement stocké dans un fichier séparé de celui qui contient les enregistrements proprement dits (le programme Btrieve de Novell constitue toutefois une exception notable à cette règle). Les enregistrements eux-mêmes sont ajoutés au fichier principal dans l'ordre de leur saisie (en réutilisant éventuellement la place laissée vacante par les enregistrements marqués comme étant " détruits " du fichier), tandis que le fichier d'index ne contient que les clés sur lesquelles se feront les recherches ultérieures (les clés ne représentent habituellement qu'une fraction des données stockées dans un enregistrement). Ces clés doivent donc être organisées de manière à pouvoir retrouver rapidement l'adresse de l'enregistrement associé à une clé donnée (cette adresse peut représenter le numéro de l'enregistrement ou le déplacement correspondant dans le fichier principal) .

 

Les contraintes

Dès que l'on aborde la gestion de fichiers de grande taille, le facteur limitatif devient l'accès au périphérique de stockage, autrement dit, la lecture ou l'écriture d'un secteur sur le disque dur (ou sur le CD-ROM). Les méthodes d'indexation tiennent compte de cette contrainte et cherchent à minimiser le nombre de secteurs à lire sur le disque pour localiser un enregistrement donné. D'une manière générale, on mesure les performances d'un algorithme d'indexation selon quatre critères :

Chaque insertion impose généralement un parcours de l'index pour déterminer l'emplacement où la nouvelle valeur sera insérée. Il peut également s'avérer utile de procéder à une réorganisation partielle de la structure de l'index ;

Les algorithmes d'indexation à base de B-arbres étudiés ici obtiennent de bons résultats sur l'ensemble des critères précités. D'autres méthodes d'indexation peuvent se révéler mieux adaptées à certains cas particuliers (par exemple, une base de données sur CD-ROM dont le contenu n'est jamais modifié). La souplesse d'utilisation des B-arbres leur permet toutefois de couvrir la grande majorité des besoins en matière d'indexation, ce qui explique sans doute pourquoi de nombreux SGBD du commerce gèrent leurs index à l'aide d'une méthode dérivée des B-arbres. Parmi les plus connus, on peut notamment citer FoxPro 2.0 (Fox Software), Btrieve (Novell), Paradox (Borland) et db Vista (Raima Corporation, distribué en France par Ise-Cegos).

Comment un arbre accélère-t-il la recherche de l'enregistrement correspondant dont la clé a une valeur donnée ? Pour répondre à cette question, considérons tout d'abord un type d'arbre particulier appelé " arbre binaire ". Il est important d'en comprendre le fonctionnement, car les B-arbres étudiés plus loin procèdent des mêmes principes.

Un arbre binaire se caractérise par le fait que chaque noeud a deux enfants au maximum. L'arbre est ordonné de manière à ce que toutes les clés de valeur inférieure à celle du noeud courant soient situées sur la branche de gauche de ce dernier, tandis que la branche de droite

mène aux noeuds de valeur supérieure ou égale à celle du noeud courant. La figure 2 représente un arbre binaire construit selon ces conventions. Voici comment s'effectue dans cet arbre la recherche de l'enregistrement associé à la clé de valeur 16 : la valeur recherchée étant inférieure à celle de la racine (25), il faut donc suivre la branche de gauche vers le noeud de valeur 15; puisque 16 est supérieur à 15, on suit la branche de droite vers le noeud de valeur 18; comme 16 est inférieur à 18, on suit alors la branche de gauche qui mène à la valeur recherchée. Il ne reste plus alors qu'à lire dans ce noeud l'adresse de l'enregistrement correspondant à cette clé qui est stocké dans le fichier principal de la base de données.

L'arbre binaire représenté sur la figure 2 contient 13 clés et a une profondeur de 4 niveaux, puisqu'il faut traverser au maximum 4 branches pour aboutir au nceud le plus éloigné de la racine. Une recherche dans cet arbre nécessite donc la lecaire de 4 noeuds au maximum (si l'on suppose que la racine est conservée en mémoire). A titre de comparaison, une recherche séquentielle dans la même liste de valeurs nécessiterait la lecture de 6 ou 7 noeuds en moyenne, et jusqu'à 13 noeuds dans le pire des cas. L'arbre binaire offre donc déjà de bien meilleures performances qu'une recherche séquentielle, et l'écart augmente (en faveur de la recherche par arbre, bien sûr) avec le nombre de valeurs stockées (on suppose que la lecture d'un noeud impose à chaque fois un accès au disque).

Que se passerait-il maintenant si l'on recherchait la valeur 45 dans cet arbre ? En partant de la racine, il faudrait constamment suivre les branches de droite jusqu'à arriver au noeud de valeur 50. Puisque 45 est inférieur à 50, le noeud en question se trouverait sur la branche de gauche à partir du noeud de valeur 50, mais cette branche n'existe pas ! La valeur recherchée n'est donc pas présente dans l'arbre binaire. Cette recherche indique toutefois l'endroit où il faudrait insérer la valeur en question dans l'arbre, s'il fallait lui ajouter la clé de valeur 45.

Figure 1 : un arbre informatique

Bien que la méthode d'insertion décrite ci-dessus soit simple à comprendre, elle présente un risque important de dégénérescence lorsque les clés sont ajoutées de manière presque ordonnée (un cas fréquent dans la pratique).

La figure 3 représente l'arbre binaire obtenu si l'on part d'un arbre vide auquel on ajoute successivement les valeurs 15, 16, 18, 21, 25, 5, 32, 41, 40, 43, 50, 19 et 23. Cet arbre contient les mêmes valeurs que celui de la figure 2, mais sa profondeur est de 8 niveaux. Dans ce cas, une recherche peut donc obliger à lire jusqu'à 8 noeuds, ce qui n'est guère plus avantageux que la simple recherche séquentielle.

Il serait évidemment possible de réorganiser l'arbre pour obtenir une structure plus équilibrée, mais cette solution nécessiterait un temps de traitement important pendant lequel l'index ne pourrait être utilisé pour accéder au fichier de données.

Equilibrer les arbres

Figure 2 : un arbre binaire ordonné

Pour éviter d'aboutir à la situation précédente, le plus simple est d'adopter une méthode d'insertion qui maintienne l'arbre binaire en " équilibre ".

Cette propriété signifie que, pour n'importe quel noeud, la profondeur du sous-arbre de gauche diffère de celle du sous-arbre de droite d'au plus un niveau. Elle garantit également un bon " remplissage " de chaque niveau, ce qui réduit le temps de recherche moyen. A titre d'exemple, l'arbre binaire dessiné sur la figure 4 est équilibré, et sa profondeur n'est plus que de 3 niveaux (bien qu'il contienne les mêmes valeurs que les arbres des figures 2 et 3).

Figure 3 : un arbre binaire dégénéré

L'utilisation d'un arbre binaire équilibré suppose toutefois que l'on effectue quelques réorganisations pour conserver l'équilibre de l'arbre après chaque insertion ou destruction. Les algorithmes employés pour obtenir ce résultat sont similaires à ceux décrits ci-après dans Ie cadre des B-arbres : ils ne sont donc pas détaillés dans le cas particulier des arbres binaires.

Les B-arbres

Les B-arbres généralisent les notions étudiées ci-dessus sur les arbres binaires équilibrés en permettant le stockage de plusieurs clés dans chaque noeud de l'arbre.

Un noeud qui contient N clés possède exactement N+1 enfants, ce qui augmente le " facteur de branchement " (fan-out) des B-arbres par rapport aux arbres binaires. Pour un même nombre de clés, la profondeur d'un B-arbre est donc plus faible que celle de l'arbre binaire équilibré correspondant.

On appelle l'ordre d'un B-arbre le nombre maximal de clés que peut contenir un noeud, augmenté d'une unité (l'ordre d'un B-arbre correspond donc au nombre maximal d'enfants de chaque noeud). Un B-arbre d'ordre M doit satisfaire les trois propriétés suivantes :

  1. La racine de l'arbre possède au minimum deux enfants, sauf si l'arbre est réduit à sa racine.
  2. Chaque noeud possède au maximum M enfants et chaque noeud autre que la racine est rempli au moins à la moitié de sa capacité maximale. Cela signifie que tous les noeuds autres que la racine et les feuilles de l'arbre ont entre M/2 et M enfants (l'arrondi dans l’expression M/2 a lieu vers l’entier supérieur le plus proche : chaque noeud d’un B-arbre d’ordre 5 possède au minimum 3 enfants). En raison de la relation qui lie le nombre de clés (chaque noeud d’un B-arbre d’ordre 5 doit ainsi contenir au moins 2 clés).
  3. Un B-arbre est parfaitement équilibré : toutes les feuilles sont à la même profondeur par rapport à la racine. Cette propriété garantit un bon niveau de performance quelle que soit la position de la clé recherchée dans le B-arbre.

Figure 4 : un arbre binaire équilibré

Figure 5 : un B-arbre d'ordre 5

La figure 5 représente un B-arbre d’ordre 5. La profondeur de cet arbre est seulement d’un niveau, bien qu’il contienne 15 clés (soit deux clés de plus que l’arbre binaire équilibré de la figure 4 qui s’étendait, quant à lui, sur 3 niveaux).

Un noeud occupe généralement un secteur sur le disque dur. La profondeur de l’arbre correspond donc au nombre maximal d’accès disque nécessaire pour localiser l’enregistrement associé à une clé donnée.

On peut donner mathématiquement qu’un B-arbre d’ordre M qui contient K clés a une profondeur inférieure ou égale à (1+(log((K+1)/2)/log((M/2)+1)), ce qui permet de calculer le temps maximal de recherche d’une clé (un arbre binaire correspond au cas particulier où M=2).

Les méthodes d’accès à une branche

Par suite des clés multiples contenues dans chaque noeud, le parcours d’un B-arbre est plus complexe que celui d’un arbre binaire. Deux règles permettent de déterminer quelle branche suivre lors d’une recherche : à l’intérieur de chaque noeud, toutes les clés sont classées par ordre ascendant ; pour chaque clé de valeur k, la branche de gauche qui part de cette clé contient les clés de valeur inférieure à k, tandis que la branche de droite contient les clés de valeur supérieure ou égale à k.

Lors de la recherche d’une clé, il faut donc appliquer pour chaque noeud (y compris la racine) la règle suivante : si la clé recherchée est inférieure à la première clé contenue dans le noeud, prendre la branche la plus à gauche. Si la clé recherchée est comprise entre la première et la deuxième clé du noeud, suivre la deuxième branche à partir de la gauche (et ainsi de suite). Si la clé recherchée est supérieure à la dernière clé du noeud (celle qui a la plus grande valeur), prendre la branche la plus à droite. Répéter ensuite cette opération à chaque noeud jusqu’à l’obtention de la valeur recherchée (ou de l’endroit où elle devrait se trouver si la clé correspondante n’existe pas dans l’arbre).

Les opérations d’insertion et de destruction de clés dans un B-arbre sont conçues de manière à conserver les trois propriétés fondamentales des B-arbres, ce qui garantit notamment l'équilibre constant du B-arbre. Il arrive donc que l'insertion ou la destruction d'une clé entraîne une réorganisation partielle de la structure du B-arbre. Ces petites opérations sont toutefois préférables aux réorganisations massives imposées par d'autres méthodes d'indexation durant lesquelles l'accès à la base de données est impossible.

Insérer une clé dans un B-arbre

Comme avec les arbres binaires, l'insertion d'une clé dans un B-arbre nécessite une recherche préalable qui indique l'emplacement où devrait se trouver la clé à insérer. Si le noeud en question n'est pas plein, il suffit d'y ajouter la nouvelle valeur tout en maintenant l'ordre ascendant des clés au sein du noeud.

Figure 6 : insertion d'une clé de valeur 15

La figure 6 indique le résultat obtenu après l'insertion d'une clé de valeur 15 dans le B-arbre de la figure 5. Il est cependant possible que le noeud en question contienne déjà le nombre maximal de clés autorisé (soit M-1 pour un B-arbre d'ordre M). Ce cas se produit si l'on essaie d'insérer une clé de valeur 6 dans le B-arbre de la figure 6. L'élément " central " du noeud, que l'on obtiendrait après l'insertion, est alors introduit dans le noeud père du noeud plein, tandis que ce dernier se trouve divisé en deux nceuds de taille égale.

Figure 7 : insertion d'une clé de valeur 6 et division d'un noeud

La figure 7 représente le résultat obtenu : la clé de valeur 5 est insérée dans le noeud père du noeud " saturé " <2,3,5,6,7>, et la séparation des clés restantes de ce noeud donne les noeuds <2,3> et <6,7>. Il peut évidemment arriver que le noeud père soit plein lui aussi lorsque l'on tente d'y insérer l'élément central du noeud à diviser : le noeud père est alors divisé à son tour selon la même méthode, et cette procédure de division se poursuit autant de fois qu'il le faut. Cela peut éventuellement forcer à insérer une nouvelle clé dans la racine du B-arbre. Si cette dernière est également saturée, elle est divisée comme un noeud normal, mais la clé qui aurait dû s'insérer dans le noeud père constitue alors la nouvelle racine de l'arbre. Une division de la racine augmente donc d'un niveau la profondeur du B-arbre.

A titre d'exemple, la figure 8 représente le B-arbre qui résulte de l'insertion d'une clé de valeur 25 dans le B-arbre de la figure 7. Pour aboutir à ce résultat, le noeud <21,25,27,28,29> a d'abord été divisé en <21,25> et <28,29>, tandis que la clé de valeur 27 allait s'insérer dans la racine de l'arbre. Celle-ci se trouvant alors saturée (<5,10,20,27,30>), elle est divisée en <5,10> et <27,30>, et une notivelle racine ne contenant que la clé de valeur 20 se trouve créée.

Figure 8 : L'insertion d'une clé de valeur 25 et division de la racine de l'arbre

La destruction d'une clé dans un B-arbre

La procédure de destruction d'une clé à l'intérieur d'un B-arbre est plus complexe que l'insertion car le nombre de cas à considérer est plus important. Il faut d'abord commencer par rechercher l'emplacement de la clé que l'on veut détruire. Si celle-ci appartient à une feuille de l'arbre, il suffit de retirer la valeur dans le noeud en question.

Ainsi, le fait de détruire la clé de valeur 15 dans le B-arbre de la figure 6 ramène l'arbre dans la situation de la figure 5.

Si la clé à détruire fait partie d'un nceud intérieur de l'arbre, il faut remplacer la clé détruite par une autre clé déjà présente dans l'arbre (pour conserver le même nombre de clés dans le noeud intérieur, donc un nombre identique de descendants, et par conséquent l'équilibre du B-arbre).

La clé en question sera la première clé (celle qui possède la valeur la plus faible) de la feuille située le plus à gauche sur le sous-arbre de droite de la clé à détruire.

Ainsi, supprimer la clé de valeur 20 dans l'arbre de la figure 5 amène la clé de valeur 21 à sa place, comme le montre la figure 9 (la situation serait d'ailleurs similaire si l'on retirait la même clé de l'arbre représenté par la figure 8).

Figure 9 : destruction de la clé de valeur 20 sur l'arbre de la figure 5

Il apparaît donc que la destruction d'une clé dans un B-arbre finit toujours par retirer une clé de l'une des feuilles de l'arbre. Après cette opération, la feuille en question risque toutefois de ne plus comporter suffisamment de clés pour satisfaire la deuxième propriété des B-arbres (celle qui impose un remplissage minimal de chaque noeud).

On résout ce problème en redistribuant les clés entre la feuille en sous-effectif et l'une de ses voisines, de préférence celle qui contient le plus de clés. Ce cas se produit si l'on détruit la dé de valeur 38 dans le B-arbre de la figure 9.

On réunit alors les clés qui restent dans la feuille en sous-effectif (qui contient dans notre cas uniquement la valeur 45), celles de sa voisine de gauche (qui comporte les clés <27,28,29>) et leur clé parente (de valeur 30).

On obtient donc l'ensemble de clés <27,28,29,30,45>, que l'on redistribue de manière aussi symétrique que possible (la clé de valeur 29 devenant le parent des feuilles <27,28> et <30,45>).

Le résultat de l'opération est représenté sur la figure 10.

Figure 10 : destruction de la clé de valeur 38 et redistribution des clés

Redistribuer les clés ou réunir les feuilles

Un autre cas particulier peut se produire si chaque feuille voisine de celle en sous-effectif contient à peine le nombre minimal de clés qui satisfait la deuxième propriété des B-arbres. Il est alors impossible de redistribuer les dés par la méthode précédente sans créer une nouvelle feuille en sous-effectif. C'est, par exemple, ce qui arrive si l'on essaie de détruire la clé de valeur 27 dans le B-arbre de la figure 10. Il faut alors réunir la feuille concernée par la destruction avec l'une de ses voisines pour former une feuille unique dans laquelle est également intégré le parent des deux feuilles réunies. Si l'on détruit la clé de valeur 27 du B-arbre de la figure 10 et que l'on réunit la feuille <12,18> avec la feuille <28> et leur parent <21>, on forme ainsi une nouvelle feuille qui contient les clés <12,18,21,28> (comme le montre la figure 11).

Figure 11 : destruction de la clé de valeur 27 et réunion de deux feuilles

La réunion de deux feuilles oblige donc à " emprunter " une clé au noeud père des feuilles concernées. Ce noeud risque donc de se trouver en sous-effectif après cette opération, ce qui oblige alors à lui appliquer, à son tour, l'une des deux méthodes étudiées ci-dessus (redistribution des clés ou réunion de deux noeuds). Comme pour l'insertion d'une clé, ces réorganisations peuvent se propager dans le B-arbre et atteindre éventuellement sa racine. Mais, contrairement aux feuilles et aux noeuds intérieurs de l'arbre, la racine d'un B-arbre peut rester en sous-effectif. C'est donc uniquement si la racine se retrouve entièrement vide qu'une nouvelle racine est formée par la réunion des deux noeuds situés au premier niveau de l'arbre (la profondeur totale du B-arbre diminue alors d'un niveau).

Ce cas se produit si l'on détruit la clé de valeur 25 dans le B-arbre de la figure 8 : il faut réunir la feuille <21> avec la feuille <28,29> en " empruntant " la clé <27> à leur noeud père qui se trouve alors lui-même en sous-effectif puisqu'il ne contient plus que la clé <30>. Comme le seul voisin de ce noeud contient déjà le nombre minimal de clés imposé par la deuxième propriété des B-arbres, il faut à nouveau réunir ces deux noeuds en " empruntant " la clé <20> à la racine de l'arbre. Celle-ci est alors remplacée par le noeud <5,10,20,30> qui résulte de la dernière réunion opérée, ce qui ramène à la situation représentée sur la figure 7.

Variations sur les B-arbres

Il est possible de construire plusieurs types d'arbres conçus sur le même principe que les B-arbres. Ces arbres dérivés des B-arbres s'obtiennent en modifiant l'une des trois propriétés de base ainsi que les algorithmes d'insertion et de destruction de clés.

Les B*-arbres se déduisent des B-arbres en modifiant la deuxième propriété pour imposer que chaque noeud soit au moins rempli aux deux tiers de leur capacité maximale en nombre de clés (au lieu de la moitié pour les B-arbres). On obtient ainsi des nceuds mieux remplis en moyenne qu'avec les B-arbres, d'où une meilleure utilisation de l'espace disque réservé pour l'index. Cette contrainte diminue souvent la profondeur d'un B*-arbre par rapport à celle du B-arbre correspondant, ce qui améliore également la vitesse de recherche.

La recherche dans un B'-arbre s'effectue exactement comme dans un B-arbre, et il est possible de programmer les insertions et les destructions de clés de manière tout à fait similaire. Les insertions causent toutefois plus de divisions de nceuds dans un B'-arbre que dans un B-arbre, à cause du meilleur remplissage de chaque noeud. Il est donc avantageux de modifier l'algorithme d'insertion pour éviter de diviser un noeud si ce n'est pas indispensable, car cette opération est relativement pénalisante en termes d'accès au disque et de performances. De plus, le fait de limiter les divisions des noeuds évite parfois la propagation d'une division jusqu'à la racine de l'arbre, ce qui empêche à son tour une augmentation de la profondeur totale de ce dernier. A noter cependant que la méthode des permutations locales (local shifts), étudiée ci-après, pour limiter les divisions de noeuds peut également être appliquée aux B-arbres classiques.

B*-arbres et permutations locales

Au lieu de diviser un noeud plein dès qu'il faut y insérer une nouvelle clé, on commence par examiner son frère de droite. Si ce noeud n'est pas plein, on lui ajoute la clé parente des deux noeuds concernés, tandis que celle-ci est remplacée par la plus grande clé du noeud plein (ce qui libère dans ce dernier l'emplacement nécessaire pour recevoir la nouvelle clé).

Ainsi, l'insertion d'une clé de valeur 20 dans l'arbre représenté sur la figure 11 n'entraîne pas la division du noeud <12,18,21,28> comme cela serait le cas avec l'algorithme de base. La clé parente <29> est ajoutée au frère de droite <30,45> et remplacée par la clé <28> du noeud initialement plein. Celui-ci peut alors recevoir la clé de valeur 20, ce qui amène à la situation décrite par la figure 12.

Figure 12 : insertion d'une clé de valeur 20 et permutations locales

Si le frère de droite se trouve déjà plein (ou s'il n'existe pas), la même opération est réalisée avec le frère de gauche du noeud dans lequel on tente d'insérer la nouvelle clé. C'est seulement lorsque les deux frères du noeud considéré sont déjà remplis qu'une division a lieu. Pour cela, on forme (à partir du noeud dans lequel s'insère la nouvelle clé et de l'un de ses voisins) trois noeuds dans lesquels les clés sont réparties aussi équitablement que possible. La figure 13 montre le résultat obtenu après l'insertion d'une clé de valeur 4 dans l'arbre de la figure 12. Ces divisions peuvent se propager sur plusieurs niveaux (si le noeud père est également plein) et, éventuellement, atteindre la racine de l'arbre. Dans ce dernier cas, la division de la racine s'effectue exactement comme avec l'algorithme classique.

Figure 13 : insertion d'une clé de valeur 4 et division de 2 noeuds pleins en 3 noeuds

Les B+-arbres

Les B+-arbres constituent la variante des B-arbres qui est probablement la plus utilisée dans les systèmes d'indexation réels. En effet, avec un SGBD, il est courant de rechercher l'enregistrement associé à une clé, puis de vouloir examiner séquentiellement les enregistrements suivants (dans l'ordre déterminé par la clé en question : il peut, par exemple, s'agir d'une date ou d'un numéro de compte bancaire).

Un B-arbre classique fournit un moyen efficace pour trouver le premier enregistrement associé à une clé, mais le traitement séquentiel des enregistrements suivants, nécessite à chaque fois une nouvelle recherche à partir de la racine de l'arbre, d'où une performance médiocre.

Un B+-arbre résout ce problème en stockant, dans chaque feuille de l'arbre, deux pointeurs vers les frères de gauche et de droite de la feuille en question. Une fois positionné sur une clé quelconque dans un B+-arbre, le traitement séquentiel des enregistrements revient donc à suivre ces pointeurs à la manière d'une liste chaînée. L'organisation des données au sein d'un B+-arbre est toutefois assez différente de celle des B-arbres, car le B+-arbre contient en réalite deux types de noeuds : la racine et les noeuds intérieurs de l'arbre sont organisés comme un B-arbre (ou comme un B*-arbre) servant à guider les recherches vers les feuilles de l'arbre. Celles-ci contiennent, quant à elles, toutes les clés stockées dans l'arbre, les adresses des enregistrements associés à chaque clé et les pointeurs utilisés lors des accès séquentiels.

Figure 14 : un B+-arbre d'ordre 5

Cette distinction étant posée, il faut maintenant construire le B-arbre qui guide l'accès vers les feuilles. Pour cela, les N-1 valeurs que comporte un noeud intérieur ayant N enfants sont déterminées grâce à la règle suivante : " la k-ème valeur d'un noeud est égale à la valeur de la clé la plus petite que l'on atteint à partir de la (k+1)-ème branche du noeud en question (celle qui part à droite de la valeur) ". Sur le B+-arbre de la figure 14, la valeur stockée dans la racine (20) correspond bien à la clé la plus petite que l'on atteint en suivant la deuxième branche de ce noeud (celle de droite). La même règle permet de déterminer les autres valeurs de cet arbre, et l'on applique le même raisonnement quelle que soit la complexité de l'arbre. Une recherche dans un B+-arbre s'effectue de la même manière qu'avec les B-arbres, mais il ne faut pas s'arrêter sur un noeud intérieur dès que l'on trouve la valeur recherchée : on continue, au contraire, à progresser jusqu'aux feuilles de l'arbre, car seules ces dernières contiennent les adresses effectives des enregistrements.

La partie supérieure d'un B+-arbre (c'est-à-dire tous les noeuds qui ne sont pas des feuilles) réalise en fait une sorte d'index de deuxième niveau qui permet d'accéder rapidement à la feuille contenant les informations voulucs. L'insertion et la destruction de dés dans un B+-arbre suivent les mêmes règles que pour un B-arbre ou pour un B*-arbre, en tenant compte de la modification de l'algorithme de recherche qui oblige à descendre jusqu'aux feuilles de l'arbre pour trouver l'endroit où insérer (ou détruire) une clé. Il faut néanmoins veiller à conserver la cohérence des valeurs stockées dans les noeuds intérieurs de l'arbre lorsqu'une feuille est modifiée, ce qui oblige à " remonter " les branches concernées pour ajuster certaines valeurs.

Etudions maintenant deux exemples de déclaration, en langage C, les structures de donnés nécessaires au stockage d'un B-arbre et d'un B+-arbre. La programmation d'algorithmes à base de B-arbres peut se faire selon des méthodes très diverses. Les exemples suivants ne fournissent qu'une illustration en langage C des concepts abordés dans cet article. Considérons d'abord le cas d'un B-arbre pour lequel les clés sont représentées par des variables de type integer et les adresses des enregistrements par des entiers longs correspondant, par exemple, au paramètre offset d'un appel à la fonction de bibliothèque lseek(). En plus de ces deux données, chaque clé contient un pointeur vers le noeud situé sur la branche de droite rattachée à cette clé. Les noeuds eux-mêmes comportent un nombre fixe de clés (déterminé par la constante MAX_CLES), un pointeur vers le noeud situé sur la branche la plus à gauche rattachée au noeud courant et un compteur qui indique le nombre de clés stockées dans le noeud. Enfin, l'arbre lui-même contient un pointeur sur le noeud racine et une zone tampon utilisée pour les réorganisations occasionnées par certaines insertions ou destructions :

typedef int t_cle; typedef long t_adresse;

#define MAX_CLES 10

struct s_cle {

t_cle valeur; // Valeur de la clé.

t_adresse adresse; // Adresse de l'enregistrement.

struct s_noeud *noeud_droit: // Pointeur vers le fils de droite. };

struct s_noeud {

int nbcles; // Nochre de clés dans le noeud.

struct s_noeud *noeud_gauche; // Pointeur vers la branche de gauche.

struct s_cle cles[ MAX_CLES ]; // Les clés elles-mêmes. };

typedef struct {

struct s_noeud *racine; // Racine de l'arbre.

struct s_cle *buffer; // Tampon utilisé prur les réorganisations. }

b_arbre;

L'exemple qui précède suppose que le B-arbre soit stocké en mémoire. Dans la pratique, les noeuds sont stockés dans un fichier d'index séparé du fichier principal (celui qui contient les données elles-mêmes). Les pointeurs de l'exemple ci-dessus sont alors remplacés par des adresses sur le disque (par exemple, les déplacements à partir du début du fichier d'index).

Pour minimiser les accès au disque et pour optimiser l'utilisation de l'espace disque, on " aligne " généralement les noeuds sur la taille des secteurs ou des clusters (groupes de secteurs que le DOS lit ou écrit en une seule opération). Le nombre de clés que l'on stocke dans chaque noeud est alors calculé en fonction de cette contrainte. Un B*-arbre utilise la même structure de

données qu'un B-arbre classique, seules les routines d'insertion et de destruction sont modifiées pour tenir compte des nouvelles règles à respecter.

Le cas des B+-arbres est, quant à lui, plus complexe car les noeuds intérieurs de l'arbre ont une structure différente de celle des feuilles. Ceci oblige à se servir des pointeurs de type void * (dans le cas où l'arbre est " en mémoire ") et à inclure un champ permettant de distinguer si l'on pointe sur un noeud intérieur ou sur une feuille :

typedef int t_cle; typedef long t_adresse;

typedef enum {e_noeud, e_feuille } type noeud;

#define MAX_CLES 10

struct s_cle_noeud {

t_cle valeur; // Valeur de la clé.

void *droit; // Pointeur vers le fils de droite. };

struct s_cle feuille {

t_cle valeur; // Valeur de la clé.

t_adresse adresse; // Adresse de l'enregistrrsnt. } ;

struct s_noeud {

type noeud type; // Normalement égal à "e_noeud".

int nb_clef; // Nombre de clés dans le noeud.

void *gauche; // Pointeur vers la branche de gauche.

struct s_cle_noeud cles[ MAX_CLES ] ;

// Les clés elles-mêmes. } ;

struct s_feuille {

type noeud type; // Normalement égal à "e_feuille".

int nbcles: // Nombre de clés dans la feuille.

void *gauche; // Pointeur vers la feuille de gauche.

void *droite: // Pointeur vers la feuille de droite.

struct s_cle_feuille cles [ MAX_CLES ] ;

// Les clés elles-mêmes. } ;

typedef struct {

struct s_noeud *racine; // Racine de l'arbre.

struct s_feuille *premiere; // Feuille la plus à gauche.

struct s_cle_noeud *buffer_noeud; // Tampon utilisé pour les réorganisations.

struct s_cle_feuille *buffer_feuille; // Idem. }

bplus_arbre;

A partir de ces déclarations et des principes exposés plus haut, il est possible de construire un ensemble complet de routines d'indexation à base de B-arbres, de B*-arbres ou de B+-arbres. Mais un projet de cette taille n'est pas trivial à développer, et il sera souvent plus rentable d'acquérir une bibliothèque C du commerce (de préférence avec son code source). Débutants en C, s'abstenir.

Sharam Hekmatpour : C++, a book and disk guide for C programmers (Prentiee-Hall, 1990). H.F. Korth & A.

Silberschatz : Database system concepts (Mc-Graw-Hill, 1986).

Robert Sedgewick : Algorithms (Addison-Wesley, 1983).