Dans le didacticiel suivant, nous découvrirons la structure de données B Tree et envisagerons de la visualiser.
Alors, commençons.
Qu’est-ce qu’un arbre B ?
Le Arbre B est un type spécial d'arbre de recherche multidirectionnel , communément appelé le voie M arbre qui s'équilibre. En raison de leur structure équilibrée, ces arbres sont couramment utilisés pour exploiter et gérer d’immenses bases de données et simplifier les recherches. Dans un arbre B, chaque nœud peut avoir au plus n nœuds enfants. B Tree est un exemple d'indexation multiniveau dans un système de gestion de base de données (SGBD). Les nœuds feuilles et internes auront tous deux des références d’enregistrement. L'arbre B est connu sous le nom d'arbre stocké équilibré car tous les nœuds feuilles sont au même niveau.
Le diagramme suivant est un exemple d’arbre B :
Figure 1. A B Arbre d’ordre 3
Comprendre les règles de l'arbre B
Voici les propriétés importantes d’un arbre B :
- Tous les nœuds feuilles sont au même niveau.
- La structure de données B Tree est définie par le terme degré minimum « d ». La valeur de « d » dépend de la taille du bloc de disque.
- Chaque nœud, à l'exclusion de la racine, doit être constitué d'au moins d-1 clés. Le nœud racine peut être constitué d’au moins 1 clé.
- Tous les nœuds (y compris le nœud racine) peuvent être constitués d'au plus (2j-1) clés.
- Le nombre d'enfants d'un nœud est égal au ajout du nombre de clés présentes dedans et .
- Toutes les clés d'un nœud sont triées par ordre croissant. L'enfant entre deux clés, k1 et k2, est constitué de toutes les clés comprises respectivement entre k1 et k2.
- Contrairement à l'arbre de recherche binaire, la structure de données de l'arbre B croît et rétrécit à partir de la racine. Alors que l’arbre de recherche binaire croît vers le bas et se rétrécit vers le bas.
- Semblable à d'autres arbres de recherche binaires auto-équilibrés, la complexité temporelle de la structure de données de l'arbre B pour les opérations telles que la recherche, l'insertion et la suppression est O(log?n) .
- L'insertion d'un nœud dans l'arbre B se produit uniquement au niveau du nœud feuille.
Considérons l'exemple suivant d'un arbre B d'ordre minimum 5.
Figure 2. A B Arbre d'ordre 5
Remarque : la valeur de la commande minimum est bien supérieure à 5 dans un B Trees pratique.
Dans le diagramme ci-dessus, nous pouvons observer que tous les nœuds feuilles sont au même niveau et que tous les nœuds non-feuilles n'ont pas de sous-arbre vide et sont constitués de clés une de moins que le nombre de leurs enfants.
La formulation définie des règles du B Tree :
Chaque arbre B dépend d'un entier constant positif appelé LE MINIMUM , qui est utilisé afin de déterminer le nombre d'éléments de données pouvant être conservés dans un seul nœud.
Règle 1: La racine peut avoir seulement un seul élément de données (ou même aucun élément de données s'il n'y a pas non plus d'enfants) ; chaque autre nœud a au moins LE MINIMUM éléments de données.
Règle 2 : Le nombre maximum d'éléments de données stockés dans un nœud est le double de la valeur de LE MINIMUM .
java si sinon
Règle 3 : Les éléments de données de chaque nœud du B Tree sont stockés dans un tableau partiellement rempli, trié à partir du plus petit élément de données (à l'index 0 ) au plus grand élément de données (à la position finale utilisée du tableau).
Règle 4 : Le nombre total de sous-arbres sous un nœud non-feuille est toujours un de plus que le nombre d'éléments de données dans ce nœud.
- sous-arbre 0,sous-arbre 1,...
Règle 5 : Par rapport à tout nœud non-feuille :
- Un élément de données à l'index est supérieur à tous les éléments de données du numéro de sous-arbre je du nœud, et
- Un élément de données à l'index est inférieur à tous les éléments de données du numéro de sous-arbre je+1 du nœud.
Règle 6 : Chaque feuille d'un arbre B a la même profondeur. Ainsi, cela garantit qu’un arbre B évite le problème d’un arbre déséquilibré.
Opérations sur une structure de données B Tree
Afin de garantir qu'aucune des propriétés d'une structure de données B Tree n'est violée lors des opérations, le B Tree peut être divisé ou joint. Voici quelques opérations que nous pouvons effectuer sur un arbre B :
- Recherche d'un élément de données dans B Tree
- Insertion d'une donnée dans B Tree
- Suppression d'une donnée dans B Tree
Opération de recherche sur un arbre B
La recherche d’un élément dans un arbre B est similaire à celle dans un arbre de recherche binaire. Mais au lieu de prendre une décision bidirectionnelle (gauche ou droite) comme un arbre de recherche binaire, un arbre B prend une décision dans plusieurs sens à chaque nœud, où m est le nombre d'enfants du nœud.
Étapes pour rechercher un élément de données dans un arbre B :
Étape 1: La recherche commence à partir du nœud racine. Comparez l'élément de recherche, k, avec la racine.
Étape 1.1 : Si le nœud racine est constitué de l’élément k, la recherche sera terminée.
Étape 1.2 : Si l'élément k est inférieur à la première valeur de la racine, nous nous déplacerons vers l'enfant le plus à gauche et rechercherons l'enfant de manière récursive.
Étape 1.3.1 : Si la racine n’a que deux enfants, nous nous déplacerons vers l’enfant le plus à droite et rechercherons récursivement les nœuds enfants.
Étape 1.3.2 : Si la racine a plus de deux clés, nous rechercherons le reste.
Étape 2: Si l'élément k n'est pas trouvé après avoir parcouru tout l'arbre, alors l'élément de recherche n'est pas présent dans l'arbre B.
point np
Visualisons les étapes ci-dessus à l'aide d'un exemple. Supposons que nous voulions rechercher une clé k=34 dans l’arbre B suivant :
Graphique 3.1. Un arbre B donné
- Tout d'abord, nous vérifierons si la clé k = 34 est au nœud racine. Puisque la clé n’est pas à la racine, nous allons passer à ses nœuds enfants. On peut également observer que le nœud racine a deux enfants ; par conséquent, nous comparerons la valeur requise entre les deux clés.
Graphique 3.2. La clé k n'est pas présente à la racine - Maintenant que nous pouvons remarquer que la clé k est supérieure au nœud racine, c'est-à-dire 30, nous allons procéder avec le bon enfant de la racine.
Graphique 3.3. La clé k > 30, passe à l'enfant droit - Nous allons maintenant comparer la clé k avec les valeurs présentes sur le nœud, soit respectivement 40 et 50. Puisque la clé k est inférieure à la clé gauche, c'est-à-dire 40, nous allons nous déplacer vers l'enfant gauche du nœud.
Graphique 3.4. La clé k<40, move to left child< li> - Étant donné que la valeur 40 dans l'enfant de gauche est 34, ce qui est la valeur requise, nous pouvons conclure que la clé est trouvée et que l'opération de recherche est terminée.
Graphique 3.4. La clé k = 34, l'enfant gauche de 40
Nous avons comparé la clé avec quatre valeurs différentes dans l'exemple ci-dessus jusqu'à ce que nous la trouvions. Ainsi, la complexité temporelle requise pour l’opération de recherche dans un arbre B est O(log?n) .
Insertion d'une opération sur un arbre B
Lors de l'insertion d'un élément de données dans un arbre B, nous devons d'abord vérifier si cet élément est déjà présent dans l'arbre ou non. Si l'élément de données est trouvé dans l'arborescence B, l'opération d'insertion n'a pas lieu. Cependant, si ce n’est pas le cas, nous poursuivrons l’insertion. Il y a deux scénarios à prendre en compte lors de l'insertion d'un élément dans le nœud feuille :
Étapes pour insérer un élément de données dans un arbre B :
Étape 1: Nous commencerons par calculer le nombre maximum de clés dans le nœud en fonction de l’ordre du B Tree.
Étape 2: Si l'arborescence est vide, un nœud racine est alloué et nous insérerons la clé qui fait office de nœud racine.
Étape 3: Nous allons maintenant rechercher le nœud applicable pour l'insertion.
Étape 4: Si le nœud est plein :
Étape 4.1 : Nous insérerons les éléments de données par ordre croissant.
Étape 4.2 : Si les éléments de données sont supérieurs au nombre maximum de clés, nous diviserons le nœud complet à la médiane.
Étape 4.3 : Nous allons pousser la touche médiane vers le haut et diviser les touches gauche et droite en enfants gauche et droit.
statut git -s
Étape 5 : Si le nœud n'est pas plein, nous insérerons le nœud par ordre croissant.
Visualisons les étapes ci-dessus à l'aide d'un exemple. Supposons que nous devions créer un arbre B d’ordre 4. Les éléments de données à insérer dans l’arbre B sont 5,3,21,11,1,16,8,13,4 et 9 .
- Puisque m est égal à 3, le nombre maximum de clés pour un nœud = m-1 = 3-1 = 2 .
- Nous commencerons par insérer 5 dans l'arbre vide.
Graphique 4.1. Insérer 5 - Nous allons maintenant en insérer 3 dans l’arbre. Puisque 3 est inférieur à 5, nous allons insérer 3 à gauche de 5 dans le même nœud.
Graphique 4.2. Insérer 3 - Nous allons maintenant insérer 21 dans l'arbre, et comme 21 est supérieur à 5, il sera inséré à droite de 5 dans le même nœud. Cependant, comme on sait que le nombre maximum de clés dans le nœud est de 2, une de ces clés sera déplacée vers un nœud au-dessus afin de la diviser. Ainsi, 5, l'élément de données du milieu, montera, et 3 et 21 deviendront respectivement ses nœuds gauche et droit.
Graphique 4.3. Insérer 21 - Il est maintenant temps d'insérer l'élément de données suivant, c'est-à-dire 11, qui est supérieur à 5 mais inférieur à 21. Par conséquent, 11 sera inséré comme clé à gauche du nœud composé de 21 comme clé.
Graphique 4.4. Insérer 11 - De même, nous insérerons l'élément de données suivant 1 dans l'arborescence, et comme nous pouvons l'observer, 1 est inférieur à 3 ; par conséquent, il sera inséré comme clé à gauche du nœud composé de 3 comme clé.
Graphique 4.5. Insérer 1 - Maintenant, nous allons insérer l'élément de données 16 dans l'arborescence, qui est supérieur à 11 mais inférieur à 21. Cependant, le nombre de clés dans ce nœud dépasse le nombre maximum de clés. Par conséquent, le nœud se divisera, déplaçant la clé du milieu vers la racine. Par conséquent, 16 sera inséré à droite du 5, divisant 11 et 21 en deux nœuds distincts.
Graphique 4.6. Insérer 16 - La donnée 8 sera insérée en clé à gauche de 11.
Graphique 4.7. Insérer 8 - Nous allons insérer 13 dans l'arborescence, qui est inférieur à 16 et supérieur à 11. Par conséquent, l'élément de données 13 doit être inséré à droite du nœud composé de 8 et 11. Cependant, puisque le nombre maximum de clés dans l'arborescence peut ne soit que 2, une division se produira, déplaçant l'élément de données du milieu 11 vers le nœud ci-dessus et 8 et 13 en deux nœuds séparés. Désormais, le nœud ci-dessus sera composé de 5, 11 et 16, ce qui dépasse encore une fois le nombre maximum de clés. Par conséquent, il y aura une autre division, faisant de l’élément de données 11 le nœud racine avec 5 et 16 comme enfants.
Graphique 4.8. Insérer 13 - Puisque l'élément de données 4 est inférieur à 5 mais supérieur à 3, il sera inséré à droite du nœud composé de 1 et 3, ce qui dépassera à nouveau le nombre maximum de clés dans un nœud. Par conséquent, un déversement se produira à nouveau, déplaçant le 3 vers le nœud supérieur à côté du 5.
Graphique 4.9. Insérer 4 - Enfin, la donnée 9, qui est supérieure à 8 mais inférieure à 11, sera insérée à droite du nœud constitué de 8 en guise de clé.
Graphique 4.10. Insérer 9
Dans l'exemple ci-dessus, nous avons effectué différentes comparaisons. La première valeur a été directement insérée dans l'arborescence ; après cela, chaque valeur devait être comparée aux nœuds disponibles dans cet arbre. La complexité temporelle de l'opération d'insertion dans un arbre B dépend du nombre de nœuds et de .
Suppression d'une opération sur un arbre B
La suppression d'un élément de données sur un B Tree contient trois événements principaux :
- Rechercher le nœud où existe la clé à supprimer,
- Supprimer la clé, et
- Équilibrer l'arbre, si nécessaire.
Lors de la suppression d'un élément de l'arborescence, une condition appelée Underflow peut se produire. Un dépassement de capacité se produit lorsqu'un nœud comprend moins que le nombre minimum de clés ; ça devrait tenir.
Voici quelques termes à comprendre avant de visualiser l’opération de suppression/suppression :
Voici trois cas marquants d’opération de suppression dans un arbre B :
Cas 1 : La suppression/suppression de la clé se situe dans le nœud Feuille - Ce cas est ensuite divisé en deux cas différents :
1. La suppression/suppression de la clé ne viole pas la propriété du nombre minimum de clés qu'un nœud doit détenir.
Visualisons ce cas à l'aide d'un exemple où nous supprimerons la clé 32 du B Tree suivant.
Graphique 4.1 : Suppression d'une clé de nœud feuille (32) de l'arbre B
Comme nous pouvons le constater, supprimer 32 de cet arbre ne viole pas la propriété ci-dessus.
2. La suppression/suppression de la clé viole la propriété du nombre minimum de clés qu'un nœud doit détenir. Dans ce cas, nous devons emprunter une clé à son nœud frère le plus proche dans l’ordre de gauche à droite.
Tout d’abord, nous rendrons visite à son frère proche de gauche. Si le nœud frère gauche possède plus d’un nombre minimum de clés, il empruntera une clé à ce nœud.
Sinon, nous vérifierons pour emprunter au nœud frère droit le plus proche.
Visualisons maintenant ce cas à l'aide d'un exemple où nous supprimerons 31 de l'arbre B ci-dessus. Dans ce cas, nous emprunterons une clé au nœud frère gauche.
Figure 4.2 : Suppression d'une clé de nœud feuille (31) de l'arbre B
Si les deux nœuds frères proches contiennent déjà un nombre minimum de clés, nous fusionnerons le nœud avec le nœud frère gauche ou celui de droite. Ce processus de fusion s'effectue via le nœud parent.
Visualisons à nouveau en supprimant la clé 30 de l'arbre B ci-dessus.
Graphique 4.3 : Suppression d'une clé de nœud feuille (30) de l'arbre B
python ou
Cas 2 : la suppression/suppression de la clé réside dans le nœud non-Leaf - Ce cas est ensuite divisé en différents cas :
1. Le nœud non-Leaf/Internal, qui est supprimé, est remplacé par un prédécesseur dans l'ordre si le nœud enfant gauche a plus que le nombre minimum de clés.
Visualisons ce cas à l'aide d'un exemple où nous supprimerons la clé 33 du B Tree.
Graphique 4.4 : Suppression d'une clé de nœud feuille (33) de l'arbre B
2. Le nœud non-Leaf/Internal, qui est supprimé, est remplacé par un successeur dans l'ordre si le nœud enfant droit a plus que le nombre minimum de clés.
Si l’un ou l’autre des enfants dispose d’un nombre minimum de clés, nous fusionnerons les nœuds enfants gauche et droit.
Visualisons ce cas en supprimant la clé 30 du B Tree.
Graphique 4.5 : Suppression d'une clé de nœud feuille (30) de l'arbre B
Après la fusion, si le nœud parent a moins que le nombre minimum de clés, on peut rechercher les frères et sœurs, comme dans Cas 1 .
Cas 3 : Dans le cas suivant, la hauteur de l'arbre diminue. Si la clé cible se trouve dans un nœud interne et que la suppression de la clé entraîne moins de clés dans le nœud (ce qui est inférieur au minimum nécessaire), recherchez le prédécesseur dans l'ordre et le successeur dans l'ordre. Si les deux enfants disposent d’un nombre minimum de clés, l’emprunt ne peut pas avoir lieu. Cela mène à Cas 2(3) , c'est-à-dire fusionner les nœuds enfants.
Nous chercherons à nouveau le frère ou la sœur pour emprunter une clé. Cependant, si le frère comprend également un nombre minimum de clés, nous fusionnerons le nœud avec le frère avec le nœud parent et organiserons les nœuds enfants selon les exigences (ordre croissant).
Visualisons ce cas à l'aide d'un exemple où nous supprimerons l'élément de données 10 du B Tree donné.
Figure 4.6 : Suppression d'une clé de nœud feuille (10) de l'arbre B
La complexité temporelle dans les exemples ci-dessus varie en fonction de l'emplacement d'où la clé doit être supprimée. Ainsi, la complexité temporelle de l’opération de suppression dans un arbre B est O(log?n) .
La conclusion
Dans ce tutoriel, nous avons découvert le B Tree et visualisé ses différentes opérations avec différents exemples. Nous avons également compris certaines propriétés et règles fondamentales du B Tree.