Tri externe

Vous connaissez sans doute déjà plusieurs algorithmes de tri. Ce qui est nouveau lorsqu'on utilise un algorithme de tri dans un SGBD c'est la taille des données : la relation est trop grosse pour rentrer dans la mémoire; donc les algorithmes classique (e.g. tri bull, tri fusion, quicksort) ne peuvent pas être utilisés ! On fait donc appel à de nouveau algorithmes de tri, comme le tri externe, qui prend en compte la contrainte de vitesse de la mémoire vive de l'ordinateur, limitée en taille, et du disque, considéré de taille illimitée.

Le tri externe s'exécute de la manière suivante :

  • Étape 1

    • On lit ce qu'on peut dans la mémoire : on le trie ; on écrit ce fragment trié

    • On fait cela pour toute la relation

    • On obtient N fragments triés avec une lecture et une écriture du tout

  • Étape 2

    • On fusionne les fragments 2 à deux

    • On recommence jusqu'à n'avoir plus qu'un seul fragment trié

    • Coût autant de lecture/écriture que de niveau de fusion (log N)

Très sensible à la taille de la mémoire