Quand un arbre binaire est-il meilleur qu'un arbre B?

Question

Lors du stockage d'un arbre binaire ou d'un arbre B sur un périphérique de stockage secondaire tel qu'un disque ou une bande, un arbre binaire a-t-il un avantage sur un arbre B?

On m'a demandé une tâche «Quand les arbres B ont-ils un avantage sur les arbres binaires? Ce que j'ai trouvé est qu'un B-Tree est meilleur car il nécessite moins d'accès au disque (lit plus de données par accès au nœud), et saute à moins de nœuds pour arriver au nœud final. Mais la façon dont la question est formulée implique un point où un arbre binaire a effectivement l'avantage sur un arbre B. Donc, est là un point où un arbre binaire est meilleur (plus efficace) qu'un arbre B quand ils sont stockés sur le stockage secondaire?

Answer 1

Il n'est pas correct de comparer l'arbre trié (B-tree) et l'arbre binaire simple, ils ne sont pas égaux. Donc je suppose que vous voulez dire arbre de recherche binaire. B-Tree a été conçu pour être efficace lorsque les données sont stockées dans des conditions de stockage relativement lentes. Par exemple lorsque vous chargez ou enregistrez des données à partir du système de fichiers avec la taille de cluster 4kb, peu importe la quantité de données dans cette plage 0..4kb dont vous avez besoin, cela prendra le même temps pour lire 1 byte ou 4kb temps. B-tree garde à l'esprit ce fait et l'utilise. Ainsi, dans tous les scénarios d'utilisation normale/générale, il sera plus efficace d'utiliser B-tree (du point de vue espace utilisé et performance).