Dans un arbre B, vous pouvez stocker à la fois les clés et les données dans les nœuds internes et les nœuds feuilles, mais dans un arbre B+ vous devez stocker les données dans les nœuds feuilles seulement.
Y a-t-il un avantage à faire cela dans un arbre B+?
Pourquoi ne pas utiliser des arbres B à la place 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 aide à montrer les différences entre les arbres B+ et les arbres B.
Avantages des arbres B+ :
Avantage des arbres B :
@TLE Bonne question! Oui. Un disque dur accède à un minimum d'une page de mémoire à la fois, donc nous voulons adapter tous les pointeurs dans une seule page de mémoire. Nous voulons exiger seulement une lecture de disque par accès de feuille, donc nous ne voulons pas attribuer plus d'une taille de page de pointeurs à une feuille. Si nous remplissons une feuille avec une taille de page de pointeurs, et que nous voulons ajouter un autre pointeur à cette feuille, nous créons deux enfants pour ce nœud, et nous donnons la moitié des pointeurs de la feuille à chaque nouvel enfant. Bien sûr, il peut y avoir un certain réarrangement pour garantir que la hauteur de l'arbre est maintenue à un minimum. Est-ce que cela aide?
Le dernier pointeur de chaque nœud feuille de l'arbre B doit pointer vers le prochain nœud feuille, n'est-ce pas?
Le principal avantage des arbres B+ par rapport aux arbres B est qu'ils vous permettent d'emballer plus de pointeurs vers d'autres nœuds en supprimant les pointeurs vers les données, ce qui augmente le facteur de ventilation et diminue potentiellement la profondeur de l'arbre.
L'inconvénient est qu'il n'y a pas de sortie anticipée lorsque vous pourriez avoir trouvé une correspondance dans un nœud interne. Mais comme les deux structures de données ont des facteurs de ventilation énormes, la grande majorité de vos correspondances seront de toute façon sur des nœuds feuilles, ce qui rend en moyenne l'arbre B+ plus efficace.
Je préfère la réponse de Jeff, car elle met l'accent sur la différence d'efficacité lors de l'analyse complète.
Je suis vraiment confus car parcourir un arbre b en utilisant un parcours en ordre lira toutes les valeurs dans l'ordre trié en temps O(n). Si chaque nœud de l'arbre est de taille optimale pour la taille de la page physique, il semble que les choses ne deviennent pas plus optimales. En revanche, le coût pour accéder à la première valeur (la plus petite) dans un arbre b+ est O(log n) et ensuite parcourir chaque feuille est O(n) donc le coût total est O(log n + n). Cela représente plus de travail et plus de lectures de disque ce qui a du sens car l'arbre contient toutes ces données supplémentaires. Je ne comprends pas.
Les B+ arbres sont beaucoup plus faciles et plus performants à numériser entièrement, c'est-à-dire à regarder chaque donnée indexée par l'arbre, car les nœuds terminaux forment une liste chaînée. Pour effectuer une numérisation complète avec un arbre B, vous devez effectuer une traversée complète de l'arbre pour trouver toutes les données.
En revanche, les B-arbres peuvent être plus rapides lorsque vous effectuez une recherche (recherche d'une donnée spécifique par clé), surtout lorsque l'arbre réside en RAM ou dans un autre stockage non bloquant. Étant donné que vous pouvez élever les nœuds couramment utilisés dans l'arbre, moins de comparaisons sont nécessaires pour accéder aux données.
Est-ce que vous seriez d'accord alors qu'un arbre B+ serait utilisé pour des situations où il peut y avoir une lecture séquentielle sur l'ensemble des données et être capable de parcourir les feuilles. Alors que l'arbre B serait idéal pour des situations d'accès aléatoire?
Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.
42 votes
Je pense qu'ils veulent dire "Arbre-B" par rapport à Arbre-B+. Ils veulent dire un trait d'union, pas un signe négatif.