Insertion dans un arbre B
L'insertion dans un arbre B de hauteur $h$ se fait en $O(h)$ accès disque.\r\rDe plus, la hauteur d'un arbre B avec $t - 1$ à $2t - 1$ clés par noeud est $h = O(\log_t n)$.\r\rLe recasage dans la leçon bases de données c'est parce que SQL (typiquement) utilise des B-arbres pour faire ses index.
| Qualité | Numéro | Titre |
|---|---|---|
| 5 | 921 | Algorithmes de recherche et structures de données associées.2021 |
| 5 | 4 | Exemples de structures de données. Applications.2022 |
| 5 | 22 | Modèle relationnel et conception de bases de données.2022 |
Utilisateur : pauloss
Ça s'appelle B-arbres dans le Cormen (chapitre 18), il explique pourquoi c'est intéressant pages 425-429, puis l'insertion est faite pages 433-437.
Références :
Introduction à l'algorithmique - Thomas H. Cormen, Charles E. Leiserson, Clifford Stein, Ronald Rivest