B+ TREE : Rechercher, Insérer et Supprimer OperaExemples

Qu’est-ce qu’un arbre B+ ?

A Arbre B+ est principalement utilisé pour mettre en œuvre une indexation dynamique à plusieurs niveaux. Par rapport au B-Tree, le B+ Tree stocke les pointeurs de données uniquement au niveau des nœuds feuilles de l'arbre, ce qui rend le processus de recherche plus précis et plus rapide.

Règles pour l'arbre B+

Voici les règles essentielles pour B+ Tree.

• Les feuilles sont utilisées pour stocker des enregistrements de données.
• Il est stocké dans les nœuds internes de l'Arbre.
• Si une valeur de clé cible est inférieure à celle du nœud interne, alors le point situé juste à son côté gauche est suivi.
• Si une valeur de clé cible est supérieure ou égale au nœud interne, alors le point situé juste à sa droite est suivi.
• La racine a au minimum deux enfants.

Pourquoi utiliser B+Tree

Voici les raisons d’utiliser B+ Tree :

• Les clés sont principalement utilisées pour faciliter la recherche en dirigeant vers la feuille appropriée.
• B+ Tree utilise un « facteur de remplissage » pour gérer l’augmentation et la diminution d’un arbre.
• Dans les arbres B+, de nombreuses clés peuvent facilement être placées sur la page de mémoire car elles ne possèdent pas les données associées aux nœuds intérieurs. Par conséquent, il accédera rapidement aux données de l’arborescence qui se trouvent sur le nœud feuille.
• Une analyse complète et complète de tous les éléments est un arbre qui ne nécessite qu'un seul passage linéaire car tous les nœuds feuilles d'un arbre B+ sont liés les uns aux autres.

Arbre B+ contre arbre B

Voici les principales différences entre B+ Tree et B Tree

Arbre B+	Arbre B
Les clés de recherche peuvent être répétées.	Les clés de recherche ne peuvent pas être redondantes.
Les données ne sont enregistrées que sur les nœuds feuilles.	Les nœuds feuilles et les nœuds internes peuvent stocker des données
Les données stockées sur le nœud feuille rendent la recherche plus précise et plus rapide.	La recherche est lente en raison des données stockées sur Leaf et les nœuds internes.
La suppression n'est pas difficile car un élément est uniquement supprimé d'un nœud feuille.	La suppression d'éléments est un processus compliqué et long.
Les nœuds feuilles liés rendent la recherche efficace et rapide.	Vous ne pouvez pas lier des nœuds feuilles.

Rechercher Operaproduction

Dans B+ Tree, une recherche est l’une des procédures les plus simples à exécuter et à obtenir des résultats rapides et précis.

L'algorithme de recherche suivant est applicable :

• Pour trouver l'enregistrement recherché, vous devez exécuter la commande recherche binaire sur les enregistrements disponibles dans l'Arbre.
• En cas de correspondance exacte avec la clé de recherche, l'enregistrement correspondant est renvoyé à l'utilisateur.
• Dans le cas où la clé exacte n'est pas localisée par la recherche dans le nœud parent, actuel ou feuille, alors un « message non trouvé » s'affiche à l'utilisateur.
• Le processus de recherche peut être réexécuté pour des résultats meilleurs et plus précis.

Rechercher OperaAlgorithme de configuration

 1. Call the binary search method on the records in the B+ Tree.
 2. If the search parameters match the exact key
            The accurate result is returned and displayed to the user
          Else, if the node being searched is the current and the exact key is not found by the algorithm
            Display the statement "Recordset cannot be found."

Sortie:

L'enregistrement correspondant à la clé exacte est affiché à l'utilisateur ; sinon, une tentative échouée est présentée à l'utilisateur.

insérer Operaproduction

L'algorithme suivant est applicable pour l'opération d'insertion :

• 50 pour cent des éléments des nœuds sont déplacés vers une nouvelle feuille pour le stockage.
• Le parent de la nouvelle feuille est lié avec précision à la valeur de clé minimale et à un nouvel emplacement dans l'arborescence.
• Divisez le nœud parent en plusieurs emplacements au cas où il serait pleinement utilisé.
• Désormais, pour de meilleurs résultats, la clé centrale est associée au nœud de niveau supérieur de cette feuille.
• Jusqu'à ce que le nœud de niveau supérieur soit introuvable, continuez à répéter le processus expliqué dans les étapes ci-dessus.

insérer OperaAlgorithme de configuration

1.	Even inserting at-least 1 entry into the leaf container does not make it full then add the record  
     2. Else, divide the node into more locations to fit more records.
      a. Assign a new leaf and transfer 50 percent of the node elements to a new placement in the tree
      b. The minimum key of the binary tree leaf and its new key address are associated with the top-level node.
      c. Divide the top-level node if it gets full of keys and addresses.
          i. Similarly,  insert a key in the center of the top-level node in the hierarchy of the Tree.
     d. Continue to execute the above steps until a top-level node is found that does not need to be divided anymore. 

3) Build a new top-level root node of 1 Key and 2 indicators.  

Sortie:

L'algorithme déterminera l'élément et l'insérera avec succès dans le nœud feuille requis.

L’exemple d’exemple d’arbre B+ ci-dessus est expliqué dans les étapes ci-dessous :

• Premièrement, nous avons 3 nœuds, et les 3 premiers éléments, qui sont 1, 4 et 6, sont ajoutés aux emplacements appropriés dans les nœuds.
• La valeur suivante dans la série de données est 12 et doit faire partie de l'arborescence.
• Pour y parvenir, divisez le nœud, ajoutez 6 comme élément pointeur.
• Désormais, une hiérarchie à droite d'un arbre est créée et les valeurs de données restantes sont ajustées en conséquence en gardant à l'esprit les règles applicables de valeurs égales ou supérieures à par rapport aux nœuds clé-valeur de droite.

Supprimer Operaproduction

La complexité de la procédure de suppression dans l'arborescence B+ dépasse celle des fonctionnalités d'insertion et de recherche.

L'algorithme suivant est applicable lors de la suppression d'un élément de l'arbre B+ :

• Tout d’abord, nous devons localiser une entrée feuille dans l’arborescence qui contient la clé et le pointeur. , supprimez l'entrée feuille de l'arborescence si la feuille remplit les conditions exactes de suppression d'enregistrement.
• Dans le cas où le nœud feuille ne satisfait qu'au facteur satisfaisant d'être à moitié plein, alors l'opération est terminée ; sinon, le nœud Leaf a un minimum d'entrées et ne peut pas être supprimé.
• Les autres nœuds liés à droite et à gauche peuvent libérer toutes les entrées puis les déplacer vers la Feuille. Si ces critères ne sont pas remplis, ils doivent alors combiner le nœud feuille et son nœud lié dans la hiérarchie arborescente.
• Lors de la fusion du nœud feuille avec ses voisins de droite ou de gauche, les entrées de valeurs dans le nœud feuille ou le voisin lié pointant vers le nœud de niveau supérieur sont supprimées.

L'exemple ci-dessus illustre la procédure pour supprimer un élément de l'arbre B+ d'un ordre spécifique.

• Tout d'abord, les emplacements exacts de l'élément à supprimer sont identifiés dans l'Arbre.
• Ici, l'élément à supprimer ne peut être identifié avec précision qu'au niveau de la feuille et non au niveau de l'emplacement de l'index. Par conséquent, l’élément peut être supprimé sans affecter les règles de suppression, qui sont la valeur de la clé minimale.

• Dans l'exemple ci-dessus, nous devons supprimer 31 de l'arborescence.
• Nous devons localiser les instances de 31 dans Index et Leaf.
• Nous pouvons voir que 31 est disponible au niveau des nœuds Index et Feuille. Par conséquent, nous le supprimons des deux instances.
• Mais nous devons remplir l'index pointant vers 42. Nous allons maintenant regarder le bon enfant de moins de 25 ans et prendre la valeur minimale et la placer comme index. Ainsi, 42 étant la seule valeur présente, elle deviendra l'indice.

Supprimer OperaAlgorithme de configuration

1) Start at the root and go up to leaf node containing the key K
2) Find the node n on the path from the root to the leaf node containing K
    A. If n is root, remove K
         a. if root has more than one key, done
         b. if root has only K
            i) if any of its child nodes can lend a node
               Borrow key from the child and adjust child links
            ii) Otherwise merge the children nodes. It will be a new root
         c. If n is an internal node, remove K
            i) If n has at least ceil(m/2) keys, done!
            ii) If n has less than ceil(m/2) keys,
                If a sibling can lend a key,
                Borrow key from the sibling and adjust keys in n and the parent node
                    Adjust child links
                Else
                    Merge n with its sibling
                    Adjust child links
         d. If n is a leaf node, remove K
            i) If n has at least ceil(M/2) elements, done!
                In case the smallest key is deleted, push up the next key
            ii) If n has less than ceil(m/2) elements
            If the sibling can lend a key
                Borrow key from a sibling and adjust keys in n and its parent node
            Else
                Merge n and its sibling
                Adjust keys in the parent node

Sortie:

La clé « K » est supprimée et les clés sont empruntées aux frères et sœurs pour ajuster les valeurs dans n et ses nœuds parents si nécessaire.

Résumé

• B+ Tree est un arbre auto-équilibré Structure de données pour exécuter des procédures de recherche, d'insertion et de suppression précises et plus rapides sur les données
• Nous pouvons facilement récupérer des données complètes ou des données partielles car le passage par l'arborescence liée le rend efficace.
• La structure arborescente B+ grandit et rétrécit avec une augmentation/diminution du nombre d'enregistrements stockés.
• Le stockage des données sur les nœuds feuilles et le branchement ultérieur des nœuds internes raccourcissent évidemment la hauteur de l'arborescence, ce qui réduit les opérations d'entrée et de sortie du disque, consommant finalement beaucoup moins d'espace sur les périphériques de stockage.