Principale différence: dans les ordinateurs, les arbres binaires sont des structures de données arborescentes qui stockent les données et permettent à l'utilisateur d'accéder aux données, de les rechercher, de les insérer et de les supprimer au moment de l'algorithme. La différence entre un arbre B et un arbre B + réside dans le fait que, dans un arbre B, les clés et les données peuvent être stockées à la fois dans les nœuds internes et terminaux, tandis que dans un arbre B +, les données et les clés ne peuvent être stockées que dans les nœuds terminaux. .

Les arbres binaires sont des arbres de recherche équilibrés conçus pour fonctionner correctement sur les périphériques de stockage secondaires à accès direct tels que les disques magnétiques. Rudolf Bayer et Ed McCreight ont inventé le concept d’un arbre à branches.

Un arbre B est un arbre de recherche binaire généralisé, dans lequel tout nœud peut avoir plus de deux enfants. Chaque nœud interne dans un arbre B contient un certain nombre de clés. Ces clés séparent les valeurs et forment ensuite les sous-arbres. Les nœuds internes d'un arbre B peuvent avoir un nombre variable de nœuds enfants, disposés dans une plage prédéfinie. Au moment où des données sont insérées ou supprimées d'un nœud respectif, le nombre de nœuds enfants change. Afin de maintenir la plage prédéfinie, les nœuds internes peuvent être joints ou divisés. Dans un arbre B, une plage de nœuds enfants est autorisée, en conséquence de quoi la plage prédéfinie doit être conservée.

Les arbres B ne doivent pas être rééquilibrés fréquemment, contrairement aux autres arbres de recherche à auto-équilibrage. Les nœuds dans ces arbres ne sont pas toujours pleins; par conséquent, les espaces sont consommés de manière inutile dans ces arbres, ce qui entraîne un gaspillage d'espace. Seules les limites inférieure et supérieure du nombre de nœuds enfants sont généralement fixées pour une implémentation particulière. Par exemple, dans une arborescence 2-3 B-tree (souvent simplement appelée une arborescence 2-3), chaque nœud interne peut avoir uniquement 2 ou 3 nœuds enfants.

De plus, le B-tree est optimisé pour les systèmes qui lisent et écrivent des blocs de données volumineux. Il est couramment utilisé dans les bases de données et les systèmes de fichiers. Dans l'arborescence B, tous les nœuds sont conservés aux mêmes profondeurs d'équilibrage à partir des nœuds racine. Ces profondeurs augmentent lentement à mesure que le nombre d'éléments augmente; il en résulte que tous les nœuds terminaux sont un nœud supplémentaire, plus éloigné de la racine. En outre, les arbres B- sont plus avantageux que d'autres implémentations en ce qui concerne le temps nécessaire pour accéder aux données.

Une arborescence B + est une arborescence de tableaux multiples avec un nœud, composé d'un grand nombre d'enfants par nœud. La racine peut être une feuille ou un nœud contenant plus de deux enfants. Un arbre B + comprend une racine, des noeuds internes et des feuilles.

Un arbre B + est identique à un arbre B; la seule différence est que, dans l'arbre B +, un niveau supplémentaire est ajouté au bas avec des feuilles liées. De même, contrairement à l’arborescence B, chaque nœud d’une arborescence B + ne contient que des clés et non des paires clé-valeur.

De plus, le facteur d'équilibrage ou l'ordre d'un arbre B + mesure la capacité des noeuds internes d'un arbre, c'est-à-dire le nombre de noeuds qu'ils peuvent avoir. Le nombre réel d'enfants pour un nœud est limité pour les nœuds internes. La racine est toutefois une exception car il est autorisé d'avoir plus de deux enfants. Par exemple, si l'ordre d'un arbre B + est 7, chaque nœud interne (à l'exception de la racine) peut avoir entre 4 et 7 enfants; alors que la racine peut avoir entre 2 et 7. La principale valeur de l’arborescence B + réside dans le stockage des données pour une extraction efficace dans un contexte de stockage orienté par blocs et dans des systèmes de fichiers particuliers.

La valeur principale de l’arbre B + réside dans le stockage et la maintenance des données, afin que celles-ci ne soient pas perdues. Cette approche est particulièrement appliquée dans le contexte de stockage orienté par blocs et dans certains systèmes de fichiers. Les feuilles, qui sont les blocs d'index les plus bas, de l'arbre B + sont souvent liées les unes aux autres dans une liste chaînée; par conséquent, cela rend les requêtes de plage ou une itération ordonnée à travers les blocs plus simples et plus efficaces. De plus, le facteur d'espace n'est pas perdu dans les arbres B +. L'arborescence B + fournit un format de structure de données de logement efficace, ce qui facilite leur accès et leur stockage. Les arbres B + sont particulièrement utiles en tant qu'index système de base de données, où les données résident généralement sur un disque.

Comparaison entre B Tree et B + Tree: