Quelles sont les différences entre les arbres B et les arbres B +?

Dans un arbre b, vous pouvez stocker les clés et les données dans les nœuds internes et feuilles , mais dans un arbre b +, vous devez stocker les données dans les nœuds feuilles uniquement .

Y a-t-il un avantage à faire ce qui précède dans un arbre b +?

Pourquoi ne pas utiliser les arbres b au lieu des arbres b + partout, car intuitivement ils semblent beaucoup plus rapides?

Je veux dire, pourquoi avez-vous besoin de répliquer la clé (données) dans un arbre b +?

L'image ci-dessous permet de montrer les différences entre les arbres B + et les arbres B.

Avantages des arbres B +:

• Étant donné que les arbres B + n'ont pas de données associées aux nœuds intérieurs, davantage de clés peuvent tenir sur une page de mémoire. Par conséquent, il faudra moins de ratés de cache pour accéder aux données qui se trouvent sur un nœud feuille.
• Les nœuds foliaires des arbres B + sont liés, de sorte que l'analyse complète de tous les objets d'un arbre nécessite un seul passage linéaire à travers tous les nœuds foliaires. Par contre, un arbre AB nécessiterait une traversée de chaque niveau de l'arbre. Cette traversée d'arbre complet impliquera probablement plus de ratés de cache que la traversée linéaire de feuilles B +.

Avantage des arbres B:

• Étant donné que les arborescences B contiennent des données avec chaque clé, les nœuds fréquemment consultés peuvent se trouver plus près de la racine et, par conséquent, être accessibles plus rapidement.

Le principal avantage des arbres B + par rapport aux arbres B est qu'ils vous permettent d'intégrer plus de pointeurs vers d'autres nœuds en supprimant des pointeurs vers les données, augmentant ainsi le fanout et potentiellement diminuant la profondeur de l'arbre.

L'inconvénient est qu'il n'y a pas de sorties anticipées lorsque vous avez peut-être trouvé une correspondance dans un nœud interne. Mais comme les deux structures de données ont d'énormes fanouts, la grande majorité de vos correspondances seront de toute façon sur les nœuds feuilles, ce qui rendra en moyenne l'arbre B + plus efficace.

Les arbres B + sont beaucoup plus faciles et plus performants pour effectuer une analyse complète, comme pour chaque élément de données indexé par l'arbre, car les nœuds terminaux forment une liste liée. Pour effectuer une analyse complète avec un B-Tree, vous devez effectuer une traversée complète de l'arborescence pour trouver toutes les données.

D'un autre côté, les B-Trees peuvent être plus rapides lorsque vous effectuez une recherche (en recherchant une donnée spécifique par clé), en particulier lorsque l'arborescence réside dans la RAM ou dans un autre stockage non-bloc. Étant donné que vous pouvez élever les nœuds couramment utilisés dans l'arborescence, moins de comparaisons sont nécessaires pour accéder aux données.

1. Dans une arborescence B, les clés de recherche et les données sont stockées dans des nœuds internes ou feuilles. Mais dans un arbre B +, les données ne sont stockées que dans les nœuds feuilles.
2. L'analyse complète d'un arbre B + est très facile car toutes les données se trouvent dans les nœuds foliaires. L'analyse complète d'un arbre B nécessite une traversée complète.
3. Dans un arbre B, les données peuvent être trouvées dans des nœuds feuilles ou des nœuds internes. La suppression des nœuds internes est très compliquée. Dans un arbre B +, les données se trouvent uniquement dans les nœuds foliaires. La suppression des nœuds foliaires est facile.
4. L'insertion dans l'arbre B est plus compliquée que l'arbre B +.
5. Les arbres B + stockent les clés de recherche redondantes mais l'arbre B n'a pas de valeur redondante.
6. Dans une arborescence B +, les données du nœud feuille sont classées sous forme de liste chaînée séquentielle, mais dans une arborescence B, le nœud feuille ne peut pas être stocké à l'aide d'une liste chaînée. De nombreuses implémentations de systèmes de bases de données préfèrent la simplicité structurelle d'un arbre B +.

Exemple de concepts de système de base de données 5e

Arbre B +

arbre B correspondant

Définissez "beaucoup plus vite". Asymptotiquement, ils sont à peu près les mêmes. Les différences résident dans la façon dont ils utilisent le stockage secondaire. Les articles de Wikipedia sur les arbres B et les arbres B + semblent assez fiables.

Adegoke A, Amit

Je suppose qu'un point crucial que vous manquez est la différence entre les données et les pointeurs comme expliqué dans cette section.

Pointeur: pointeur vers d'autres nœuds.

Données: - Dans le contexte des index de base de données, les données ne sont qu'un autre pointeur vers des données réelles (ligne) qui résident ailleurs.

Par conséquent, dans le cas de l'arbre B, chaque nœud possède trois clés d'information, des pointeurs vers les données associées aux clés et un pointeur vers les nœuds enfants.

Dans l'arborescence B +, le nœud interne conserve les clés et les pointeurs vers le nœud enfant tandis que le nœud feuille conserve les clés et les pointeurs vers les données associées. Cela permet un plus grand nombre de clés pour une taille de nœud donnée. La taille du nœud est déterminée principalement par la taille du bloc.

L'avantage d'avoir plus de clés par nœud est expliqué bien ci-dessus, donc je vais économiser mon effort de frappe.

Les arbres B + sont particulièrement adaptés au stockage basé sur des blocs (par exemple: disque dur). dans cet esprit, vous obtenez plusieurs avantages, par exemple (du haut de ma tête):

• fanout élevé / faible profondeur: cela signifie que vous devez obtenir moins de blocs pour accéder aux données. avec des données entremêlées avec les pointeurs, chaque lecture obtient moins de pointeurs, vous avez donc besoin de plus de recherches pour accéder aux données

• stockage de blocs simple et cohérent: un nœud interne a N pointeurs, rien d'autre, un nœud feuille a des données, rien d'autre. cela facilite l'analyse, le débogage et même la reconstruction.

• une densité de clé élevée signifie que les nœuds supérieurs sont presque certainement dans le cache, dans de nombreux cas, tous les nœuds internes sont rapidement mis en cache, donc seul l'accès aux données doit aller sur le disque.

Dans B + Tree, puisque seuls les pointeurs sont stockés dans les nœuds internes, leur taille devient considérablement plus petite que les nœuds internes de B tree (qui stockent à la fois les données + la clé). Par conséquent, les index de l'arborescence B + peuvent être récupérés à partir du stockage externe dans une seule lecture de disque, traités pour trouver l'emplacement de la cible. S'il s'agit d'une arborescence B, une lecture de disque est requise pour chaque processus décisionnel. J'espère avoir fait comprendre mon point! :)

**

L'inconvénient majeur de B-Tree est la difficulté de parcourir les touches de manière séquentielle. L'arbre B + conserve la propriété d'accès aléatoire rapide de l'arbre B tout en permettant un accès séquentiel rapide

** ref: Structures de données utilisant C // Auteur: Aaro M Tenenbaum

http://books.google.co.in/books?id=X0Cd1Pr2W0gC&pg=PA456&lpg=PA456&dq=drawback+of+B-Tree+is+the+difficulty+of+Traversing+the+keys+sequential&source=bl&ots=pGcPQSEJMS&sig= F9MY7zEXYAMVKl_Sg4W-0LTRor8 & hl = en & sa = X & ei = nD5AUbeeH4zwrQe12oCYAQ & ved = 0CDsQ6AEwAg # v = onepage & q = drawback% 20of% 20B-Tree% 20is% 20the% 20diff 20%

Prenons un exemple - vous avez un tableau avec d'énormes données par ligne. Cela signifie que chaque instance de l'objet est Big.

Si vous utilisez l'arborescence B ici, la plupart du temps est consacré à la numérisation des pages contenant des données, ce qui est inutile. Dans les bases de données, c'est la raison d'utiliser les arbres B + pour éviter d'analyser les données des objets.

B + Les arbres séparent les clés des données.

Mais si la taille de vos données est inférieure, vous pouvez les stocker avec la clé, ce que fait l'arbre B.

La principale distinction entre l'arbre B et l'arbre B + est que l'arbre B élimine le stockage redondant des valeurs de clé de recherche.Comme les clés de recherche ne sont pas répétées dans l'arbre B, il se peut que nous ne puissions pas stocker l'index en utilisant moins de nœuds d'arbre. que dans l'index de l'arbre B + correspondant. Cependant, comme la clé de recherche qui apparaît dans les nœuds non-feuilles n'apparaît nulle part ailleurs dans l'arbre B, nous sommes obligés d'inclure un champ de pointeur supplémentaire pour chaque clé de recherche dans un nœud non-feuille. Ce sont des avantages d'espace pour l'arbre B, car la répétition ne se produit pas et peut être utilisée pour les grands indices.

Un arbre B + est un arbre équilibré dans lequel chaque chemin de la racine de l'arbre à une feuille est de la même longueur, et chaque nœud non-feuille de l'arbre a entre [n / 2] et [n] enfants, où n est fixe pour un arbre particulier. Il contient des pages d'index et des pages de données. Les arbres binaires n'ont que deux enfants par nœud parent, les arbres B + peuvent avoir un nombre variable d'enfants pour chaque nœud parent

Une utilisation possible des arbres B + est qu'ils conviennent aux situations où l'arbre devient si grand qu'il ne tient pas dans la mémoire disponible. Ainsi, vous vous attendez généralement à effectuer plusieurs E / S.
Il arrive souvent qu'une arborescence B + soit utilisée même lorsqu'elle tient en fait dans la mémoire, et que votre gestionnaire de cache puisse la conserver en permanence. Mais c'est un cas spécial, pas le cas général, et la politique de mise en cache est distincte de la maintenance de l'arborescence B + en tant que telle.

De plus, dans une arborescence B +, les pages feuilles sont liées entre elles dans une liste chaînée (ou liste doublement chaînée), ce qui optimise les parcours (pour les recherches par plage, le tri, etc.). Le nombre de pointeurs est donc fonction de l'algorithme spécifique utilisé.