Η εξωτερική διαλογή είναι μια τεχνική που χρησιμοποιείται για να χειριστεί μεγάλα σύνολα δεδομένων που δεν ταιριάζουν στην κύρια μνήμη. Μια βασική πτυχή της εξωτερικής διαλογής είναι ο υπολογισμός του κόστους συγχώνευσης, η οποία βοηθά στον καθορισμό της απόδοσης της διαδικασίας διαλογής. Αυτός ο οδηγός παρέχει μια βήμα προς βήμα προσέγγιση στην κατανόηση και τον υπολογισμό του κόστους συγχώνευσης στην εξωτερική διαλογή.

Κατανόηση Εξωτερικής Ταξινόμησης

Η εξωτερική διαλογή περιλαμβάνει διαίρεση των δεδομένων σε διαχειρίσιμα κομμάτια, διαλογή κάθε κομματιού ξεχωριστά, και στη συνέχεια συγχώνευση αυτών των ταξινομημένων κομματιών σε ένα ενιαίο ταξινομημένο αρχείο. Η διαδικασία συγχώνευσης μπορεί να πραγματοποιηθεί σε πολλαπλές πάσες, ανάλογα με τον αριθμό των κομματιών και τη διαθέσιμη μνήμη.

Στοιχεία κόστους συγχώνευσης

Το κόστος συγχώνευσης εξαρτάται κυρίως από τον αριθμό των περασμάτων και το ποσό των δεδομένων που υποβάλλονται σε επεξεργασία κατά τη διάρκεια κάθε πρόσβασης. Επηρεάζεται από:

  • Ο αριθμός των αρχικών ταξινομημένων δρομών (chunks)
  • Ο αριθμός των αρχείων συγχωνεύθηκε ταυτόχρονα (fan-in)
  • Το συνολικό μέγεθος των δεδομένων

Υπολογισμός κόστους συγχώνευσης

Το συνολικό κόστος συγχώνευσης μπορεί να υπολογιστεί με τη χρήση του τύπου:

Κόστος ζεύξης = Αριθμός περασμάτων × Σύνολο δεδομένων που υποβάλλονται σε επεξεργασία σε κάθε πέρασμα

Για να καθορίσετε τον αριθμό των περασμάτων, χρησιμοποιήστε τον τύπο:

Αριθμός περασμάτων = logfan-in (Αριθμός αρχικών τρεξίμων)

Για παράδειγμα, αν υπάρχουν 16 αρχικές διαδρομές και το σύστημα μπορεί να συγχωνεύσει 4 αρχεία ταυτόχρονα, τότε:

Αριθμός περασμάτων = log4 16 = 2

Τα συνολικά δεδομένα που επεξεργάζονται σε κάθε πέρασμα ισούται με το συνολικό μέγεθος όλων των δεδομένων που συγχωνεύονται κατά τη διάρκεια αυτής της πρόσβασης.