Français
Menu

Structures de données et algorithmes

Quelle est la raison principale pour laquelle les arbres B (y compris les arbres B+), plutôt que les arbres binaires de recherche, sont largement utilisés pour les index des bases de données et des systèmes de fichiers ?

  1. AChaque nœud contient de nombreuses clés, ce qui garde l'arbre peu profond et réduit fortement l'intervalle à chaque nœud lu, d'où moins de lectures de blocs sur le disque ou un support équivalent
  2. BChaque nœud ne contient qu'une seule clé, si bien qu'il faut moins de comparaisons que dans un arbre binaire de recherche
  3. CL'arbre n'a pas besoin d'être réorganisé lors d'une insertion, si bien qu'il est plus simple à implémenter qu'un arbre binaire de recherche
Afficher la réponse et l'explication

Réponse : A. Chaque nœud contient de nombreuses clés, ce qui garde l'arbre peu profond et réduit fortement l'intervalle à chaque nœud lu, d'où moins de lectures de blocs sur le disque ou un support équivalent

Les disques et les SSD lisent les données par blocs de plusieurs kilooctets, même quand un seul octet est nécessaire : il importe donc de réduire le nombre de lectures. Un arbre B place des centaines de clés dans un nœud (un bloc), si bien que chaque nœud lu se ramifie en centaines de branches ; même 100 millions d'enregistrements sont atteints en 3 à 4 niveaux. Quand une insertion ou une suppression surcharge un nœud, celui-ci est scindé, et quand un nœud devient trop vide, il est fusionné, ce qui maintient toutes les feuilles à la même profondeur. Un arbre binaire de recherche de 100 millions d'enregistrements demande au moins 27 niveaux environ, et lire un bloc différent à chaque niveau est lent.

S'entraîner sur ce thème Retour au thème

Autres questions sur Structures de données et algorithmes

  1. Quelle est une façon appropriée de stocker en mémoire un graphe creux, c'est-à-dire un graphe ayant peu d'arêtes par rapport à son nombre de sommets, comme un réseau routier d'environ 1 million de sommets et 3 millions d'arêtes ?
  2. Dans un graphe dont les arêtes n'ont pas de poids, on veut trouver le plus petit nombre d'arêtes entre un sommet de départ et chacun des autres sommets. Quelle association entre méthode de recherche et structure de données convient ?
  3. Dans un graphe non orienté, les voisins de chaque sommet sont A : B, C / B : A, D, E / C : A, F / D : B / E : B, F / F : C, E. Un parcours en profondeur par récursion part du sommet A. Les voisins sont examinés dans l'ordre indiqué, et dès qu'un sommet non visité est trouvé, le parcours s'y déplace. Dans quel ordre les sommets sont-ils visités ?
  4. Dans un graphe non orienté, les poids des arêtes (distances) sont S−A : 4, S−B : 1, A−B : 2, A−C : 1, B−C : 5, C−T : 3 et A−T : 6. Quelle réponse donne le plus court chemin de S à T trouvé par l'algorithme de Dijkstra et sa longueur ?
  5. Quelle condition sur le graphe est nécessaire pour que l'algorithme de Dijkstra trouve des plus courts chemins corrects ?