B-Tree
Un arbre B est un arbre de recherche multi-voies auto-équilibré où chaque nœud contient plusieurs clés et pointeurs enfants, garantissant des recherches en O(log N) avec un fan-out quasi O(1).
Objectif
Comprendre la structure de données centrale des index de bases de données et analyser ses performances de lecture/écriture et le remplissage des pages.
Mécanisme
Un arbre B d'ordre m a au plus m enfants par nœud et au moins ceil(m/2). Les insertions scindent et les suppressions fusionnent pour rester équilibré ; toutes les feuilles sont à la même profondeur. La taille des nœuds s'aligne sur les E/S de page de la base (p. ex. 16 Ko), et un fan-out élevé garde l'arbre bas (3-4 niveaux indexent des téraoctets).
Cas d’usage
- Structures de données d'index
- Structure interne des bases de données
- Optimisation du stockage