Κατακερματισμός στο DBMS: Τεχνικές στατικές και δυναμικές κατακερματισμοί

⚡ Έξυπνη Σύνοψη

Ο κατακερματισμός (hashing) στο DBMS είναι μια τεχνική που υπολογίζει την τοποθεσία μιας εγγραφής στο δίσκο απευθείας από το κλειδί της, χωρίς να χρειάζεται να περάσει ένα ευρετήριο. Μια συνάρτηση κατακερματισμού αντιστοιχίζει τα κλειδιά αναζήτησης σε κάδους δεδομένων και ο στατικός ή δυναμικός κατακερματισμός διαχειρίζεται τον τρόπο με τον οποίο αυτοί οι κάδοι μεγαλώνουν.

⚡ Βασική ιδέα: Μια συνάρτηση κατακερματισμού μετατρέπει ένα κλειδί σε μια διεύθυνση κάδου, επομένως μια εγγραφή βρίσκεται σε ένα βήμα και όχι μέσω διέλευσης από ευρετήριο.
🪣 Κάδος δεδομένων: Η θέση μνήμης ή η μονάδα αποθήκευσης όπου τοποθετούνται εγγραφές με το ίδιο hash.
📌 Στατικός κατακερματισμός: Ο αριθμός των κάδων είναι σταθερός, επομένως ένα δεδομένο κλειδί αντιστοιχεί πάντα στην ίδια διεύθυνση.
📈 Δυναμικό Hashing: Οι κάδοι προστίθενται και αφαιρούνται κατ' απαίτηση καθώς αλλάζει ο όγκος δεδομένων.
💥 Σύγκρουση: Χάρτης δύο κλειδιώνping στον ίδιο κάδο, επιλύεται με ανίχνευση, επανάληψη κατακερματισμού ή αλυσιδωτή σύνδεση.
🔍 καλύτερα Για: Αναζητήσεις ακριβούς αντιστοίχισης στο κλειδί αναζήτησης, όπου ο κατακερματισμός υπερτερεί της διατεταγμένης ευρετηρίασης.
📊 Ανταλλαγή: Διατεταγμένες νίκες ευρετηρίασης για ερωτήματα εύρους· νίκες κατακερματισμού για εισαγωγές σταθερών και αναζητήσεις σημείων.

Περισσότερα

Τι είναι το Hashing στο DBMS;

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

Γιατί χρειαζόμαστε κατακερματισμό;

Ακολουθούν οι περιπτώσεις σε ένα ΣΔΒΔ όπου πρέπει να εφαρμόσετε τη μέθοδο κατακερματισμού:

Για μια τεράστια δομή βάσης δεδομένων, είναι δύσκολο να αναζητήσετε όλες τις τιμές του δείκτη σε όλα τα επίπεδά τους και στη συνέχεια να φτάσετε στο μπλοκ δεδομένων προορισμού για να λάβετε τα επιθυμητά δεδομένα.
Ο κατακερματισμός χρησιμοποιείται για την ευρετηρίαση και την ανάκτηση στοιχείων σε μια βάση δεδομένων, επειδή είναι πιο γρήγορο να αναζητήσετε ένα συγκεκριμένο στοιχείο χρησιμοποιώντας το μικρότερο κατακερματισμένο κλειδί από την αρχική τιμή.
Ο κατακερματισμός (hashing) είναι μια ιδανική μέθοδος για τον υπολογισμό της άμεσης θέσης μιας εγγραφής δεδομένων στον δίσκο χωρίς τη χρήση δομής ευρετηρίου.
Είναι επίσης μια χρήσιμη τεχνική για την εφαρμογή λεξικών.

Σημαντικές ορολογίες στο Hashing

Ακολουθούν σημαντικές ορολογίες που χρησιμοποιούνται στο hashing:

Κάδος δεδομένων: Οι κάδοι δεδομένων είναι θέσεις μνήμης όπου αποθηκεύονται οι εγγραφές. Είναι επίσης γνωστή ως μονάδα αποθήκευσης.
Κλειδί: a Κλειδί DBMS είναι ένα χαρακτηριστικό ή ένα σύνολο χαρακτηριστικών που σας βοηθά να αναγνωρίσετε μια γραμμή (πλειάδα) σε μια σχέση (πίνακα).
Συνάρτηση κατακερματισμού: ένας χάρτηςping συνάρτηση που αντιστοιχίζει όλο το σύνολο των κλειδιών αναζήτησης στη διεύθυνση όπου τοποθετούνται οι πραγματικές εγγραφές.
Γραμμική ανίχνευση: ένα σταθερό διάστημα μεταξύ των ανιχνευτών. Σε αυτήν τη μέθοδο, το επόμενο διαθέσιμο μπλοκ δεδομένων χρησιμοποιείται για την εισαγωγή της νέας εγγραφής, αντί να αντικαθίσταται η παλαιότερη εγγραφή.
Τετραγωνική Διερεύνηση: βοηθά στον προσδιορισμό της νέας διεύθυνσης κάδου προσθέτοντας την διαδοχική έξοδο ενός τετραγωνικού πολυωνύμου στην αρχική τιμή που δίνεται από τον αρχικό υπολογισμό.
Δείκτης κατακερματισμού: η διεύθυνση του μπλοκ δεδομένων. Μια συνάρτηση κατακερματισμού θα μπορούσε να είναι μια απλή μαθηματική συνάρτηση ή μια σύνθετη.
Double Κατακερματισμός: μια μέθοδος που χρησιμοποιείται σε πίνακες κατακερματισμού για την επίλυση συγκρούσεων εφαρμόζοντας μια δεύτερη συνάρτηση κατακερματισμού.
Υπερχείλιση κάδου: Η συνθήκη υπερχείλισης κάδου ονομάζεται σύγκρουση. Αυτό είναι ένα μοιραίο στάδιο για οποιαδήποτε στατική συνάρτηση κατακερματισμού.

Τύποι Τεχνικών Κατακερματισμού

Υπάρχουν κυρίως δύο τύποι τεχνικών κατακερματισμού στο DBMS:

Στατικό κατακερματισμό
Δυναμική κατακερματισμός

Τα δύο διαφέρουν κυρίως ως προς το αν ο αριθμός των κάδων είναι σταθερός, όπως εξηγείται στις επόμενες δύο ενότητες.

Στατικό κατακερματισμό

Στο στατικό κατακερματισμό, η προκύπτουσα διεύθυνση κάδου δεδομένων θα παραμένει πάντα η ίδια.

Επομένως, αν δημιουργήσετε μια διεύθυνση για, ας πούμε, Student_ID = 10 χρησιμοποιώντας τη συνάρτηση κατακερματισμού mod(3), η προκύπτουσα διεύθυνση κάδου θα είναι πάντα 1Επομένως, δεν θα δείτε καμία αλλαγή στη διεύθυνση κάδου.

Επομένως, στη μέθοδο στατικού κατακερματισμού, ο αριθμός των κάδων δεδομένων στη μνήμη παραμένει πάντα σταθερός.

Στατικές συναρτήσεις κατακερματισμού

Εισαγωγή εγγραφής: Όταν χρειάζεται να εισαχθεί μια νέα εγγραφή στον πίνακα, δημιουργείτε μια διεύθυνση για αυτήν χρησιμοποιώντας το κλειδί κατακερματισμού της. Μόλις δημιουργηθεί η διεύθυνση, η εγγραφή αποθηκεύεται σε αυτήν την τοποθεσία.
Ερευνητικός: Όταν χρειάζεται να ανακτήσετε την εγγραφή, η ίδια συνάρτηση κατακερματισμού χρησιμοποιείται για την ανάκτηση της διεύθυνσης του κάδου όπου είναι αποθηκευμένα τα δεδομένα.
Διαγραφή εγγραφής: Χρησιμοποιώντας τη συνάρτηση κατακερματισμού, ανακτάτε πρώτα την εγγραφή που θέλετε να διαγράψετε και, στη συνέχεια, την αφαιρείτε από αυτήν τη διεύθυνση στη μνήμη.

Ο στατικός κατακερματισμός χωρίζεται περαιτέρω σε:

Άνοιγμα κατακερματισμού
Κλειστός κατακερματισμός

Άνοιγμα κατακερματισμού

Στη μέθοδο ανοιχτού κατακερματισμού, αντί να αντικατασταθεί η παλαιότερη εγγραφή, χρησιμοποιείται το επόμενο διαθέσιμο μπλοκ δεδομένων για την εισαγωγή της νέας εγγραφής. Αυτή η μέθοδος είναι επίσης γνωστή ως γραμμική ανίχνευση.

Για παράδειγμα, το A2 είναι μια νέα εγγραφή που θέλετε να εισαγάγετε. Η συνάρτηση κατακερματισμού δημιουργεί τη διεύθυνση 222, αλλά είναι ήδη κατειλημμένη από μια άλλη τιμή. Αυτός είναι ο λόγος για τον οποίο το σύστημα αναζητά τον επόμενο κάδο δεδομένων, 501, και του αντιστοιχίζει το A2.

Πώς λειτουργεί το ανοιχτό hashing με γραμμική ανίχνευση — Πώς λειτουργεί το Open Hash

Κλειστό Hashing

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

Δυναμική κατακερματισμός

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

Διαφορά μεταξύ ταξινομημένης ευρετηρίασης και κατακερματισμού

Παρακάτω παρατίθενται οι βασικές διαφορές μεταξύ ευρετηρίασης και κατακερματισμού:

Παράμετροι	Ταξινομημένη Ευρετηρίαση	Hashing
Αποθήκευση διεύθυνσης	Οι διευθύνσεις στη μνήμη ταξινομούνται σύμφωνα με μια τιμή κλειδιού που ονομάζεται πρωτεύον κλειδί.	Οι διευθύνσεις δημιουργούνται πάντα χρησιμοποιώντας μια συνάρτηση κατακερματισμού στην τιμή κλειδιού.
💪 Βελτίωση της απόδοσης στην άσκηση	Μπορεί να μειωθεί καθώς αυξάνονται τα δεδομένα, επειδή τα δεδομένα αποθηκεύονται ταξινομημένα και κάθε εισαγωγή, διαγραφή ή ενημέρωση τα αναδιατάσσει.	Η απόδοση είναι βέλτιστη με συνεχή προσθήκη και διαγραφή δεδομένων. Για μια τεράστια βάση δεδομένων, η συντήρηση του αρχείου κατακερματισμού γίνεται πιο δαπανηρή.
Χρήση για	Προτιμάται για ανάκτηση εύρους, όπου ανακτώνται δεδομένα για ένα συγκεκριμένο εύρος.	Ιδανικό για την ανάκτηση μιας συγκεκριμένης εγγραφής με βάση το κλειδί αναζήτησης και αποδίδει καλά μόνο όταν η συνάρτηση κατακερματισμού βρίσκεται στο κλειδί αναζήτησης.
Διαχείριση μνήμης	Πολλά αχρησιμοποίητα μπλοκ δεδομένων προκύπτουν από λειτουργίες διαγραφής και ενημέρωσης και δεν μπορούν να αποδεσμευτούν για επαναχρησιμοποίηση, επομένως απαιτείται τακτική συντήρηση.	Στο στατικό και δυναμικό κατακερματισμό, η μνήμη διαχειρίζεται πάντα και η υπερχείλιση κάδου χειρίζεται για την επέκταση του στατικού κατακερματισμού.

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

Τι είναι το Collision;

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

Πώς να αντιμετωπίσετε μια σύγκρουση κατακερματισμού

Υπάρχουν δύο τεχνικές που μπορείτε να χρησιμοποιήσετε για να αποφύγετε μια σύγκρουση κατακερματισμού:

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

Συχνές Ερωτήσεις

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

Για ερωτήματα εύρους. Ο κατακερματισμός διασκορπίζει τα κλειδιά σε διάφορους κάδους, επομένως ένα ερώτημα μεταξύ ή μεγαλύτερο από δεν μπορεί να τα ταξινομήσει με τη σειρά. Ένα ταξινομημένο ευρετήριο διατηρεί τα κλειδιά ταξινομημένα και ταιριάζει καλύτερα εκεί.

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

Τα συστήματα τεχνητής νοημοσύνης χρησιμοποιούν τον κατακερματισμό (hashing) για γρήγορη αναζήτηση χαρακτηριστικών και για το κόλπο του κατακερματισμού, το οποίο αντιστοιχίζει κατηγορίες υψηλής πληθικότητας σε ένα σταθερό διάνυσμα. Ο κατακερματισμός ομοιότητας ομαδοποιεί επίσης αποτελεσματικά σχεδόν διπλότυπες εγγραφές.

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