Discussion :

[alex.hitman]

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.

[pseudocode]

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...

Mais dans ce cas les noeuds qui sont dans le même bloc n'ont pas de rapport entre eux (i.e. ne sont pas consécutifs). Ou alors il faut modifier le contenu des blocs à chaque balancement, ce qui ferait beaucoup d'accès disque.

[alex.hitman]

Merci de la réponse.

On pourrait décider de placer dans un même bloc les noeuds issus d'un même parent, c'est à dire qu'il y aurait un "sous-AVL" dans un bloc, dans ce cas une lecture de bloc suffirait pour nous donner plusieurs niveaux de notre AVL.

Effectivement, il faudrait ensuite maintenir tout cela organisé, mais je ne pense pas que cela demande tant d'opérations sur le disque que ça, comparé à un Btree.

Je vais réfléchir sur ce point...


Mais autrement, n'y a-t'il pas d'autre raison poussant à l'utilisation d'un Btree ?

[Jean-Marc.Bourguet]

Merci de la réponse.

On pourrait décider de placer dans un même bloc les noeuds issus d'un même parent, c'est à dire qu'il y aurait un "sous-AVL" dans un bloc, dans ce cas une lecture de bloc suffirait pour nous donner plusieurs niveaux de notre AVL.

Effectivement, il faudrait ensuite maintenir tout cela organisé, mais je ne pense pas que cela demande tant d'opérations sur le disque que ça, comparé à un Btree.

Je vais réfléchir sur ce point...


Mais autrement, n'y a-t'il pas d'autre raison poussant à l'utilisation d'un Btree ?

Regarde le rapport entre les Red-Black tree et les AVL d'une part et les Btree de l'autre.

[alex.hitman]

Justement, j'ai beaucoup lu et travaillé sur ces différents types d'arbres, mais je ne comprends pas pourquoi ce sont les Btree qui sont utilisés, et non par exemple des AVL que l'on structurerait "par bloc"...

[Jean-Marc.Bourguet]

Justement, j'ai beaucoup lu et travaillé sur ces différents types d'arbres, mais je ne comprends pas pourquoi ce sont les Btree qui sont utilisés, et non par exemple des AVL que l'on structurerait "par bloc"...

1/ pourquoi preferer des red-black trees aux AVL?
2/ quel est le rapport entre les red-black tree et les Btrees? (Si tu n'en vois pas, considere le regroupement d'un noeud noir et de ses fils rouges et compare ca avec un Btree dont les noeuds ont 4 fils au maximum).