Ευρετηρίαση σε DBMS: Τι είναι, Τύποι ευρετηρίων με ΠΑΡΑΔΕΙΓΜΑΤΑ

Τι είναι η ευρετηρίαση;

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

Ένα ευρετήριο:

• Δέχεται ένα κλειδί αναζήτησης ως είσοδο.
• Επιστρέφει αποτελεσματικά μια συλλογή από αντίστοιχες εγγραφές.

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

Τύποι ευρετηρίασης στο DBMS

Η δημιουργία ευρετηρίου σε μια βάση δεδομένων ορίζεται με βάση τα χαρακτηριστικά δημιουργίας ευρετηρίου της. Οι δύο κύριοι τύποι μεθόδων δημιουργίας ευρετηρίου είναι:

• Πρωτογενής Ευρετηρίαση
• Δευτερεύουσα Ευρετηρίαση

Πρωτεύον ευρετήριο στο DBMS

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

Ο κύριος δείκτης χωρίζεται επίσης περαιτέρω σε δύο τύπους:

• Πυκνός δείκτης
• Αραιός δείκτης

Πυκνός δείκτης

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

Αραιός δείκτης

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

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

Παρακάτω είναι ένα παράδειγμα ευρετηρίου βάσης δεδομένων ενός αραιού ευρετηρίου.

Πυκνός Δείκτης έναντι Αραιού Δείκτη

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

Άποψη	Πυκνός δείκτης	Αραιός δείκτης
καταχωρήσεις	Ένα ανά κλειδί αναζήτησης	Ένα ανά μπλοκ
Χώρος	Περισσότερο	Less
Ταχύτητα αναζήτησης	Ταχύτερη	Βραδύτερη
Συντήρηση	υψηλότερη	Χαμηλώστε

Δευτερεύων ευρετήριο στο DBMS

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

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

Παράδειγμα δευτερεύοντος δείκτη

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

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

Clusterευρετήριο στο DBMS

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

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

Θεωρούνται ως μία μόνο συστάδα και ο δείκτης δείχνει την συστάδα ως σύνολο. Εδώ, το Department_no είναι ένα μη μοναδικό κλειδί.

Τι είναι ένας Πολυεπίπεδος Δείκτης;

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

Δείκτης B-Tree

Το ευρετήριο B-tree είναι η πιο ευρέως χρησιμοποιούμενη δομή δεδομένων για την ευρετηρίαση που βασίζεται σε δέντρα στο DBMS. Είναι μια πολυεπίπεδη μορφή ευρετηρίασης που βασίζεται σε δέντρα και χρησιμοποιεί ισορροπημένη δυαδικά δέντρα αναζήτησηςΌλοι οι κόμβοι φύλλων του B-δέντρου περιέχουν τους πραγματικούς δείκτες δεδομένων.

Επιπλέον, όλοι οι κόμβοι-φύλλα είναι διασυνδεδεμένοι με μια συνδεδεμένη λίστα, η οποία επιτρέπει σε ένα B-δέντρο να υποστηρίζει τόσο τυχαία όσο και διαδοχική πρόσβαση.

• Οι κόμβοι φύλλων πρέπει να έχουν μεταξύ 2 και 4 τιμών.
• Κάθε διαδρομή από τη ρίζα σε ένα φύλλο έχει ως επί το πλείστον ίσο μήκος.
• Οι μη-φύλλοι κόμβοι εκτός από τον ριζικό κόμβο έχουν μεταξύ 3 και 5 θυγατρικούς κόμβους.
• Κάθε κόμβος που δεν είναι ρίζα ή φύλλο έχει μεταξύ n/2 και n παιδιά.

Όπου κυριαρχούν οι αναζητήσεις ακριβούς αντιστοίχισης και οι σαρώσεις εύρους είναι σπάνιες, κατακερματισμός μπορεί να είναι μια ταχύτερη εναλλακτική λύση σε σχέση με ένα ευρετήριο B-tree.

Πλεονεκτήματα της ευρετηρίασης

Τα σημαντικά πλεονεκτήματα της ευρετηρίασης είναι:

• Βοηθά στη μείωση του συνολικού αριθμού λειτουργιών εισόδου/εξόδου που απαιτούνται για την ανάκτηση δεδομένων, επομένως δεν χρειάζεται να έχετε πρόσβαση σε μια γραμμή απευθείας από τον πίνακα.
• Προσφέρει στους χρήστες ταχύτερη αναζήτηση και ανάκτηση δεδομένων.
• Μπορεί να μειώσει τον χώρο στον πίνακα, επειδή δεν χρειάζεται να αποθηκεύσετε το ROWID στο ευρετήριο για κάθε συνδεδεμένη γραμμή.
• Τα δεδομένα στους κόμβους φύλλων είναι ήδη ταξινομημένα με βάση την τιμή του κλειδιού.

Μειονεκτήματα της ευρετηρίασης

Τα σημαντικά μειονεκτήματα της δημιουργίας δεικτών είναι:

• Για να εκτελέσετε ευρετηρίαση, χρειάζεστε ένα πρωτεύον κλειδί στον πίνακα με μια μοναδική τιμή.
• Δεν μπορείτε να δημιουργήσετε ένα άλλο ευρετήριο σε δεδομένα που είναι ήδη οργανωμένα σε ευρετήριο με τον ίδιο τρόπο.
• Δεν επιτρέπεται να χωρίσετε έναν πίνακα οργανωμένο με ευρετήριο.
• Η δημιουργία ευρετηρίου μειώνει την απόδοση στα ερωτήματα INSERT, DELETE και UPDATE.

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