Salut
svp, je voudrai savoir le cout en nombre d'ES et en temps CPU des algorithmes de jointure : nested-loop , tri-fusion et hash-join dans les bases des données orientées objet.
Merci d'avance.
Version imprimable
Salut
svp, je voudrai savoir le cout en nombre d'ES et en temps CPU des algorithmes de jointure : nested-loop , tri-fusion et hash-join dans les bases des données orientées objet.
Merci d'avance.
Soit n et m les cardinalité des tables en jeu des deux côté de la jointure...
tri fusion = n + m si les jointures sont faites sur des clefs indexées (cas de la clef primaire, et doit normalement être le cas de la clef étrangère), donc, algo de cout minimal
nested loop = n x m, c'est à dire le pire si n et m sont >> 1
hash-join : cout très difficile à déterminer, mais entre les deux en général :
1) cout du calcul de la transformation de la données en clef de hachage
2) cout de placement de la clef hachée dans un "baquet"
3) cout de rapprochement des "baquets" (voisi du tri fusion)
4) cout de recherche d'une valeur à l'intérieur du baquet
A +