Qu'est-ce qu'un arbre B +?
Un arbre B + est principalement utilisé pour implémenter l'indexation dynamique sur plusieurs niveaux. Par rapport à B-Tree, l'arborescence B + stocke les pointeurs de données uniquement aux nœuds feuilles de l'arborescence, ce qui rend la recherche plus précise et plus rapide.
Dans ce didacticiel B + Tree, vous apprendrez:
- Qu'est-ce qu'un arbre B +?
- Règles pour B + Tree
- Pourquoi utiliser B + Tree
- Arbre B + contre Arbre B
- Opération de recherche
- Insérer une opération
- Supprimer l'opération
Règles pour B + Tree
Voici les règles essentielles pour B + Tree.
- Les feuilles sont utilisées pour stocker les enregistrements de données.
- Il est stocké dans les nœuds internes de l'arbre.
- Si une valeur de clé cible est inférieure au nœud interne, le point situé juste à gauche est suivi.
- Si une valeur de clé cible est supérieure ou égale au nœud interne, le point situé juste à droite est suivi.
- La racine a au moins 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 se 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 n'ont 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 complète de tous les éléments est un arbre qui n'a besoin que d'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 touches 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 les nœuds Leaf et internes. |
| La suppression n'est pas difficile car un élément n'est supprimé 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 les nœuds feuilles. |
Opération de recherche
Dans B + Tree, une recherche est l'une des procédures les plus simples à exécuter et en obtenir des résultats rapides et précis.
L'algorithme de recherche suivant est applicable:
- Pour trouver l'enregistrement requis, vous devez exécuter la recherche binaire sur les enregistrements disponibles dans l'arborescence.
- En cas de correspondance exacte avec la clé de recherche, l'enregistrement correspondant est renvoyé à l'utilisateur.
- Si la clé exacte n'est pas localisée par la recherche dans le nœud parent, courant ou feuille, un "message non trouvé" est affiché à l'utilisateur.
- Le processus de recherche peut être réexécuté pour des résultats meilleurs et plus précis.
Algorithme d'opération de recherche
1. Call the binary search method on the records in the B+ Tree.2. If the search parameters match the exact keyThe accurate result is returned and displayed to the userElse, if the node being searched is the current and the exact key is not found by the algorithmDisplay the statement "Recordset cannot be found."
Sortie :
L'enregistrement correspondant défini par rapport à la clé exacte est affiché à l'utilisateur; sinon, une tentative infructueuse est affichée à l'utilisateur.
Insérer une opération
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 ne soit pas trouvé, continuez à répéter le processus expliqué dans les étapes ci-dessus.
Insérer un algorithme d'opération
1. Even inserting at-least 1 entry into the leaf container does not make it full then add the record2. 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 treeb. 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 ci-dessus de l'arbre B + 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 qui doit faire partie de l'arbre.
- Pour ce faire, divisez le nœud, ajoutez 6 comme élément de 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 égales ou supérieures aux valeurs par rapport aux nœuds clé-valeur sur la droite.
Supprimer l'opération
La complexité de la procédure de suppression dans l'arborescence B + dépasse celle de la fonctionnalité d'insertion et de recherche.
L'algorithme suivant est applicable lors de la suppression d'un élément de l'arborescence 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 que le facteur satisfaisant d'être à moitié plein, alors l'opération est terminée; sinon, le nœud Feuille a des entrées minimales et ne peut pas être supprimé.
- Les autres nœuds liés à droite et à gauche peuvent quitter 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 à droite ou à gauche, les entrées de valeurs dans le nœud feuille ou 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'arborescence B + d'un ordre spécifique.
- Tout d'abord, les emplacements exacts de l'élément à supprimer sont identifiés dans l'arborescence.
- Ici, l'élément à supprimer ne peut être identifié avec précision qu'au niveau feuille et non à l'emplacement de l'index. Par conséquent, l'élément peut être supprimé sans affecter les règles de suppression, qui est 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 à la fois au niveau des nœuds Index et Leaf. 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 un index. Ainsi, 42 étant la seule valeur présente, elle deviendra l'indice.
Supprimer l'algorithme d'opération
1) Start at the root and go up to leaf node containing the key K2) Find the node n on the path from the root to the leaf node containing KA. If n is root, remove Ka. if root has more than one key, doneb. if root has only Ki) if any of its child nodes can lend a nodeBorrow key from the child and adjust child linksii) Otherwise merge the children nodes. It will be a new rootc. If n is an internal node, remove Ki) 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 nodeAdjust child linksElseMerge n with its siblingAdjust child linksd. If n is a leaf node, remove Ki) If n has at least ceil(M/2) elements, done!In case the smallest key is deleted, push up the next keyii) If n has less than ceil(m/2) elementsIf the sibling can lend a keyBorrow key from a sibling and adjust keys in n and its parent nodeElseMerge n and its siblingAdjust 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 de n et de ses nœuds parents si nécessaire.
Résumé:
- B + Tree est une structure de données auto-équilibrée 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 partielles, car passer par l'arborescence liée le rend efficace.
- L'arborescence B + se développe et se 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.