Développement : Insertion dans un arbre B

Détails/Enoncé :

L'insertion dans un arbre B de hauteur $h$ se fait en $O(h)$ accès disque.

De plus, la hauteur d'un arbre B avec $t - 1$ à $2t - 1$ clés par noeud est $h = O(\log_t n)$.

Le recasage dans la leçon bases de données c'est parce que SQL (typiquement) utilise des B-arbres pour faire ses index.

Recasages pour l'année 2024 :

  • Pas de recasages pour cette année.

Versions :

Références utilisées dans les versions de ce développement :

Introduction à l'algorithmique, Thomas H. Cormen, Charles E. Leiserson, Clifford Stein, Ronald Rivest (utilisée dans 49 versions au total)