Exercice : Construction d’un B+-tree

Contexte : Vous gérez une petite base de données de ventes et souhaitez indexer les identifiants de commandes.

Consigne : Construisez un B+-tree d’ordre t = 2 en insérant les clés suivantes dans l’ordre donné :

Clés à insérer : 10, 20, 30, 40, 50, 60, 25, 35

Questions :

1. Dessinez la structure finale du B+-tree après insertion de toutes les clés
2. Indiquez clairement quels sont les nœuds internes et quelles sont les feuilles
3. Montrez les liens horizontaux entre les feuilles
4. Tracez le chemin de recherche pour trouver la clé 35

Rappels pour un B+-tree d’ordre t = 2 :

• Chaque nœud contient entre t-1 = 1 et 2t-1 = 3 clés
• Exception : la racine peut contenir moins de t-1 clés si elle est aussi une feuille
• Chaque nœud interne avec k clés a exactement k+1 fils
• Les données (pointeurs TID) ne sont stockées que dans les feuilles
• Les nœuds internes ne contiennent que des clés guides pour la navigation
• Toutes les feuilles sont au même niveau (arbre équilibré)
• Les feuilles sont reliées entre elles par des liens horizontaux