B+ Tree
Un arbre B+ est une variante de l'arbre B : les données ne vivent que dans les feuilles, les nœuds internes ne contiennent que des clés et des pointeurs, et les feuilles sont chaînées pour permettre les parcours par intervalles.
Objectif
Comprendre la variante d'index la plus courante dans les bases de données et optimiser les requêtes par intervalle et l'accès séquentiel.
Mécanisme
Les nœuds internes ne contiennent que des clés d'index (fan-out élevé) ; les feuilles contiennent clés + données + pointeurs suivants. Les parcours par intervalle lisent séquentiellement le long de la chaîne de feuilles. Les suppressions n'affectent que les feuilles. Presque tous les index de bases de données relationnelles utilisent des arbres B+.
Cas d’usage
- Optimisation des requêtes par intervalle
- Conception d'index
- Structure interne des bases de données