La différence entre b-tree et b + tree

Difference Between B Tree



Arbre B:


Arbre B +:





Structurellement



Le jeu de mots-clés dans l'arbre B est distribué dans l'arborescence entière, le nœud feuille ne contient aucune information de mot-clé et le jeu de mots-clés de l'arbre B + est distribué dans le nœud feuille, et le nœud non-feuille n'est que l'index du mot-clé dans le nœud feuille
Tout mot-clé de l'arborescence B n'apparaît que dans un nœud, et les mots-clés de l'arborescence B + doivent apparaître dans le nœud feuille ou dans les nœuds non-feuille

Performances (c'est pourquoi l'arborescence B + est plus adaptée que l'arborescence B pour l'index de fichier et l'index de base de données du système d'exploitation dans l'application réelle?)

  • Le coût de lecture et d'écriture du disque B + tree est inférieur À cause de l'arbre B + Les nœuds non-feuilles ne stockeront que les informations d'index ,et Les informations de données réelles ne sont stockées que dans le nœud feuille De cette manière, chaque nœud non feuille stocke plus d'informations d'index, et une E / S de disque peut lire plus d'informations d'index dans la mémoire, ce qui peut réduire le nombre d'E / S de disque.
  • L'efficacité des requêtes d'arbre B + est plus stable Étant donné que les nœuds non-feuilles stockent uniquement les informations d'index et aucune information de données réelles, toute recherche par mot-clé doit emprunter un chemin du nœud racine au nœud feuille. Les longueurs de chemin de toutes les requêtes par mot-clé sont identiques, ce qui se traduit par une efficacité de requête pour chaque donnée.
  • L'arbre B + est plus adapté à la requête d'intervalle Étant donné que les données de l'arborescence B + sont stockées dans les nœuds feuilles, les nœuds non-feuilles sont tous indexés, et seuls les nœuds feuilles doivent être analysés pour obtenir toutes les informations de données, mais l'arbre B stocke également les données en raison de son nœuds non-feuilles. Nous devons trouver les données spécifiques, nous devons effectuer un parcours séquentiel pour balayer dans l'ordre, de sorte que l'arbre B + est plus approprié pour la requête d'intervalle, donc généralement l'arbre B + est utilisé pour l'indexation de la base de données.