LES B-ARBRES

Comment une base de donnees retrouve-t-elle une ligne parmi cent millions, en quelques millisecondes ? La reponse tient en une structure inventee en 1970 et jamais detronee depuis : le B-arbre. Ce cours l'explique de la definition formelle jusqu'aux index SQL, schemas a l'appui.

Ce que vous saurez faire a la fin

Enoncer la definition d'un B-arbre et verifier qu'un arbre donne en est un.
Passer d'une convention a l'autre : degre minimal t et ordre m : sans vous tromper en examen.
Demontrer la borne sur la hauteur, h ≤ log_t((n+1)/2).
Derouler a la main une recherche, une insertion avec eclatement, une suppression avec fusion ou rotation.
Calculer le degre optimal a partir de la taille d'une page disque.
Comprendre pourquoi un index accelere certaines requetes SQL et pas d'autres.

A qui s'adresse ce cours

A tout etudiant qui connait deja les arbres binaires de recherche. Les prerequis sont rappeles au passage, et chaque notion nouvelle est introduite par un exemple avant d'etre formalisee.

Le cours s'adresse aussi a ceux qui preparent un examen de structures de donnees : les demonstrations sont detaillees pas a pas, et les deux conventions de notation sont traitees cote a cote.

Le point de depart

Un noeud porte plusieurs cles triees, un noeud a k cles possede k+1 fils, et toutes les feuilles sont exactement au meme niveau. Ces trois observations contiennent deja l'essentiel ; le reste du cours en tire les consequences.

Les huit chapitres

Chapitre 1Pourquoi le disque change toutLes B-arbres n'existent pas pour aller vite en mémoire, mais pour éviter le disque. Comprendre ce rapport de un à un million explique toute la structure.Chapitre 2La définition, et ses deux conventionsCe qu'est exactement un B-arbre : les quatre propriétés qui le définissent, et la réconciliation des deux notations, degré minimal t et ordre m, qu'on rencontre selon les cours.Chapitre 3Anatomie d'un nœudComment un nœud est réellement organisé en mémoire et sur le disque : clés, pointeurs, intervalles, et le choix du degré en fonction de la taille d'une page.Chapitre 4La hauteur, et pourquoi elle reste minusculeLe théorème central des B-arbres : h ≤ log_t((n+1)/2), avec sa démonstration détaillée pas à pas, et ce qu'il garantit en pratique.Chapitre 5Rechercher une cléL'algorithme de recherche dans un B-arbre, sa traduction en code, et la distinction entre le coût en accès disque et le coût processeur.Chapitre 6Insérer : l'éclatement des nœuds pleinsComment ajouter une clé sans jamais déséquilibrer l'arbre : le partage d'un nœud plein, l'astuce de l'éclatement préventif, et la croissance par le haut.Chapitre 7Supprimer : emprunter ou fusionnerLa suppression, opération la plus délicate du B-arbre : remplacement par un voisin, emprunt au frère par rotation, fusion quand personne ne peut prêter, et rétrécissement par le haut.Chapitre 8B+ arbres, bases de données et systèmes de fichiersLa variante qui équipe réellement les bases de données : feuilles chaînées, nœuds internes allégés, et pourquoi tous les index sérieux sont des B+ arbres.

Pour aller plus loin

Cours sur la complexite des algorithmes : pour maitriser les notations O, Ω et Θ utilisees ici.
Cours d'algorithmique : les bases : boucles, tableaux, fonctions, recursivite.
Examens d'algorithmique avancee : plusieurs sujets portent sur les B-arbres.

Pour prolonger ce cours : Algorithmes de graphes : parcours, chemins, arbres couvrants et flots, avec dix chapitres et des exercices corrigés.