Salut à tous,

A l'occasion de mon TIPE, je suis amené à travailler avec des B-tree et des AVL. Seulement, une question à laquelle je dois répondre est "pourquoi dans les bases de données ce sont les b-tree qui sont utilisés, et non les AVL ?"

En effet, les AVL sont plus performants (si on travaille en mémoire tout du moins). Seulement, ce qui est vraiment coûteux en performance, ce sont les accès disques. Alors je me suis dit que sur le disque (ce qui correspond parfaitement aux bases de données), les Btree sont certainement beaucoup plus performants que les AVL, étant donné qu'un noeud d'un btree contient beaucoup plus d'éléments qu'un noeud d'AVL. Donc, si l'on peut accéder à un noeud par une seule lecture sur le disque, les btree sont plus performants.

Mais rien ne nous empêche de mettre plusieurs noeuds d'un AVL dans un seul bloc du disque, et donc d'accéder aussi à un grand nombre d'éléments d'un AVL par une seule lecture sur le disque...


Donc, pourquoi utiliser des Btree et non des AVL ? Qu'est-ce qui les rend plus performants ?



Merci d'avance.