B TREE dans la structure de données: exemple d'opération de recherche, d'insertion, de suppression

Table des matières:

Anonim

Qu'est-ce qu'un arbre B?

B Tree est une structure de données auto-équilibrée basée sur un ensemble spécifique de règles pour rechercher, insérer et supprimer les données d'une manière plus rapide et efficace en termes de mémoire. Pour ce faire, les règles suivantes sont suivies pour créer un arbre B.

Un B-Tree est un type spécial d'arbre dans une structure de données. En 1972, cette méthode a été introduite pour la première fois par McCreight, et Bayer l'a nommée Arbre de recherche m-way à hauteur équilibrée. Il vous aide à conserver les données triées et à permettre diverses opérations telles que l'insertion, la recherche et la suppression en moins de temps.

Dans ce didacticiel B-Tree, vous apprendrez:

  • Qu'est-ce qu'un arbre B?
  • Pourquoi utiliser B-Tree
  • Histoire de l'arbre B
  • Opération de recherche
  • Insérer une opération
  • Supprimer l'opération

Règles pour B-Tree

Voici les règles importantes pour créer B_Tree

  • Toutes les feuilles seront créées au même niveau.
  • B-Tree est déterminé par un certain nombre de degrés, qui est également appelé "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 se trouvent principalement les données.
  • Le sous-arbre gauche du nœud aura des valeurs moindres que le 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 = 4max keys: 4 - 1 = 3

  • Chaque nœud, à l'exception de la racine, doit contenir au minimum des clés de 
    [m/2]-1
    Par exemple: 
    m = 4min 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 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 traiter 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 à opter pour la lecture et l'écriture de gros blocs de données

Histoire de l'arbre B

  • Les données sont stockées sur le disque en 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 la consommation de temps et 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 résoudre ce problème, des tables d'index sont créées qui enregistrent la référence d'enregistrement des enregistrements en fonction des blocs dans lesquels elles résident. Cela réduit considérablement le temps et la consommation de mémoire.
  • Puisque nous avons d'énormes données, nous pouvons créer des tables d'index à plusieurs niveaux.
  • L'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.

Opération de recherche

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 gauche, si k est supérieur à la valeur racine, recherchez 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, passez à l'enfant avec une clé plus grande.
  • Si k n'est pas trouvé dans l'arbre, nous retournons NULL.

Insérer une opération

Puisque 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 le lieu d'insertion approprié.
  • Insérez la nouvelle clé à l'emplacement approprié, mais si le nœud a déjà un nombre maximum de clés:
  • Le nœud, avec une clé nouvellement insérée, sera séparé de l'élément du milieu.
  • L'élément du milieu deviendra le parent des deux autres nœuds enfants.
  • Les nœuds doivent réorganiser les clés dans l'ordre croissant.

ASTUCE

Ce qui suit n'est pas vrai à propos de l'algorithme d'insertion:

Puisque le nœud est plein, il se divisera, 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 a-t-il plus qu'é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 a-t-il plus d'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 se divisera et la clé du milieu deviendra le nœud racine des deux autres nœuds.
  • En cas de nombre pair de clés, le nœud du milieu sera sélectionné par biais à gauche ou à droite.

Dans l'exemple ci-dessus:

  • Le nœud a moins de clés max
  • 1 est inséré à côté de 3, mais la règle d'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 moins que la règle de clés max 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 des clés max.
  • Le nœud cible est divisé et la touche du milieu par biais à gauche est maintenant 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 des cas ci-dessus, le reste des valeurs peut être inséré facilement dans l'arbre B.

Supprimer l'opération

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 se trouve dans le nœud feuille

  • La cible est dans le nœud feuille, plus de clés min.
    • Supprimer cela ne violera pas la propriété de B Tree
  • La cible est dans le nœud feuille, elle a un minimum de nœuds clés
    • La suppression de ceci violera la propriété de B Tree
    • Le nœud cible peut emprunter la clé du nœud gauche immédiat ou du 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
  • La cible se trouve dans le nœud feuille, mais aucun frère n'a plus d'un nombre minimal 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 à min
    • 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

  • Soit choisir, prédécesseur dans l'ordre ou successeur dans l'ordre
  • Dans le cas du prédécesseur dans l'ordre, la clé maximale de son sous-arbre de 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 les clés min, 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 min, recherchez la clé minimale du successeur dans l'ordre.
  • Si le prédécesseur et le successeur dans l'ordre de la clé cible ont tous deux moins de clés min., 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 min, alors le nœud cible empruntera la valeur max à son frère via le parent du 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 montre différents cas d'opération de suppression dans un B-Tree. Cet arbre B 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 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 les clés minimales
  • Supprimez simplement la clé

Dans l'exemple ci-dessus:

  • Le nœud cible a des clés égales aux clés minimales, il ne peut donc pas le supprimer directement car il enfreindra les conditions

Maintenant, le diagramme suivant explique comment supprimer cette clé:

  • Le nœud cible empruntera une clé au frère immédiat, dans ce cas, 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 inorder 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 montre comment supprimer une clé qui a besoin d'une valeur de son successeur dans l'ordre.

  • Le nœud cible empruntera une clé au frère immédiat, dans ce cas, le successeur dans l'ordre (frère droit) car son prédécesseur dans l'ordre (frère gauche) a des clés égales au 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 qui peut donner sa clé au nœud cible. Par conséquent, la fusion est requise.

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 de fusion
  • Supprimer la clé cible du nœud fusionné

Supprimer le pseudo-code d'opération

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

Sortie :

Le plus gros élément est supprimé de l'arbre B.

Résumé:

  • B Tree est une structure de données auto-équilibrée pour une meilleure recherche, insertion et suppression des données du disque.
  • L'arbre B est régulé par le degré spécifié
  • B Les clés d'arbre et les nœuds sont classés par ordre croissant.
  • L'opération de recherche de B Tree est la plus simple, qui commence toujours à partir 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 assez 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 tels que les clés minimum et maximum du nœud cible, des frères et sœurs et du parent.