Question 1

Qu'est-ce qu'un arbre B ?

Accepted Answer

Un arbre B est un arbre de recherche multi-voies auto-équilibré. Chaque nœud peut contenir de nombreuses clés et de nombreux enfants, et toutes les feuilles restent à la même profondeur, donc la recherche, l'insertion et la suppression sont en O(log n) avec très peu de visites de nœuds — idéal pour le stockage basé sur disque et sur pages.

Question 2

Que signifie l'ordre m ?

Accepted Answer

L'ordre m est le nombre maximum d'enfants qu'un nœud peut avoir. Un nœud d'ordre m contient au plus m−1 clés et, quand il n'est pas la racine, au moins ceil(m/2)−1 clés. Cette simulation vous permet de choisir m de 3 à 6.

Question 3

Comment fonctionne une division ?

Accepted Answer

Quand un nœud déborderait avec m clés, il se divise : la clé médiane est poussée dans le parent et les clés restantes deviennent deux nœuds frères. Si la racine se divise, une nouvelle racine est créée et l'arbre grandit d'un niveau depuis le sommet.

Question 4

Pourquoi toutes les feuilles restent-elles à la même profondeur ?

Accepted Answer

Un arbre B ne grandit en hauteur qu'en divisant la racine et en poussant une clé vers le haut. Comme les divisions se propagent vers le haut et n'allongent jamais une seule branche isolément, chaque chemin racine-feuille a toujours exactement la même longueur, gardant l'arbre parfaitement équilibré en hauteur.

Question 5

Comment la recherche est-elle effectuée dans un arbre B ?

Accepted Answer

La recherche parcourt les clés triées à l'intérieur d'un nœud pour trouver l'intervalle où tombe la cible, puis suit le pointeur enfant pour cet intervalle et répète, descendant d'un niveau par nœud jusqu'à ce que la clé soit trouvée ou qu'une feuille soit atteinte sans elle.

Question 6

Pourquoi les arbres B sont-ils utilisés pour les index de bases de données ?

Accepted Answer

Comme chaque nœud regroupe de nombreuses clés, l'arbre est très peu profond, donc une recherche ne touche qu'une poignée de nœuds — et donc une poignée de pages disque. Cela minimise les lectures disque lentes, c'est pourquoi les arbres B et leur variante arbre B+ sous-tendent presque tous les index de bases de données relationnelles et de nombreux systèmes de fichiers.

Question 7

Quelle est la différence entre un arbre B et un arbre B+ ?

Accepted Answer

Dans un arbre B, chaque nœud peut stocker des valeurs de données. Dans un arbre B+, toutes les valeurs vivent dans les feuilles et les nœuds internes ne contiennent que des clés de routage, avec les feuilles liées dans une liste. Cela rend les balayages de plage faciles, c'est pourquoi la plupart des bases de données utilisent en réalité des arbres B+.

Question 8

Quelle hauteur un arbre B atteint-il ?

Accepted Answer

La hauteur croît avec le logarithme du nombre de clés en base ceil(m/2). Avec un grand ordre m, un arbre contenant des millions de clés peut n'avoir que trois ou quatre niveaux de profondeur, ce qui est exactement pourquoi il est si efficace sur disque.

Question 9

Que met en évidence la simulation après une division ?

Accepted Answer

Le nœud qui vient de se diviser et la clé poussée dans son parent sont mis en évidence, afin que vous puissiez retracer comment la médiane a été déplacée et comment les deux nœuds frères ont été formés.

Question 10

Est-ce une véritable implémentation d'arbre B ?

Accepted Answer

Oui. L'insertion utilise l'algorithme standard de division en cas de débordement avec promotion de la médiane. Les clés sont maintenues triées dans chaque nœud, toutes les feuilles restent à profondeur égale, et l'ordre, la hauteur, le nombre de nœuds et le nombre de divisions se mettent à jour en direct à partir de la structure réelle.

🗃️ Arbre B — Arbre de recherche multi-voies

À propos de la structure d'index Arbre B

Qu'avez-vous trouvé ?