B TREE dans la structure de données : rechercher, insérer, supprimer OperaExemple de configuration

Règles pour B-Tree

Voici les règles importantes pour créer un B_Tree

• Toutes les feuilles seront créées au même niveau.
• B-Tree est déterminé par un certain nombre de degrés, également appelés « ordre » (spécifié par un acteur externe, comme un programmeur), appelé

  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 maximum de nœuds enfants qu'un nœud racine ainsi que ses nœuds enfants peuvent contenir sont calculés par cette formule :

  m – 1

  Par exemple :

  m = 4
  max keys: 4 – 1 = 3
  

• Chaque nœud, à l'exception de root, doit contenir au minimum des 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 B-Tree

• 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 bon choix lorsqu’il s’agit de lire et d’écrire de gros blocs de données

Histoire de l’arbre B

• Les données sont stockées sur le disque sous forme de blocs. Ces données, lorsqu'elles sont introduites dans la mémoire principale (ou RAM), sont appelées structure de données.
• En 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 principale en raison de la fréquence d'accès au disque et de la taille des données élevées.
• Pour surmonter ce problème, des tables d'index sont créées qui enregistrent la référence des enregistrements en fonction des blocs dans lesquels ils résident. Cela réduit considérablement le temps 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 à plusieurs niveaux peut être conçu à l'aide de B Tree pour conserver 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 B Tree.

L'algorithme suivant est appliqué :

• Soit la clé (la valeur) à rechercher par « k ».
• Commencez la recherche à partir de la racine et parcourez récursivement vers le bas.
• Si k est inférieur à la valeur racine, recherchez le sous-arbre de gauche, si k est supérieur à la valeur racine, recherchez le sous-arbre de droite.
• 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

Étant donné que B Tree est un arbre auto-équilibré, vous ne pouvez 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.

ASTUCE

Ce qui suit n'est pas vrai concernant l'algorithme d'insertion : Puisque le nœud est plein, il sera divisé, puis une nouvelle valeur sera insérée

Dans l'exemple ci-dessus:

• Recherchez la position appropriée dans le nœud pour 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 supérieur ou égal à un nombre minimum de clés, qui est 1 ? Dans ce cas, oui, c'est le cas. Vérifiez la règle suivante.
• Après l'insertion, le nœud possède-t-il plus qu'un nombre maximum de clés, qui est de 3 ? Dans ce cas, non, ce n’est pas le cas. Cela signifie que l'arbre B ne viole aucune règle et que l'insertion est terminée.

Dans l'exemple ci-dessus:

• Le nœud a atteint le nombre maximum de clés
• Le nœud sera divisé et la clé du milieu deviendra le nœud racine des deux nœuds restants.
• En cas de nombre pair de clés, le nœud du milieu sera sélectionné par biais gauche ou biais droit.

Dans l'exemple ci-dessus:

• Le nœud a moins que le nombre maximum de clés
• 1 est inséré à côté de 3, mais la règle de l'ordre croissant n'est pas respectée
• Afin de résoudre ce problème, les clés sont triées

De même, 13 et 2 peuvent être insérés facilement dans le nœud car ils remplissent la règle des clés inférieures au nombre maximum 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 viole la règle du nombre maximum 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 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 est dans le nœud feuille, plus de minutes de clés.
• La suppression de ceci ne violera pas la propriété de B Tree
• Target est dans le nœud feuille, il a un minimum de nœuds clés
• La suppression de ceci violerait la propriété de B Tree
• Target le nœud peut emprunter la clé au nœud gauche immédiat ou au nœud droit immédiat (frère)
• Le frère dira oui s'il a plus que le nombre minimum de clés
• La clé sera empruntée au nœud parent, la valeur maximale sera transférée à un parent, la valeur maximale du nœud parent sera transférée au nœud cible et supprimera la valeur cible
• Target se trouve dans le nœud feuille, mais aucun frère ou sœur n'a plus que le nombre minimum de clés
• Rechercher une clé
• Fusionner avec les frères et sœurs et le minimum de nœuds parents
• Le nombre total de clés sera désormais supérieur au minimum
• 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 dans l'ordre, la clé maximale de son sous-arbre gauche sera sélectionnée
• En cas de successeur dans l'ordre, la clé minimale de son sous-arbre droit sera sélectionnée
• Si le prédécesseur dans l'ordre de la clé cible a plus que le nombre minimum de clés, alors seulement il peut remplacer la clé cible par le maximum du prédécesseur dans l'ordre.
• Si le prédécesseur dans l'ordre de la clé cible n'a pas plus de clés minimales, recherchez la clé minimale du successeur dans l'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 maximum du sous-arbre prédécesseur dans l'ordre
• Si, après la suppression, la cible a moins de clés minimales, alors le nœud cible empruntera la valeur maximale à son frère via le parent de son frère.
• La valeur max du parent sera prise par une cible, mais avec les nœuds de la valeur max du frère.

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

Le diagramme ci-dessus affiche différents cas d'opération de suppression dans un B-Tree. Ce B-Tree est d'ordre 5, ce qui signifie que le nombre minimum de nœuds enfants qu'un nœud peut avoir est de 3, et le nombre maximum de nœuds enfants qu'un nœud peut avoir est de 5. Alors que le nombre minimum et maximum de clés pour tout nœud peuvent avoir respectivement 2 et 4.

Dans l'exemple ci-dessus:

• Le nœud cible a la clé cible à supprimer
• Le nœud cible a plus de clés que le nombre minimum de clés
• Supprimez simplement la clé

Dans l'exemple ci-dessus:

• Le nœud cible a des clés égales au minimum de clés, il ne peut 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é au frère immédiat, dans ce cas, au 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 inorder sera transférée au parent, et le parent transférera la valeur maximale au nœud cible (voir le schéma 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é au frère immédiat, dans ce cas, au successeur dans l'ordre (frère droit), car son prédécesseur dans l'ordre (frère gauche) a des clés égales au nombre minimum de clés.
• 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 n'a aucun frère pouvant donner sa clé au nœud cible. Une fusion est donc nécessaire.

Voir la procédure de suppression d'une telle clé :

• Fusionner le nœud cible avec l'un de ses frères et sœurs immédiats avec la clé parent
• La clé du nœud parent est sélectionnée pour que les frères et sœurs se trouvent entre les deux nœuds qui fusionnent.
• Supprimez la clé cible du nœud fusionné

Supprimer OperaPseudo 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.

Résumé

• B Tree est une structure de données auto-équilibrée pour une meilleure recherche, insertion et suppression de données du disque.
• L'arbre B est réglementé par le degré spécifié
• Les clés et nœuds de l'arborescence B sont classés par ordre croissant.
• L'opération de recherche de B Tree est la plus simple, elle part toujours de la racine et commence à vérifier si la clé cible est supérieure ou inférieure à la valeur du nœud.
• L'opération d'insertion de B Tree est plutôt détaillée, qui trouve d'abord une position d'insertion appropriée pour la clé cible, l'insère, évalue la validité de B Tree par rapport à différents cas, puis restructure les nœuds B Tree en conséquence.
• L'opération de suppression de B Tree recherche d'abord la clé cible à supprimer, la supprime, évalue la validité en fonction de plusieurs cas comme les clés minimales et maximales du nœud cible, des frères et sœurs et du parent.