Arbre B dans les structures de données : Recherche, Insertion, Suppression

Qu’est-ce qu’un arbre B ?

Arbre B Un arbre B est une structure de données auto-équilibrée, basée sur un ensemble de règles spécifiques permettant de rechercher, d'insérer et de supprimer des données de manière plus rapide et économe en mémoire. Pour ce faire, les règles suivantes sont appliquées lors de la création d'un arbre B.

Un arbre B est un type particulier d'arbre dans une structure de données. Cette méthode a été introduite en 1972 par McCreight et Bayer, qui l'ont nommée arbre de recherche à hauteur équilibrée (m-way Search Tree). Elle permet de conserver des données triées et accélère diverses opérations telles que l'insertion, la recherche et la suppression.

Règles pour B-Tree

Voici les règles importantes pour créer un arbre B :

• Toutes les feuilles seront créées au même niveau.
• Un arbre B est déterminé par un nombre de degrés, également appelé « ordre » (spécifié par un acteur externe, comme un programmeur), désigné par m À partir de. La valeur de m dépend de la taille du bloc sur le disque sur lequel les données se trouvent principalement.
• Le sous-arbre gauche du nœud aura des valeurs inférieures à celles du côté droit du sous-arbre. Cela signifie que les nœuds sont également triés par ordre croissant de gauche à droite.
• Le nombre maximal de clés qu'un nœud racine, ainsi que ses nœuds enfants, peuvent contenir est calculé par la formule suivante : m − 1. Par exemple:

  m = 4
  max keys: 4 − 1 = 3

• Chaque nœud, à l'exception de la racine, doit contenir un nombre minimum de clés de [m/2] − 1. Par exemple:

  m = 4
  min keys: 4/2 − 1 = 1

• Le nombre maximum de nœuds enfants qu'un nœud peut avoir est égal à son degré, qui est m.
• Le nombre minimum d'enfants qu'un nœud peut avoir est la moitié de l'ordre, soit m/2 (la valeur plafond est prise).
• Toutes les clés d'un nœud sont triées par ordre croissant.

Pourquoi utiliser B-Tree

Voici les raisons d'utiliser un arbre B :

• Réduit le nombre de lectures effectuées sur le disque.
• Les arbres B peuvent être facilement optimisés pour ajuster leur taille (c'est-à-dire le nombre de nœuds enfants) en fonction de la taille du disque.
• Il s’agit d’une technique spécialement conçue pour gérer une quantité volumineuse de données.
• C'est un algorithme utile pour les bases de données et les systèmes de fichiers.
• Un excellent choix pour la lecture et l'écriture de gros volumes de données.

Histoire de l’arbre B

• Les données sont stockées sur le disque par blocs. Ces données, lorsqu'elles sont chargées en mémoire vive (ou RAM), sont appelées une structure de données.
• Dans le cas de données volumineuses, la recherche d'un enregistrement sur le disque nécessite la lecture de l'intégralité du disque ; cela augmente le temps et la consommation de mémoire vive en raison de la fréquence élevée d'accès au disque et de la taille des données.
• Pour pallier ce problème, des tables d'index sont créées afin de sauvegarder la référence des enregistrements en fonction des blocs dans lesquels ils se trouvent. Cela réduit considérablement le temps de traitement et la consommation de mémoire.
• Puisque nous disposons d’énormes données, nous pouvons créer des tables d’index à plusieurs niveaux.
• Un index multiniveau peut être conçu en utilisant un arbre B pour la conservation des données.ping les données triées de manière auto-équilibrée.

Rechercher Operaproduction

L'opération de recherche est l'opération la plus simple sur un arbre B. L'algorithme suivant est appliqué :

• Soit « k » la clé (la valeur) à rechercher.
• Commencez la recherche à partir de la racine et parcourez récursivement vers le bas.
• Si k est inférieur à la valeur de la racine, recherchez dans le sous-arbre gauche ; si k est supérieur à la valeur de la racine, recherchez dans le sous-arbre droit.
• Si le nœud a le k trouvé, renvoyez simplement le nœud.
• Si le k n'est pas trouvé dans le nœud, descendez jusqu'à l'enfant avec une clé plus grande.
• Si k n'est pas trouvé dans l'arbre, nous renvoyons NULL.

insérer Operaproduction

Puisqu'un arbre B est un arbre auto-équilibré, on ne peut pas forcer l'insertion d'une clé dans n'importe quel nœud. L'algorithme suivant s'applique :

• Exécutez l'opération de recherche et trouvez l'endroit d'insertion approprié.
• Insérez la nouvelle clé au bon endroit, mais si le nœud dispose déjà d'un nombre maximum de clés :
• Le nœud, ainsi qu'une clé nouvellement insérée, seront séparés de l'élément central.
• L'élément du milieu deviendra le parent des deux autres nœuds enfants.
• Les nœuds doivent réorganiser les clés par ordre croissant.

Dans l'exemple ci-dessus:

• Recherchez la position appropriée dans le nœud pour trouver la clé.
• Insérez la clé dans le nœud cible et vérifiez les règles.
• Après l'insertion, le nœud possède-t-il un nombre de clés supérieur ou égal au minimum requis (1) ? Si c'est le cas, oui. Consultez la règle suivante.
• Après l'insertion, le nœud possède-t-il plus de trois clés (le nombre maximal autorisé) ? Dans ce cas, non. Cela signifie que l'arbre B respecte toutes les règles et que l'insertion est terminée.

Dans l'exemple ci-dessus:

• Le nœud a atteint le nombre maximal de clés.
• Le nœud se divisera, et la clé centrale deviendra le nœud racine des deux autres nœuds.
• En cas de nombre pair de clés, le nœud central sera sélectionné par biais gauche ou biais droit.

Dans l'exemple ci-dessus:

• Le nœud possède moins de clés que le nombre maximal.
• Le chiffre 1 est inséré à côté du 3, mais la règle de l'ordre croissant n'est pas respectée.
• Pour remédier à cela, les clés sont triées.

De même, 13 et 2 peuvent être facilement insérés dans le nœud car ils remplissent la règle « moins que le nombre maximal de clés » pour les nœuds.

Dans l'exemple ci-dessus:

• Le nœud a des clés égales au nombre maximum de clés.
• La clé est insérée dans le nœud cible, mais elle enfreint la règle du nombre maximal de clés.
• Le nœud cible est divisé et la clé du milieu par biais gauche est désormais le parent des nouveaux nœuds enfants.
• Les nouveaux nœuds sont classés par ordre croissant.

De même, sur la base des règles et cas ci-dessus, le reste des valeurs peut être facilement inséré dans l’arbre B.

Supprimer Operaproduction

L'opération de suppression comporte plus de règles que les opérations d'insertion et de recherche. L'algorithme suivant s'applique :

• Exécutez l'opération de recherche et trouvez la clé cible dans les nœuds.
• Trois conditions sont appliquées en fonction de l'emplacement de la clé cible, comme expliqué dans les sections suivantes.

Si la clé cible est dans le nœud feuille

• Target Le nœud feuille contient plus de clés que le minimum requis. Sa suppression ne violera pas la propriété de l'arbre B.
• Target se trouve dans le nœud feuille et possède des nœuds de clé minimale. Supprimer ce nœud violerait une propriété de l'arbre B.
• Le nœud cible peut emprunter une clé au nœud immédiatement à gauche ou au nœud immédiatement à droite (frère).
• Le frère dira oui si elle comporte plus que le nombre minimum de clés.
• La clé sera empruntée au nœud parent, la valeur maximale sera transférée au parent, la valeur maximale du nœud parent sera transférée au nœud cible, et la valeur cible sera supprimée.
• Target est dans le nœud feuille, mais aucun frère n'a plus que le nombre minimum de clés : rechercher la clé, fusionner avec les frères et sœurs et le minimum des nœuds parents, le nombre total de clés sera maintenant supérieur au minimum, et la clé cible sera remplacée par le minimum d'un nœud parent.

Si la clé cible se trouve dans un nœud interne

• Choisissez soit un prédécesseur dans l'ordre, soit un successeur dans l'ordre.
• Dans le cas d'un prédécesseur en ordre, la clé maximale de son sous-arbre gauche sera sélectionnée.
• Dans le cas d'un successeur en ordre, la clé minimale de son sous-arbre droit sera sélectionnée.
• Si le prédécesseur en ordre de la clé cible comporte plus de clés que le nombre minimal, alors seulement elle peut remplacer la clé cible par la valeur maximale du prédécesseur en ordre.
• Si le prédécesseur en ordre de la clé cible ne possède pas plus de clés minimales, recherchez la clé minimale du successeur en ordre.
• Si le prédécesseur et le successeur de la clé cible ont tous deux moins de clés, fusionnez le prédécesseur et le successeur.

Si la clé cible se trouve dans un nœud racine

• Remplacer par l'élément maximal du sous-arbre prédécesseur en ordre.
• Si, après suppression, la cible possède moins de clés minimales, alors le nœud cible empruntera la valeur maximale à son frère via le parent de ce dernier.
• La valeur maximale du parent sera prise par la cible, mais avec les nœuds de la valeur maximale du frère.

Maintenant, comprenons l'opération de suppression avec un exemple.

Le diagramme ci-dessus illustre différents cas de l'opération de suppression dans un arbre B. Cet arbre B est d'ordre 5, ce qui signifie que chaque nœud peut avoir au minimum 3 enfants et au maximum 5. Par ailleurs, chaque nœud peut avoir au minimum 2 clés et au maximum 4.

Dans l'exemple ci-dessus:

• Le nœud cible possède la clé cible à supprimer.
• Le nœud cible possède plus de clés que le nombre minimum de clés.
• Il suffit de supprimer la clé.

Dans l'exemple ci-dessus:

• Le nœud cible possède des clés égales au nombre minimum de clés, nous ne pouvons donc pas le supprimer directement car cela violerait les conditions.

Maintenant, le schéma suivant explique comment supprimer cette clé :

• Le nœud cible empruntera une clé à un frère immédiat, en l'occurrence le prédécesseur dans l'ordre (frère gauche), car il n'a pas de successeur dans l'ordre (frère droit).
• La valeur maximale du prédécesseur dans l'ordre sera transférée au parent, et le parent transférera la valeur maximale au nœud cible (voir le diagramme ci-dessous).

L'exemple suivant illustre comment supprimer une clé qui nécessite une valeur de son successeur dans l'ordre.

• Le nœud cible empruntera une clé à un frère immédiat, en l'occurrence le successeur dans l'ordre (frère de droite), car son prédécesseur dans l'ordre (frère de gauche) possède des clés égales aux clés minimales.
• La valeur minimale du successeur dans l'ordre sera transférée au parent, et le parent transférera la valeur maximale au nœud cible.

Dans l'exemple ci-dessous, le nœud cible ne possède aucun nœud frère pouvant lui fournir sa clé. Une fusion est donc nécessaire. Consultez la procédure de suppression d'une telle clé :

• Fusionnez le nœud cible avec l'un de ses frères et sœurs immédiats ainsi qu'avec la clé parente.
• La clé du nœud parent sélectionné se situe entre les deux nœuds de fusion.
• Supprimez la clé cible du nœud fusionné.

Supprimer Operation Pseudo Code

private int removeBiggestElement()
{
    if (root has no child)
        remove and return the last element
    else {
        answer = subset[childCount-1].removeBiggestElement()
        if (subset[childCount-1].dataCount < MINIMUM)
            fixShort (childCount-1)
        return answer
    }
}

Sortie : Le plus gros élément est supprimé du B-Tree.

FAQ