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

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

Μια ΣΚ πρέπει να έχει τα εξής χαρακτηριστικά:

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

OPEN

READ_DIRECT

WRITE_DIRECT

UPDATE

CLOSE

EOF

VALID

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

Ένας τρόπος για να σκεφτούμε τη ΣΚ είναι ο εξής:

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

Η ΣΚ μπορεί να θεωρηθεί κι ως μια απεικόνιση του χώρου των διευθύνσεων του κλειδιού προς το χώρο διευθύνσεων του αρχείου. Το αρχείο έχει ένα καθορισμένο αριθμό διευθύνσεων που θα καταλάβουν οι εγγραφές έτσι ώστε : 0 < R < N, για ένα αρχείο με Ν διαφορετικές διευθύνσεις. Το κλειδί όμως λαμβάνει τιμές από μεγαλύτερο σύνολο διευθύνσεων. Π.χ. το κλειδί μπορεί να είναι ένα όνομα που αντιστοιχεί σε αλφαριθμητικό 30 χαρακτήρων. Κάθε χαρακτήρας στον κώδικα ASCII μπορεί να λάβει 256 διαφορετικές τιμές, άρα το σύνολο ορισμού του κλειδιού είναι 256³⁰. Είναι προφανές ότι είναι αδύνατο να απεικονίσουμε μονοσήμαντα ένα τόσο μεγάλο πεδίο ορισμού σε ένα τόσο μικρό σύνολο διευθύνσεων στο αρχείο. Γι’ αυτό τα συνώνυμα είναι αναπόφευκτα. Εκείνο τελικά που επιδιώκουμε είναι η μη συχνή εμφάνιση συνωνύμων όπως συμβαίνει με τυχαίους αριθμούς. Για να μετατρέψουμε ένα κλειδί σε αριθμό εγγραφής θα πρέπει το κλειδί να μπορούμε να το χειριστούμε σαν να ήταν αριθμός. Βέβαια όταν το κλειδί είναι αριθμητικού τύπου δεν υπάρχει πρόβλημα. Αν όμως είναι αλφαβητικό ή αλφαριθμητικό τότε θα πρέπει πρώτα να μετατραπεί σε αριθμητικό. Η πράξη αυτή είναι γνωστή ως αναδίπλωση (folding) του κλειδιού.

Μια μέθοδος μετατροπής αλφαριθμητικού κλειδιού σε αριθμητικό μπορεί να είναι:

Εικόνα 7.1

Χωρίζουμε δυο-δυο τους ASCII αριθμούς που αντιστοιχούν σε κάθε χαρακτήρα του ονόματος και τους αθροίζουμε

7679+8769+7676+3232+3232+3232 = 33820

Δυστυχώς αυτός ο αριθμός σε κάποιους μικρο-ΗΥ θα δημιουργήσει πρόβλημα μια και οι integer τύπου αριθμοί δεν μπορούν να υπερβούν την τιμή 32767 γιατί προκαλείται overflow errors ή επιστρέφουν αρνητικό αποτέλεσμα. Για να αποφύγουμε αυτό το πρόβλημα εφαρμόζουμε τα εξής:

Ας υποθέσουμε ότι τα κλειδιά σχηματίζονται από κεφαλαία αγγλικά γράμματα ή κενά, άρα ο μεγαλύτερος προσθετέος είναι ο 9090 (αντιστοιχεί στο ΖΖ). Έστω ότι επιλέγουμε τον αριθμό 19937 ως τον μεγαλύτερο ενδιάμεσο αποτέλεσμα. Ο αριθμός αυτός διαφέρει από 32767 πολύ περισσότερο από 9090 μονάδες και για να είμαστε σίγουροι ότι δεν θα έχουμε προβλήματα υπερχείλισης εφαρμόζουμε σε κάθε ενδιάμεσο αποτέλεσμα διαίρεση με 19937

7679 + 8769 =16448 mod 19937 = 16448

16448 + 7676 = 24124 mod 19937 =4187

4187 + 3232 = 10651 mod 19937 = 10651

10651 + 3232 = 13883 mod 19937 = 13883

H παραπάνω διαδικασία είναι γνωστή ως «αναδιπλώνω και προσθέτω» (fold and add).

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

R = K mod N (1)

R = αριθμός εγγραφής

K = το κλειδί σε αριθμητική μορφή

N = αριθμός θέσεων στο αρχείο

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

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

Μια τέτοια περίπτωση είναι η εξής: στους ξένους φοιτητές και σε όσους δεν έχουν αριθμούς ταυτότητας συχνά τους δίνονται αριθμοί μητρώου της μορφής 999-99-xxxx, όπου τα ψηφία xxxx λαμβάνουν τιμές 0001, 0002, … Αυτοί οι αριθμοί κατακερματίζονται σε συνεχείς θέσεις με αποτέλεσμα τη δημιουργία αλυσίδας συνωνύμων. Η καλύτερη λύση είναι η χρήση αριθμών ταυτότητας της μορφής 999-ΥΥ-ΥΥΥΥ, όπου ΥΥΥΥ ψηφία που προκύπτουν από γεννήτορες τυχαίων (random generators). Έτσι επιλέγοντας τυχαία αριθμούς και μεγαλώνοντας το τμήμα του κλειδιού που σχηματίζεται τυχαία, οι αντίστοιχοι αριθμοί εγγραφής διασκορπίστηκαν σε μεγαλύτερο χώρο του αρχείου.

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

Η δημιουργία συνώνυμων είναι αναπόφευκτη με τη μέθοδο του κατακερματισμού. Η πιθανότητα k εγγραφές να κατακερματισθούν στην ίδιον αριθμό εγγραφής είναι :

(2)

Η παραπάνω σχέση μπορεί να προσεγγισθεί για μεγάλες τιμές του Ν με τη συνάρτηση Poisson.

(3)

f = παράγοντας φόρτισης (load factor)

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

Όσο ο παράγοντας φόρτισης τείνει προς το 100%, το ποσοστό των θέσεων όπου καμία εγγραφή δεν έχει κατακερματισθεί πλησιάζει το 1/e ή περίπου 0,368. Έτσι αφού μόνο μια εγγραφή μπορεί να αποθηκευθεί σε κάθε θέση του αρχείου, κάποια μέθοδος πρέπει να επινοηθεί για να μετακινηθούν τα συνώνυμα προς μη χρησιμοποιημένες θέσεις με τέτοιο όμως τρόπος που να μπορούν να εντοπισθούν γρήγορα όταν θα χρειασθεί.

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

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

Ένας απλός τρόπος οργάνωσης του αρχείου υπερχείλισης είναι ως σειριακό - χρονολογικό αρχείο. Όσο το πλήθος των εγγραφών είναι μικρό το κόστος αποτελεσματικότητας είναι αποδεκτό.

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

Προφανώς η αποθήκευση όλων των εγγραφών σ’ ένα αρχείο είναι προτιμότερη από την χρήση δυο ή περισσοτέρων αρχείων υπερχείλισης για την αποθήκευσή τους. Αυτό μπορεί να γίνει με διάφορους τρόπους. Ένας τρόπος είναι να διαμοιράσουμε το αρχείο σε 2 περιοχές. Μια μεγάλη που θα χρησιμοποιηθεί ως περιοχή κατακερματισμού και μια μικρή που θα χρησιμοποιηθεί ως περιοχή υπερχείλισης. Μια τέτοια λύση βέβαια θα αφήσει 37% των θέσεων να μην χρησιμοποιηθούν (με 100% παράγοντα φόρτισης). Προφανώς θα ήταν οικονομικότερο από άποψη χώρου αν με κάποιο τρόπο χρησιμοποιούνταν για τα συνώνυμα μια περιοχή που ούτως ή άλλως δεν θα χρησιμοποιούνταν.

Η γενική μέθοδος επανατοποθέτησης (reallocating) των συνωνύμων στο ίδιο βασικό αρχείο είναι η μέθοδος της ανοικτής διεύθυνσης (open addressing). Ανοικτή διεύθυνση ορίζεται ως η μέθοδος με την οποία μια προβλέψιμη ακολουθία θέσεων εξετάζεται ή ερευνάται μέχρι να βρεθεί κάποια άδεια θέση και το συνώνυμο τοποθετείται σ’ αυτή την άδεια θέση. Μια και η ακολουθία των θέσεων είναι προβλέψιμη η μέθοδος αυτή επαναλαμβάνεται. Κατά την αναζήτηση η ίδια ακολουθία ακολουθείται μέχρι να εντοπισθεί η εγγραφή. Υπάρχουν 2 μέθοδοι ανοικτής διεύθυνσης: της γραμμικής εξέτασης και του επανακερματισμού, που θα εξετασθούν στη συνέχεια.

Γραμμική εξέταση σημαίνει ότι όταν προκύπτει συνώνυμο το αρχείο εξετάζεται από κει και πέρα (forward) από την φυσική διεύθυνση της εγγραφής μέχρι να βρεθεί κενή θέση και τότε η εγγραφή αποθηκεύεται στην άδεια θέση. Η φυσική διεύθυνση (natural address) είναι η θέση που προκύπτει από τη ΣΚ εφαρμοζόμενη στο κλειδί εγγραφής. Σε περίπτωση που η φυσική διεύθυνση είναι κοντά στο τέλος του αρχείου και δεν υπάρχουν άδειες θέσεις τότε η εξέταση αρχίζει από την αρχή του αρχείου.

Οι αλγόριθμοι που χειρίζονται τις διαδικασίες της προσθήκης και της αναζήτησης εγγραφής με συγκεκριμένη τιμή κλειδιού είναι:

procedure Algor5_1(file, newrecord, n);

k := Fold(key(newrecord));              {fold the key if necessary}

r := k mod n;                                  {calculate the natural address}

READ_DIRECT(file, buffer, r);         {get slot at natural address}

WHILE VALID(file) DO BEGIN     {search for empty slot}

r := (r+1) mod n;                  {go to next slot wrap around if needed}

READ_DIRECT(file, buffer, r);

END; {empty slot is at r when loop exits}

WRITE_DIRECT(file, newrecord, r); {write the new record}

Read a record with specific key value (Algorithm 5_2)

logical function Algor5_2(file, buffer, givenkey, n);

{returns true iff matching record is found}

k := fold(givenkey);         {fold the key if necessary}

r := k mod n;                  {calculate the natural address}

READ_DIRECT(file, buffer, r);         {get slot at natural address}

WHILE valid(file) and key(buffer) ? givenkey DO BEGIN

r := (r+1) mod n;                     {calculate next address of linear probe}

READ_DIRECT(file, buffer, r); {get next record}

END;

IF key(buffer) = givenkey THEN Algor5_2 := true

            {record has been found}

ELSE Algor5_2 := false; {record does not exist}

Η γραμμική εξέταση για τη διαχείριση των συνωνύμων έχει και αρκετές δυσκολίες.

• Καθώς ο παράγοντας φόρτισης πλησιάζει το 100% κάποιες περιοχές θα είναι υπερπλήρεις. Από μετρήσεις φαίνεται ότι καθώς ο παράγοντας φόρτισης είναι περίπου 99% η μέση αναζήτηση φτάνει τις 25 εγγραφές. Η χειρότερη περίπτωση είναι για παράγοντα φόρτισης 99%, όπου η αναζήτηση μπορεί να υπερβεί τις 1000 εγγραφές για μεγάλα αρχεία. Έτσι αν ο παράγοντας φόρτισης διατηρηθεί κάτω από ένα λογικό όριο, π.χ. 85%, η αποτελεσματικότητα της μέθοδο θα μπορεί να είναι αποδεκτή και η χειρότερη περίπτωση θα κυμαίνεται μεταξύ 100 και 200 εγγραφών. Απ’ τη στιγμή που με τη γραμμική εξέταση εφαρμόζεται σειριακή αναζήτηση από τη θέση της φυσικής διεύθυνσης, η ομαδοποίηση εγγραφών (blocking) θα μπορούσε να μειώσει το πλήθος των φυσικών προσπελάσεων στο αρχείο. Δυστυχώς, δεν υπάρχει απλή και ρητή μέθοδος που να μας επιτρέπει να μετρήσουμε την επίδραση της ομαδοποίησης.

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

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

Μια άλλη προσέγγιση είναι να μην διαγραφεί η εγγραφή αλλά να σημειωθεί ως “εγκαταλελειμμένη” (abandoned). Ο αλγόριθμος 5_2 δεν θα σταματήσει μόλις βρει μια σημειωμένη εγγραφή, αλλά αυτή η εγγραφή θα μπορούσε να αντικατασταθεί από μια νέα εγγραφή τροποποιώντας κατάλληλα τον αλγόριθμο 5_1. Εγγραφές που έχουν σημειωθεί και δεν έχουν αντικατασταθεί, θα πρέπει να λαμβάνονται υπόψη στον υπολογισμό του παράγοντα φόρτισης. Με βάση αυτή την προσέγγιση, ο παρακάτω αλγόριθμος μπορεί να χρησιμοποιηθεί για την λογική διαγραφή εγγραφών χωρίς να αφήνονται οι αντίστοιχες θέσεις κενές. Η συνάρτηση REMOVE χρησιμοποιείται για να σημειωθεί η εγγραφή που βρίσκεται στο buffer ως εγκαταλελειμμένη.

logical function Algor5_3(file, givenkey, n);

{returns true iff matching record is found}

k := fold(givenkey);                            {fold the key if necessary}

r := k mod n;                                    {calculate the natural address}

READ_DIRECT(file, buffer, r);         {get slot at natural address}

r := (r+1) mod n;                              {calculate next address of linear probe}

READ_DIRECT(file, buffer, r); {get next record}

END;

IF key(buffer) = givenkey THEN BEGIN

REMOVE(buffer);              {set slot as abandoned}

UPDATE(file, buffer);         {write back flagged record}

Algor5_3 := true                  {record found and deleted}

ELSE Algor5_3 := false;              {record does not exist}

• Ανάγνωση όλων των εγγραφών του αρχείο χωρίς μια συγκεκριμένη σειρά

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

Η μέθοδος του επανακερματισμού είναι μια άλλη μέθοδος ανοικτής διεύθυνσης για τον προσδιορισμό μιας εναλλακτικής θέσης για το συνώνυμο μέσα στο βασικό αρχείο. Σ’ αυτή τη μέθοδο απαιτούνται δυο ΣΚ. Η πρώτη εφαρμόζεται στο αναδιπλωμένο κλειδί (R = K mod N). Αν η εγγραφή R είναι καταλημένη, έχουμε το φαινόμενο του συνώνυμου, όποτε εφαρμόζεται η 2η ΣΚ στο αναδιπλωμένο κλειδί.

D = (K mod J) + 1

J = πρώτος αριθμός μικρότερος του Ν. Το D δηλώνει μετατόπιση (displacement) από τον πραγματικό αριθμό εγγραφής R. Μια και R + D μπορεί να είναι αριθμός μεγαλύτερος του Ν γι’ αυτό η πρόσθεση γίνεται με mod Ν. Αυτό μπορεί να οδηγήσει σε αναζήτηση από την αρχή του αρχείου. Επειδή κάθε συνώνυμο θα αναζητηθεί σε διαφορετική ακολουθία θέσεων για να τοποθετηθεί, με τον επανακερματισμό αποφεύγεται η συμφόρηση που προκαλείται σε κάποιες περιοχές με την μέθοδο της γραμμικής εξέτασης. Αυτό με τη σειρά του έχει ως αποτέλεσμα την εξέταση λιγότερων εγγραφών. Βέβαια αφού η μετατόπιση D θα είναι σχεδόν πάντα μεγαλύτερη του παράγοντα ομαδοποίησης το πλεονέκτημα της ομαδοποίησης χάνεται.

Το πρόβλημα “πότε να σταματήσουμε μια ανεπιτυχή αναζήτηση” είναι παρόμοιο μ’ αυτό της γραμμικής εξέτασης. Η μόνη διαφορά είναι στην ακολουθία των εξεταζόμενων εγγραφών. Όπως και με τη γραμμική εξέταση, η καλύτερη λύση είναι πιθανώς να σημειωθούν οι εγγραφές που έχουν διαγραφεί λογικά ως εγκαταλειμμένες και όχι ως άδειες. Οι αλγόριθμοι που αναφέρονται στις βασικές διαδικασίες με βάση την μέθοδο του επακερματισμού είναι :

• Προσθήκη

Οι πρώτες R κατακερματισμένες εγγραφές ελέγχονται αν είναι κενές ή εγκαταλελειμμένες, η εγγραφή προστίθεται και η διαδικασία της Προσθήκης ολοκληρώνεται. Αν η θέση είναι καταλημένη τότε υπολογίζεται η μετατόπιση D και ελέγχεται η θέση (R+D) mod Ν. Επανεξετάζεται αν η θέση είναι ελεύθερη. Η διαδικασία επαναλαμβάνεται για τις θέσεις (R+2D) mod N, (R+3D) mod N, κτλ, μέχρι να εντοπισθεί ελεύθερη θέση. Στους παρακάτω αλγόριθμους η συνάρτηση ΑΒ έχει τιμή “αληθή”, αν η εγγραφή στον buffer έχει σημειωθεί ως “εγκαταλελειμμένη” αλλιώς έχει τιμή “ψευδή”.

Τα προβλήματα αυτής της μεθόδου είναι τα εξής :

• Για δοσμένο ζεύγος κλειδιών που οδηγούν σε συνώνυμα με βάση τη 1η ΣΚ, θα είναι ανεπιθύμητο να οδηγήσουν και πάλι σε συνώνυμα μετά την εφαρμογή και της 2ης ΣΚ. Με την χρήση διαφορετικών σταθερών στην ΣΚ αυτή η πιθανότητα μειώνεται σε 1/N*J.

• Το D πρέπει να είναι μεγαλύτερο του 0 αλλιώς η διαδικασία θα επαναλαμβάνεται επ’ άπειρον. Αυτό επιτυγχάνεται με τον όρο +1 που χρησιμοποιείται στον υπολογισμό του D.

• H διαδικασία θα επαναλαμβάνεται έπ’ άπειρον αν δεν συναντήσει κενή θέση. Αυτό μπορεί να συμβεί αν εξετάζεται επαναληπτικά το ίδιο σύνολο θέσεων αν και ενδεχόμενα να υπάρχουν σ’ άλλη περιοχή κενές θέσεις. Βέβαια αφού ο Ν είναι πρώτος αριθμός και D < Ν αυτό δεν μπορεί να συμβεί. Ακόμη το R εξαναγκάζεται να λάβει όλες τις τιμές πριν οποιαδήποτε επανάληψη τους.

Read a record with specific key value (Algorithm 5_5)

logical procedure Algor5_5(file, buffer, givenkey, n);

k := fold(givenkey);                                  {fold the key if necessary}

r := k mod n;                                          {calculate both hash functions}

d := (k mod j) +1;

READ_DIRECT(file, buffer, r);                      {get record at natural address}

WHILE VALID(file) and key(buffer) <>givenkey DO BEGIN

{iterate until a vacant slot or the record is found}

r := (r+d) mod n;

READ_DIRECT(file, buffer, r);

END;

IF VALID(file) and not Ab(buffer) THEN Algor5_5 := true

{record has been found}

ELSE Algor5_5 := false; {search is unsuccessful}

• Διαγραφή

logical function Algor5_6(file, givenkey, n);

{returns true iff matching record is found and deleted}

k := fold(givenkey); {fold the key if necessary}

r := k mod n; {calculate both hash functions}

d := (k mod j)+1;

READ_DIRECT(file, buffer, r);                  {get record at natural address}

r := (r+d) mod n;                              {calculate next address of probe}

READ_DIRECT(file, buffer, r);              {get next record}

END;

IF VALID(file) THEN BEGIN                          {record has been found}

REMOVE(buffer);                          {set flag as abandoned}

UPDATE(file, buffer);                      {write back flagged record}

Algor5_6 := true                              {matching record found and deleted}

END

ELSE Algor5_6 := false;                           {record does not exist}

(α)                                                          (β)

Εικόνα 7.3 : Αλυσίδες συνωνύμων, (α) πριν τις προσθήκες, (β) μετά τις προσθήκες

Στη αρχή όλες οι θέσεις από τον αριθμό εγγραφής 0-8 έχουν καταληφθεί από εγγραφές που αντιστοιχούν στις φυσικές διευθύνσεις τους. Η επόμενη εγγραφή (κλειδί 9) που πρόκειται να προστεθεί κατακερματίζεται στη θέση 0 που είναι ήδη κατειλημμένη. Η γραμμική εξέταση τοποθετεί την εγγραφή αυτή στη θέση 2. Ένας δείκτης στην εγγραφή 0 συνδέει τη φυσική διεύθυνση με την εγγραφή που τοποθετήθηκε τελικά. Η επόμενη εγγραφή (κλειδί 20) πρέπει να τοποθετηθεί στη θέση 2 που είναι κατειλημμένη από το συνώνυμο του 18. Η γραμμική εξέταση καταλαμβάνει τη θέση 6 όπου τοποθετείται η νέα εγγραφή και η αλυσίδα αυξάνει.

Η 3η νέα εγγραφή (κλειδί 27) πρέπει να τοποθετηθεί στην 0 που είναι κατειλημμένη. Με τη γραμμική εξέταση καταλαμβάνεται η θέση 8, όπου τοποθετείται η εγγραφή. Έτσι η αλυσίδα, που ξεκινά από την 0, ακολουθείται μέχρι το τέλος της (αριθμός εγγραφής = 6) μετά συνδέεται η νέα εγγραφή στη θέση 8, που γίνεται το νέο τέλος της αλυσίδας. Το τέλος της αλυσίδας σημειώνεται θέτοντας ως τιμή του δείκτη το -1.

Σ’ αυτό το παράδειγμα η προσθήκη των 3 εγγραφών θα προκαλέσει την ένωση 2 αλυσίδων. Η μια αρχίζει από την εγγραφή 0 και η άλλη από την 2. Συνώνυμα και από τις 2 διευθύνσεις αναμειγνύονται κατά μήκος της αλυσίδας. Έτσι καθώς ο παράγοντας φόρτισης μεγαλώνει τόσο οι αλυσίδες μπλέκονται με αποτέλεσμα να απαιτείται περιοδικά αναδιοργάνωση του αρχείου. Αν και είναι δυνατή η προσθήκη και αναζήτηση εγγραφών με την χρήση ενός δείκτη προς τα εμπρός (forward pointer) συνήθως χρησιμοποιείται και 2ος δείκτης προς τα πίσω (backward pointer) και έτσι αντιμετωπίζουμε τις αλυσίδες ως διπλοδεσμικές λίστες. Ο λόγος της χρήσης διπλοδεσμικής λίστας είναι για να απλοποιηθούν διαδικασίες όπως αυτή της διαγραφής.

Στην συνέχεια παρουσιάζονται οι αλγόριθμοι που αναφέρονται στις βασικές διαδικασίες, χρησιμοποιώντας τη τεχνική διαχείρισης συνωνύμων χωρίς επανατοποθέτηση και γραμμική εξέταση. Οι συναρτήσεις FWD(buffer) και BKWD(buffer) επιτρέπουν πρόσβαση στον δείκτη προς τα εμπρός και στον δείκτη προς τα πίσω της εγγραφής που είναι αποθηκευμένη στον buffer. Η συνάρτηση GETNEXTSLOT(R ) επιστρέφει τον αριθμό εγγραφής, της άδειας θέσης στη γειτονιά της εγγραφής με τον αριθμό εγγραφής R.

• Προσθήκη

procedure Algor5_7(file, newbuffer, n);

k := fold(key(newbuffer));                              {fold the key if necessary}

r := k mod n;                                              {calculate the natural address}

READ_DIRECT(file, buffer, r);                      {get slot at natural address}

IF not VALID(file) THEN UPDATE(file, newbuffer) {write rec}

ELSE BEGIN

{find end of chain and add new record to end}

WHILE Fwd(buffer) <> null DO BEGIN              {get next rec}

r := fwd(buffer);

READ_DIRECT(file, buffer, r);

END;                                                      {last record of chain is now in buffer, r points to it}

j := GETNEWSLOT(r);                                         {returns record nbr of vacant slot}

fwd(buffer) := j;                                                  {link new slot into chain}

UPDATE(file, buffer);

bkwd(newbuffer) := r;                                          {set pointers for new record}

fwd(newbuffer) := null;

WRITE_DIRECT(file, newbuffer, j); {write new record}

END;

integer function GETNEWSLOT(r)                  {returns address of empty}

j := r;                                                          {initialize to given slot}

DO BEGIN

J := (j+1) mod n;                              {address of next slot with wraparound}

READ_DIRECT(file, localbuffer, j);     {test next slot}

END UNTIL not VALID(file);                          {empty slot has been found}

GETNEWSLOT := j;                                      {return the record number}

• Διαγραφή

Και πάλι η διαδικασία της διαγραφής δημιουργεί προβλήματα και περιπλέκει τα πράγματα. Υπάρχουν 2 προβλήματα ένα μικρό και ένα μεγάλο. Το μικρό είναι αυτό που κατά την διαγραφή εγγραφών θα πρέπει να διατηρείται η αλυσίδα και να μην διακόπτεται. Αυτό επιτυγχάνεται με τον προσδιορισμό της εγγραφής που προηγείται και έπεται της διαγραφόμενης και δίνοντας τιμές στους δείκτες τέτοιες που να δείχνουν σ’ αυτές. Αυτό απαιτεί κάποιες επιπλέον αναγνώσεις και εγγραφές αλλά ο αλγόριθμος είναι απλός.

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

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

Προφανώς δεν υπάρχει απλός τρόπος να διαγράφει μια εγγραφή όταν χρησιμοποιείται η μέθοδος διαχείρισης συνωνύμων χωρίς επανατοποθέτηση. Όπως και με την γραμμική εξέταση είναι προτιμότερο να διαγραφεί λογικά η εγγραφή σημειώνοντας την ως “εγκαταλελειμμένη” παρά ως κενή. Οι δείκτες θα συνεχίζουν να συνδέουν την εγγραφή μέσα στην αλυσίδα. Θα μπορέσει να αποθηκευθεί σ’ αυτή τη θέση μια νέα εγγραφή μόνο αν ο προς τα πίσω δείκτης έχει τιμή -1 ή βρεθεί κατά την διάρκεια της διαδικασίες εισαγωγής καθώς αναζητείται το τέλος της αλυσίδας. Όπως αναφέρθηκε ήδη, στις μεθόδους γραμμικής εξέτασης και επανακερματισμού, οι “εγκαταλελειμμένες” εγγραφές πρέπει να λαμβάνονται υπόψη στον υπολογισμό του παράγοντα φόρτισης. Το αρχείο απαιτεί κατά χρονικά διαστήματα αναδιοργάνωση. Η καλύτερη μέθοδος αναδιοργάνωσης του αρχείου είναι να αναγνωσθεί κάθε ενεργή εγγραφή του αρχείου με διάταξη διάφορη της σειράς που εμφανίζονται οι εγγραφές στο αρχείο, και διάφορη αυτής που προστέθηκαν στο αρχείο. Καθώς κάθε εγγραφή θα διαβάζεται θα προστίθεται σε νέο αρχείο με βάση τον αλγόριθμο 1_5. Τέλος το παλιό θα διαγραφεί.

• Ανάγνωση μιας εγγραφής με βάση την τιμή κάποιου συγκεκριμένου κλειδιού

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

Read a record with specific key value (Algorithm 5_8)

logical procedure Algor5_8(file, givenkey, n);

{returns true iff matching record is found}

k := fold(givenkey);

r := k mod n;                                  {hash to natural address}

READ_DIRECT(file, buffer, r);              {get slot at natural address}

r := fwd(buffer);                                  {get pointer for next record in chain }

READ_DIRECT(file, buffer, r); {read it}

END;                                          {either record is found or does not exist}

IF givenkey = key(buffer) THEN Algor5_8 := true

{record is found}

ELSE Algor5_8 := false; {search is unsuccessful}

• Ανάγνωση όλων των εγγραφών του αρχείο χωρίς μια συγκεκριμένη σειρά και

Ανάγνωση όλων των εγγραφών με βάση κάποιο συγκεκριμένο κλειδί

Τα αρχεία άμεσης προσπέλασης δεν προσφέρονται για αυτές τις διαδικασίες. Έτσι μπορούν να χρησιμοποιηθούν οι αλγόριθμοι 1_2. και 1_5. Μια και ο αλγόριθμος 1_5 είναι ανεπαρκής καλό είναι να αποφεύγεται όπου είναι δυνατόν.

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

Αυτή η αλλαγή μπορεί να υλοποιηθεί με μικρή τροποποίηση της GETNEXTSLOT του αλγόριθμος 5_7. Αντί να αρχίσουμε την σειριακή αναζήτηση από την εγγραφή που ακολουθεί μετά το τέλος της αλυσίδας αρχίζουμε από την 1η εγγραφή του block που περιέχει το τέλος της αλυσίδας. Στην παρακάτω έκδοση της GETNEXTSLOT η μεταβλητή b εκφράζει τον παράγοντα ομαδοποίησης.

integer function GETNEWSLOT(r)                      {returns address of empty}

                    {following calculation is done with integer divide}

j := b(r/b)-1;                                      {calculate the first record in block -1}

DO BEGIN

J := (j+1) mod n;                      {address of next slot with wraparound}

READ_DIRECT(file, localbuffer, j);                  {test next slot}

END UNTIL not VALID(file);                              {empty slot has been found}

GETNEWSLOT := j;                              {return the record number}

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

Μ’ αυτήν την μέθοδο:

(α)                                                              (β)

Εικόνα 7.4 : Αλυσίδες συνωνύμων με επανατοποθέτηση, (α) πριν τις προσθήκες, (β) μετά τις προσθήκες

Όπως και προηγουμένως στον πίνακα (α) φαίνεται η αρχική κατάσταση. Η επόμενη εγγραφή που προστίθεται (κλειδί 9) είναι εκείνη που η ΣΚ επιστρέφει ως αριθμό εγγραφής τον 0 που είναι όμως κατειλημμένος με εγγραφή που βρίσκεται στη φυσική της διεύθυνση. Με γραμμική εξέταση εντοπίζεται η θέση 2 που είναι κενή και εκεί τοποθετείται η νέα εγγραφή.

Η ΣΚ επιστρέφει τον αριθμό εγγραφής 2 για να αποθηκευθεί η επόμενη εγγραφή (κλειδί 20), η θέση όμως αυτή είναι κατειλημμένη από το συνώνυμό του 18. Επειδή αυτή η εγγραφή δεν βρίσκεται στη φυσική της διεύθυνση μετακινείται. Η εξέταση για άδεια θέση εντοπίζει τη θέση 6 και η εγγραφή που ήταν αποθηκευμένη στην 2 μετακινείται στην 6, και η αλυσίδα συνώνυμων με αρχή στην 0 ενημερώνεται. Τελικά η εγγραφή που η ΣΚ έδειξε ότι πρέπει να τοποθετηθεί στην 2 τελικώς τοποθετείται σ’ αυτή τη θέση που είναι η φυσική της διεύθυνση.

Η 3η νέα εγγραφή (κλειδί 27) πρέπει να τοποθετηθεί στη θέση 0 σύμφωνα με την τιμή που επιστρέφει η ΣΚ, η οποία είναι όμως κατειλημμένη από εγγραφή για την οποία είναι φυσική διεύθυνση. Η αλυσίδα ακολουθείται μέχρι το τέλος της, που είναι η 6, από όπου η εξέταση εντοπίζει την θέση 8 που είναι κενή. Σ’ αυτή τη θέση τοποθετείται η νεοεισερχόμενη εγγραφή και συνδέεται με το προηγούμενο τέλος της αλυσίδας. Αν συγκρίνουμε τον τελευταίο πίνακα με τον αντίστοιχο της προηγούμενης μεθόδου βλέπουμε ότι η εγγραφή 2 (κλειδί 20) δεν είναι πλέον μέρος της αλυσίδας, που αποτελείται από τα κλειδιά 18, 9, 27.

• Προσθήκη

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

Η 2η μέθοδος είναι να χρησιμοποιηθεί η συνάρτηση Add για την εισαγωγή της εγγραφής στο αρχείο σαν να εισέρχεται για πρώτη φορά. Αυτός ο τρόπος απαιτεί την κλήση της Add αναδρομικά.

integer function ADD(file, newbuffer, n);

k := fold(key(newbuffer));                  {fold key and hash}

r := k mod n;

READ_DIRECT(file, buffer, r);                      {read from natural address}

IF not VALID(file) THEN BEGIN

        {write it ot its natural address}

UPDATE(file, newbuffer);

ADD:= r:                              {return the natural address}

END

END

ELSE BEGIN                  {natural address is occupied by synonym}

END;

• Διαγραφή

Κατά τη διαγραφή εγγραφής μπορούν να προκύψουν 2 προβλήματα. Το 1ο συμβαίνει όταν η προς διαγραφή εγγραφή είναι η αρχή της αλυσίδας συνωνύμων. Εξ ορισμού κάθε συνώνυμο βρίσκεται στη φυσική του διεύθυνση. Έτσι ένα άλλο συνώνυμο πρέπει να αντικαταστήσει την διαγραμμένη εγγραφή αλλιώς η αλυσίδα δεν θα έχει αρχή και άρα θα είναι αδύνατος ο εντοπισμός της. Το 2ο πρόβλημα είναι να “μπαλώσουμε” την αλυσίδα των συνώνυμων έτσι ώστε να παραμείνει συνεχής όταν η εγγραφή που διαγράφεται είναι η αρχή της αλυσίδας ή όχι. Σημειώνεται η χρήση “διπλού buffer” έτσι ώστε να είναι διαθέσιμες και η προηγούμενη και η τρέχουσα εγγραφή.

logical function Algor5_10(file, givenkey, n);

{returns true iff matching record is found and deleted}

k := fold(givenkey);                                      {hash the given key}

r := k mod n;

READ_DIRECT(file, buffer1, r);                      {read record at natural address}

{search until key matches or end of chain found}

buffer2 := buffer1;                              {save previous record}

r := fwd(buffer1);                              {address of next link in chain}

READ_DIRECT(file, buffer1, r);         {read next record}

END;

END;

ALGOR5_10 := true;                          {record found and deleted}

END

ELSE IF VALID(file) and key(buffer1) = givenkey THEN BEGIN

{found record now patch up chain}

IF bkwd(buffer1) ? null THEN BEGIN

{fix pointer in previous record which is still in buffer2}

fwd(buffer2) := fwd(buffer1);

WRITE_DIRECT(file, buffer2, bkwd(buffer1));

END;

IF fwd(buffer1) <>null THEN BEGIN

{fix pointer in next record}

READ_DIRECT(file, buffer2, fwd(buffer1));

bwd(buffer2) := bkwd(buffer1);

WRITE_DIRECT(file, buffer2, fwd(buffer1));

END;

buffer1 := null                                              {put null record into buffer}

WRITE_DIRECT(file, buffer1, r);                  {write out empty record}

ALGOR5_10 := true;                                  {record not found}

END

ELSE ALGOR5_10 := false;

• Ανάγνωση όλων των εγγραφών με βάση κάποιο συγκεκριμένο κλειδί και

Ανάγνωση όλων των εγγραφών του αρχείο χωρίς μια συγκεκριμένη σειρά

Και πάλι αυτές οι διαδικασίες αντιμετωπίζονται με τους αλγ. 1_2 και 1_5

Read all records in any order, and read all records in key order

As algorithms 1_2 and 1_5.

• Ανάγνωση μιας εγγραφής με βάση την τιμή κάποιου συγκεκριμένου κλειδιού

Αυτός ο αλγόριθμος αποτελεί το αποκορύφωμα της μελέτης των αρχείων άμεσης προσπέλασης. Επιτρέπει τον εντοπισμό οποιασδήποτε εγγραφής γρήγορα και αποτελεσματικά. Όλα τα πλεονεκτήματα αυτής της δομής αρχείου πραγματοποιούνται μ’ αυτό τον αλγόριθμο. Βέβαια η χρήση αυτού του αλγόριθμου επιτρέπεται μόνο αν το αρχείο έχει δομηθεί με βάση τους αλγόριθμους 5_9 και 5_10.

Read a record with specific key value (Algorithm 5_11)

logical function Algor5_11(file, buffer, givenkey, n);

{returns true iff matching record is found}

k := fold(givenkey); {hash the given key}

r := k mod n;

READ_DIRECT(file, buffer, r); {read record at natural address}

WHILE VALID(file) and key(buffer)<> givenkey and fwd(buffer)<> null DO BEGIN

{search until key matches or end of chain found}

r := fwd(buffer); {address of next link in chain }

READ_DIRECT(file, buffer, r); {read next record}

END;

IF VALID(file) and givenkey = key(buffer) THEN Algor5_11 := true

{record found}

ELSE Algor5_11 := false; {record not found}

Περίληψη

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

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

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

Η μέθοδος της ανοικτής διεύθυνσης με γραμμική εξέταση έχει το πλεονέκτημα ότι είναι απλή και εύκολη στον προγραμματισμό. Γι’ αυτούς τους λόγους συνήθως χρησιμοποιείται. Όμως για υψηλούς παράγοντες φόρτισης μπορούν να προκύψουν μεγάλες αναζητήσεις. Επιπλέον υπάρχει πρόβλημα με την διαγραφή εγγραφών. Μια λύση για το πρόβλημα της διαγραφής εγγραφών είναι να σημειωθούν ως “εγκαταλελειμμένες”. Σε τακτά χρονικά διαστήματα καθώς οι εγγραφές προστίθενται και διαγράφονται, αυτές οι εγγραφές που είναι εγκαταλελειμμένες αλλά όχι κενές δημιουργούν ένα μεγάλο ποσοστό συγκέντρωσης. Γι’ αυτό απαιτείται αναδιοργάνωση του αρχείου. Έτσι η φαινομενική απλότητα της γραμμικής εξέτασης αντισταθμίζεται τελικά από την ανάγκη για διαχείριση και αναδιοργάνωση του αρχείου στις περισσότερες εφαρμογές.

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

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

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

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

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

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

Οι αλγόριθμοι που παρουσιάσθηκαν σ’ αυτό το κεφάλαιο δεν συνοδεύονται κι από ελέγχους όταν το αρχείο είναι σχεδόν γεμάτο. Οι περισσότεροι από τους “Add” αλγόριθμους θα ανακυκλώνονται έπ’ άπειρο αν επιχειρήσουμε να προσθέσουμε εγγραφές πέρα από την χωρητικότητα του αρχείου. Εφόσον οι αλγόριθμοι τροποποιηθούν για να λαμβάνουν υπόψη και αυτή την περίπτωση, η καλύτερη στρατηγική για τις διαδικασίες που πραγματοποιούν προσθήκη και διαγραφή εγγραφών να κρατούν στατιστική του πλήθους των ενεργών εγγραφών. Για την αποθήκευση αυτής της πληροφορίας μπορεί να χρησιμοποιηθεί η επικεφαλίδα του αρχείου.

Δυο όρια πρέπει να τεθούν στον παράγοντα φόρτισης. Όταν γίνεται προσθήκη εγγραφής που θα προκαλέσει αύξηση του παράγοντα φόρτισης πάνω από το πρώτο όριο, τότε θα πρέπει να στέλνεται προειδοποιητικό μήνυμα. Προσπάθειες προσθήκης εγγραφής που θα προκαλέσουν αύξηση του παράγοντα φόρτισης πάνω από το δεύτερο όριο θα πρέπει να προκαλούν κατάσταση λάθους. Π.χ. τα όρια μπορεί να είναι 85% και 95%. Προσθήκες που θα προκαλέσουν υπέρβαση του 85% θα στέλνουν προειδοποιητικό μήνυμα, ενώ προσθήκες που θα προκαλέσουν υπέρβαση του 95% θα πρέπει να μην γίνονται δεκτές.