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