B+ Tree est une extension de B Tree qui permet des opérations efficaces d'insertion, de suppression et de recherche.
Dans B Tree, les clés et les enregistrements peuvent tous deux être stockés dans les nœuds internes et feuilles. Alors que, dans l'arborescence B+, les enregistrements (données) ne peuvent être stockés que sur les nœuds feuilles tandis que les nœuds internes ne peuvent stocker que les valeurs clés.
Les nœuds feuilles d'un arbre B+ sont liés entre eux sous la forme de listes à chaînage unique pour rendre les requêtes de recherche plus efficaces.
B+ Tree est utilisé pour stocker la grande quantité de données qui ne peuvent pas être stockées dans la mémoire principale. Du fait que la taille de la mémoire principale est toujours limitée, les nœuds internes (clés pour accéder aux enregistrements) de l'arborescence B+ sont stockés dans la mémoire principale tandis que les nœuds feuilles sont stockés dans la mémoire secondaire.
mon livecricket dans
Les nœuds internes de l’arbre B+ sont souvent appelés nœuds d’index. Un arbre B+ d’ordre 3 est représenté dans la figure suivante.
Avantages de l'arbre B+
- Les enregistrements peuvent être récupérés en un nombre égal d'accès au disque.
- La hauteur de l’arbre reste équilibrée et inférieure à celle de l’arbre B.
- Nous pouvons accéder aux données stockées dans un arbre B+ de manière séquentielle ou directe.
- Les clés sont utilisées pour l'indexation.
- Requêtes de recherche plus rapides car les données sont stockées uniquement sur les nœuds feuilles.
Arbre B VS Arbre B+
| SN | Arbre B | Arbre B+ |
|---|---|---|
| 1 | Les clés de recherche ne peuvent pas être stockées à plusieurs reprises. | Des clés de recherche redondantes peuvent être présentes. |
| 2 | Les données peuvent être stockées dans des nœuds feuilles ainsi que dans des nœuds internes | Les données ne peuvent être stockées que sur les nœuds feuilles. |
| 3 | La recherche de certaines données est un processus plus lent puisque les données peuvent être trouvées sur les nœuds internes ainsi que sur les nœuds feuilles. | La recherche est comparativement plus rapide car les données ne peuvent être trouvées que sur les nœuds feuilles. |
| 4 | La suppression des nœuds internes est si compliquée et prend du temps. | La suppression ne sera jamais un processus complexe puisque l'élément sera toujours supprimé des nœuds feuilles. |
| 5 | Les nœuds feuilles ne peuvent pas être liés entre eux. | Les nœuds feuilles sont liés entre eux pour rendre les opérations de recherche plus efficaces. |
Insertion dans l'arbre B+
Étape 1: Insérez le nouveau nœud en tant que nœud feuille
Étape 2: Si la feuille ne dispose pas de l'espace requis, divisez le nœud et copiez le nœud du milieu sur le nœud d'index suivant.
Étape 3: Si le nœud d'index ne dispose pas de l'espace requis, divisez le nœud et copiez l'élément du milieu sur la page d'index suivante.
Exemple :
Insérez la valeur 195 dans l'arbre B+ d'ordre 5 illustré dans la figure suivante.
java ajouter une chaîne
195 sera inséré dans le sous-arbre droit de 120 après 190. Insérez-le à la position souhaitée.
Le nœud contient plus d'éléments que le nombre maximum, c'est-à-dire 4, divisez-le donc et placez le nœud médian jusqu'au parent.
tuple java
Maintenant, le nœud d'index contient 6 enfants et 5 clés, ce qui viole les propriétés de l'arbre B+, nous devons donc le diviser, comme indiqué ci-dessous.
Suppression dans l'arborescence B+
Étape 1: Supprimez la clé et les données des feuilles.
Étape 2: si le nœud feuille contient moins que le nombre minimum d'éléments, fusionnez le nœud avec son frère et supprimez la clé entre eux.
Étape 3: si le nœud d'index contient moins que le nombre minimum d'éléments, fusionnez le nœud avec le frère et déplacez la clé entre eux.
Exemple
Supprimez la clé 200 de l’arborescence B+ illustrée dans la figure suivante.
200 est présent dans le sous-arbre droit de 190, après 195. supprimez-le.
Fusionnez les deux nœuds en utilisant 195, 190, 154 et 129.
Désormais, l'élément 120 est le seul élément présent dans le nœud qui viole les propriétés de l'arbre B+. Par conséquent, nous devons le fusionner en utilisant 60, 78, 108 et 120.
Désormais, la hauteur de l’arbre B+ sera diminuée de 1.
javafx sur éclipse
