B+ TREE : Recherche, insertion et suppression Operations
Sarah Chen
⚡ Résumé intelligent
L'arbre B+ est un index dynamique multiniveau qui stocke les pointeurs de données uniquement au niveau des nœuds feuilles liés, ce qui permet des recherches précises et rapides. Cet article présente les règles de l'arbre B+, ses différences avec un arbre B classique, ainsi que les opérations de recherche, d'insertion et de suppression.
Qu’est-ce qu’un arbre B+ ?
A Arbre B+ Il est principalement utilisé pour implémenter l'indexation dynamique à plusieurs niveaux. Contrairement à un arbre B, l'arbre B+ stocke les pointeurs de données uniquement dans les nœuds feuilles, ce qui rend la recherche plus précise et plus rapide.
Règles pour l'arbre B+
Voici les règles essentielles pour un arbre de compétences B+.
- Les feuilles sont utilisées pour stocker des enregistrements de données.
- Les enregistrements sont stockés dans les nœuds internes de l'arbre.
- Si la valeur d'une clé cible est inférieure à celle du nœud interne, alors le pointeur situé juste à sa gauche est suivi.
- Si la valeur d'une clé cible est supérieure ou égale à celle du nœud interne, alors le pointeur situé juste à sa droite est suivi.
- La racine a au minimum deux enfants.
Pourquoi utiliser B+Tree
Voici les raisons d'utiliser un arbre B+ :
- Les clés servent principalement à faciliter la recherche en dirigeant vers la feuille appropriée.
- Un arbre B+ utilise un « facteur de remplissage » pour gérer la croissance et la décroissance 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.
- Un balayage complet de tous les éléments ne nécessite qu'un seul passage linéaire car tous les nœuds feuilles d'un arbre B+ sont liés entre eux.
Arbre B+ contre arbre B
Voici les principales différences entre un arbre B+ et un arbre B.
| 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 tous deux 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 les nœuds feuilles et les nœuds internes. |
| La suppression n'est pas difficile, car un élément n'est retiré que 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 un arbre B+, la recherche est l'une des procédures les plus faciles à exécuter et donne 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'arbre.
- 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. If 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 :
- Tout d'abord, 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, qui doit être intégrée à l'arbre.
- Pour ce faire, divisez le nœud et ajoutez 6 comme élément pointeur.
- Une hiérarchie arborescente droite est maintenant créée, et les valeurs de données restantes sont ajustées en conséquence par keeping en tenant compte des règles applicables de valeurs égales ou supérieures à celles des nœuds clé-valeur à 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 dans l'arbre une entrée feuille qui contient la clé et le pointeur, puis supprimer cette entrée feuille de l'arbre si elle remplit les conditions exactes de suppression d'enregistrement.
- Si le nœud feuille atteint seulement la moitié du seuil de remplissage, l'opération est terminée ; sinon, le nœud feuille contient un nombre minimal d'entrées et ne peut pas être supprimé.
- Les autres nœuds liés à droite et à gauche peuvent libérer leurs entrées et les déplacer vers la feuille. Si ces critères ne sont pas remplis, ils doivent fusionner le nœud feuille et le nœud auquel il est lié dans la hiérarchie de l'arbre.
- Lors de la fusion d'un nœud feuille avec ses voisins de droite ou de gauche, les valeurs contenues 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 permettant de supprimer un élément d'un 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 à son index. Par conséquent, sa suppression n'affecte pas les règles de suppression, qui correspondent à la valeur de la clé minimale.
- Dans l'exemple ci-dessus, nous devons supprimer 31 de l'arborescence.
- Nous devons localiser les occurrences de 31 dans l'index et la feuille.
- On constate que 31 est présent à la fois au niveau du nœud index et du nœud feuille. Par conséquent, nous le supprimons des deux instances.
- Mais nous devons renseigner l'index pointant vers 42. Nous allons maintenant examiner l'enfant de droite inférieur à 25, prendre sa valeur minimale et l'utiliser comme index. Ainsi, 42 étant la seule valeur présente, elle deviendra l'index.
Supprimer OperaAlgorithme de configuration
1) Start at the root and go up to the 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 des clés sont empruntées aux nœuds frères pour ajuster les valeurs dans n et ses nœuds parents si nécessaire.
