Κατακερματισμός στο DBMS: Τεχνικές στατικές και δυναμικές κατακερματισμοί
Τι είναι το Hashing στο DBMS;
Στο DBMS, ο κατακερματισμός είναι μια τεχνική για την άμεση αναζήτηση της θέσης των επιθυμητών δεδομένων στο δίσκο χωρίς τη χρήση δομής ευρετηρίου. Η μέθοδος κατακερματισμού χρησιμοποιείται για την ευρετηρίαση και την ανάκτηση στοιχείων σε μια βάση δεδομένων, καθώς είναι ταχύτερη η αναζήτηση αυτού του συγκεκριμένου αντικειμένου χρησιμοποιώντας το συντομότερο κατακερματισμένο κλειδί αντί της αρχικής του τιμής. Τα δεδομένα αποθηκεύονται με τη μορφή μπλοκ δεδομένων των οποίων η διεύθυνση δημιουργείται με την εφαρμογή μιας συνάρτησης κατακερματισμού στη θέση μνήμης όπου αποθηκεύονται αυτές οι εγγραφές, γνωστή ως μπλοκ δεδομένων ή κάδος δεδομένων.
Γιατί χρειαζόμαστε Hashing;
Ακολουθούν οι καταστάσεις στο DBMS όπου πρέπει να εφαρμόσετε τη μέθοδο Hashing:
- Για μια τεράστια δομή βάσης δεδομένων, είναι δύσκολο να αναζητήσετε όλες τις τιμές ευρετηρίου σε όλο το επίπεδο και, στη συνέχεια, πρέπει να φτάσετε στο μπλοκ δεδομένων προορισμού για να λάβετε τα επιθυμητά δεδομένα.
- Η μέθοδος κατακερματισμού χρησιμοποιείται για την ευρετηρίαση και την ανάκτηση στοιχείων σε μια βάση δεδομένων, καθώς είναι ταχύτερη η αναζήτηση αυτού του συγκεκριμένου αντικειμένου χρησιμοποιώντας το συντομότερο κατακερματισμένο κλειδί αντί της αρχικής του τιμής.
- Ο κατακερματισμός είναι μια ιδανική μέθοδος για τον υπολογισμό της άμεσης θέσης μιας εγγραφής δεδομένων στο δίσκο χωρίς τη χρήση δομής ευρετηρίου.
- Είναι επίσης μια χρήσιμη τεχνική για την εφαρμογή λεξικών.
Σημαντικές ορολογίες στο Hashing
Ακολουθούν σημαντικές ορολογίες που χρησιμοποιούνται στο Hashing:
- Κάδος δεδομένων – Οι κάδοι δεδομένων είναι θέσεις μνήμης όπου αποθηκεύονται οι εγγραφές. Είναι επίσης γνωστό ως Unit Of Storage.
- Κλειδί: Μια Κλειδί DBMS είναι ένα χαρακτηριστικό ή ένα σύνολο χαρακτηριστικών που σας βοηθά να προσδιορίσετε μια σειρά (πλούδα) σε μια σχέση (πίνακα). Αυτό σας επιτρέπει να βρείτε τη σχέση μεταξύ δύο πινάκων.
- Λειτουργία κατακερματισμού: Μια συνάρτηση κατακερματισμού, είναι μια συνάρτηση αντιστοίχισης που αντιστοιχίζει όλο το σύνολο των κλειδιών αναζήτησης στη διεύθυνση όπου τοποθετούνται οι πραγματικές εγγραφές.
- Γραμμική Ανίχνευση – Η γραμμική ανίχνευση είναι ένα σταθερό διάστημα μεταξύ των ανιχνευτών. Σε αυτήν τη μέθοδο, το επόμενο διαθέσιμο μπλοκ δεδομένων χρησιμοποιείται για την εισαγωγή της νέας εγγραφής, αντί για αντικατάσταση στην παλαιότερη εγγραφή.
- Τετραγωνική ανίχνευση– Σας βοηθά να προσδιορίσετε τη νέα διεύθυνση του κάδου. Σας βοηθά να προσθέσετε το διάστημα μεταξύ των ανιχνευτών προσθέτοντας τη διαδοχική έξοδο του τετραγωνικού πολυωνύμου στην αρχική τιμή που δίνεται από τον αρχικό υπολογισμό.
- Ευρετήριο κατακερματισμού – Είναι μια διεύθυνση του μπλοκ δεδομένων. Μια συνάρτηση κατακερματισμού θα μπορούσε να είναι μια απλή μαθηματική συνάρτηση ακόμη και μια πολύπλοκη μαθηματική συνάρτηση.
- Double Hashing -Double Ο κατακερματισμός είναι μια μέθοδος προγραμματισμού υπολογιστή που χρησιμοποιείται σε πίνακες κατακερματισμού για την επίλυση ζητημάτων σύγκρουσης.
- Υπερχείλιση κάδου: Η συνθήκη υπερχείλισης κάδου ονομάζεται σύγκρουση. Αυτό είναι ένα μοιραίο στάδιο για κάθε στατικό πρέπει να λειτουργήσει.
Τύποι Τεχνικών Κατακερματισμού
Υπάρχουν κυρίως δύο τύποι μεθόδων/τεχνικών κατακερματισμού SQL:
- Στατικό κατακερματισμό
- Δυναμική κατακερματισμός
στατικό κατακερματισμό
Στο στατικό κατακερματισμό, η προκύπτουσα διεύθυνση του κάδου δεδομένων θα παραμένει πάντα η ίδια.
Επομένως, εάν δημιουργήσετε μια διεύθυνση για να πούμε Student_ID = 10 χρησιμοποιώντας τη λειτουργία κατακερματισμού mod(3), η προκύπτουσα διεύθυνση κάδου θα είναι πάντα 1. Έτσι, δεν θα δείτε καμία αλλαγή στη διεύθυνση του κάδου.
Επομένως, σε αυτήν τη μέθοδο στατικού κατακερματισμού, ο αριθμός των κάδων δεδομένων στη μνήμη παραμένει πάντα σταθερός.
Στατικές συναρτήσεις κατακερματισμού
- Εισαγωγή εγγραφής: Όταν μια νέα εγγραφή χρειάζεται να εισαχθεί στον πίνακα, μπορείτε να δημιουργήσετε μια διεύθυνση για τη νέα εγγραφή χρησιμοποιώντας το κλειδί κατακερματισμού της. Όταν δημιουργείται η διεύθυνση, η εγγραφή αποθηκεύεται αυτόματα σε αυτήν τη θέση.
- Αναζήτηση: Όταν χρειάζεται να ανακτήσετε την εγγραφή, η ίδια συνάρτηση κατακερματισμού θα πρέπει να είναι χρήσιμη για την ανάκτηση της διεύθυνσης του κάδου όπου θα πρέπει να αποθηκεύονται τα δεδομένα.
- Διαγράψτε μια εγγραφή: Χρησιμοποιώντας τη συνάρτηση κατακερματισμού, μπορείτε πρώτα να ανακτήσετε την εγγραφή που θέλετε να διαγράψετε. Στη συνέχεια, μπορείτε να αφαιρέσετε τις εγγραφές για αυτήν τη διεύθυνση στη μνήμη.
Ο στατικός κατακερματισμός χωρίζεται περαιτέρω σε
- Άνοιγμα κατακερματισμού
- Κλείσιμο κατακερματισμού.
Άνοιγμα κατακερματισμού
Στη μέθοδο Open hashing, αντί να αντικατασταθεί παλαιότερη, χρησιμοποιείται το επόμενο διαθέσιμο μπλοκ δεδομένων για την εισαγωγή της νέας εγγραφής. Αυτή η μέθοδος είναι επίσης γνωστή ως γραμμική ανίχνευση.
Για παράδειγμα, το A2 είναι μια νέα εγγραφή που θέλετε να εισαγάγετε. Η συνάρτηση κατακερματισμού δημιουργεί διεύθυνση ως 222. Αλλά είναι ήδη κατειλημμένη από κάποια άλλη τιμή. Γι' αυτό το σύστημα αναζητά τον επόμενο κάδο δεδομένων 501 και του εκχωρεί Α2.
Κλείσιμο κατακερματισμού
Στη μέθοδο κλεισίματος κατακερματισμού, όταν οι κάδοι είναι γεμάτοι, εκχωρείται ένας νέος κάδος για τον ίδιο κατακερματισμό και το αποτέλεσμα συνδέεται μετά το προηγούμενο.
Δυναμική κατακερματισμός
Ο δυναμικός κατακερματισμός προσφέρει έναν μηχανισμό στον οποίο οι κάδοι δεδομένων προστίθενται και αφαιρούνται δυναμικά και κατ' απαίτηση. Σε αυτόν τον κατακερματισμό, η συνάρτηση κατακερματισμού σάς βοηθά να δημιουργήσετε μεγάλο αριθμό τιμών.
Διαφορά μεταξύ Ordered Indexing και Hashing
Παρακάτω είναι οι βασικές διαφορές μεταξύ Ευρετηρίασης και Κατακερματισμού
παράμετροι | Ευρετηρίαση παραγγελιών | Hashing |
---|---|---|
Αποθήκευση διεύθυνσης | Οι διευθύνσεις στη μνήμη ταξινομούνται σύμφωνα με μια τιμή κλειδιού που ονομάζεται πρωτεύον κλειδί | Οι διευθύνσεις δημιουργούνται πάντα χρησιμοποιώντας μια συνάρτηση κατακερματισμού στην τιμή κλειδιού. |
επίδοση | Μπορεί να μειωθεί όταν τα δεδομένα αυξάνονται στο αρχείο κατακερματισμού. Καθώς αποθηκεύει τα δεδομένα σε ταξινομημένη μορφή όταν εκτελείται οποιαδήποτε λειτουργία (εισαγωγή/διαγραφή/ενημέρωση) που μειώνει την απόδοσή του. | Η απόδοση του κατακερματισμού θα είναι καλύτερη όταν υπάρχει συνεχής προσθήκη και διαγραφή δεδομένων. Ωστόσο, όταν η βάση δεδομένων είναι τεράστια, τότε η οργάνωση αρχείων κατακερματισμού και η συντήρησή της θα είναι πιο δαπανηρή. |
Χρήση για | Προτιμάται για την ανάκτηση εύρους δεδομένων - που σημαίνει ότι κάθε φορά που υπάρχουν δεδομένα ανάκτησης για μια συγκεκριμένη περιοχή, αυτή η μέθοδος είναι μια ιδανική επιλογή. | Αυτή είναι μια ιδανική μέθοδος όταν θέλετε να ανακτήσετε μια συγκεκριμένη εγγραφή με βάση το κλειδί αναζήτησης. Ωστόσο, θα έχει καλή απόδοση μόνο όταν η συνάρτηση κατακερματισμού είναι στο κλειδί αναζήτησης. |
Διαχείριση μνήμης | Θα υπάρχουν πολλά αχρησιμοποίητα μπλοκ δεδομένων λόγω της λειτουργίας διαγραφής/ενημέρωσης. Αυτά τα μπλοκ δεδομένων δεν μπορούν να κυκλοφορήσουν για επαναχρησιμοποίηση. Γι' αυτό απαιτείται τακτική συντήρηση της μνήμης. | Στις στατικές και δυναμικές μεθόδους κατακερματισμού, η διαχείριση της μνήμης γίνεται πάντα. Η υπερχείλιση του κάδου αντιμετωπίζεται επίσης τέλεια για την επέκταση του στατικού κατακερματισμού. |
Τι είναι το Collision;
Η σύγκρουση κατακερματισμού είναι μια κατάσταση κατά την οποία ο κατακερματισμός που προκύπτει από δύο ή περισσότερα δεδομένα στο σύνολο δεδομένων, αντιστοιχίζει λανθασμένα την ίδια θέση στο πίνακας κατακερματισμού.
Πώς να αντιμετωπίσετε το Hashing Collision;
Υπάρχουν δύο τεχνικές που μπορείτε να χρησιμοποιήσετε για να αποφύγετε μια σύγκρουση κατακερματισμού:
- Ξανακάθισμα: Αυτή η μέθοδος, καλεί μια δευτερεύουσα συνάρτηση κατακερματισμού, η οποία εφαρμόζεται συνεχώς μέχρι να βρεθεί μια κενή υποδοχή, όπου θα πρέπει να τοποθετηθεί μια εγγραφή.
- Αλυσίδα: Η μέθοδος Chaining δημιουργεί μια Συνδεδεμένη λίστα στοιχείων των οποίων το κλειδί κατακερματίζεται στην ίδια τιμή. Αυτή η μέθοδος απαιτεί ένα επιπλέον πεδίο σύνδεσης σε κάθε θέση πίνακα.
Σύνοψη
- In DBMS, ο κατακερματισμός είναι μια τεχνική για την άμεση αναζήτηση της θέσης των επιθυμητών δεδομένων στο δίσκο χωρίς τη χρήση δομής ευρετηρίου.
- Η μέθοδος κατακερματισμού χρησιμοποιείται για την ευρετηρίαση και την ανάκτηση στοιχείων σε μια βάση δεδομένων, καθώς είναι ταχύτερη η αναζήτηση αυτού του συγκεκριμένου αντικειμένου χρησιμοποιώντας το συντομότερο κατακερματισμένο κλειδί αντί της αρχικής του τιμής.
- Κάδος δεδομένων, Κλειδί, Συνάρτηση κατακερματισμού, Γραμμική ανίχνευση, Τετραγωνική ανίχνευση, Ευρετήριο κατακερματισμού, Double Το Hashing, το Bucket Overflow είναι σημαντικές ορολογίες που χρησιμοποιούνται στον κατακερματισμό
- Δύο τύποι μεθόδων κατακερματισμού είναι 1) ο στατικός κατακερματισμός 2) ο δυναμικός κατακερματισμός
- Στο στατικό κατακερματισμό, η προκύπτουσα διεύθυνση του κάδου δεδομένων θα παραμένει πάντα η ίδια.
- Ο δυναμικός κατακερματισμός προσφέρει έναν μηχανισμό στον οποίο οι κάδοι δεδομένων προστίθενται και αφαιρούνται δυναμικά και κατ' απαίτηση.
- Με τη σειρά Οι διευθύνσεις ευρετηρίου στη μνήμη ταξινομούνται σύμφωνα με μια κρίσιμη τιμή, ενώ στον κατακερματισμό οι διευθύνσεις δημιουργούνται πάντα χρησιμοποιώντας μια συνάρτηση κατακερματισμού στην τιμή κλειδιού.
- Η σύγκρουση κατακερματισμού είναι μια κατάσταση κατά την οποία ο κατακερματισμός που προκύπτει από δύο ή περισσότερα δεδομένα στο σύνολο δεδομένων, αντιστοιχίζει λανθασμένα την ίδια θέση στον πίνακα κατακερματισμού.
- Το rehashing και το chaining είναι δύο μέθοδοι που σας βοηθούν να αποφύγετε τη σύγκρουση κατακερματισμού.