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

Εικόνα 8.1: Κατακερματισμός σε αρχείο άμεσης προσπέλασης

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

Θα ήταν πιο συμφέρον να είχαμε μια δυναμική δομή αρχείου (dynamic file structure) η οποία θα αυξάνεται και συστέλλεται αυτόματα ανάλογα με το πλήθος των εγγραφών. Πιο συγκεκριμένα, μια δυναμική δομή αρχείου στην ιδανική περίπτωση θα έπρεπε να έχει 3 ιδιότητες.

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

• Το αρχείο να μπορεί να συστέλλεται αυτόματα έτσι ώστε η πιθανότητα του παράγοντα φόρτισης να πέσει κάτω από 50% να είναι αμελητέα. Όπως με την αύξηση έτσι και με την συστολή να μην απαιτείται αναδιοργάνωση του αρχείου ή επανατοποθέτηση σημαντικού αριθμού εγγραφών.

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

Η τελευταία ιδιότητα είναι η μόνη που διαθέτουν τα αρχεία άμεσης προσπέλασης.

Ο Επεκτατός κατακερματισμός (extendible hashing) είναι μια μέθοδος οργάνωσης αρχείου που διαθέτει τις παραπάνω 3 ιδιότητες. Αντί να χρησιμοποιείται ένας μετασχηματισμός του κλειδιού εφαρμόζονται 3 μετασχηματισμοί για να μετατραπεί το κλειδί σε δείκτη αρχείου.

Εικόνα 8.2 : Μετασχηματισμοί κλειδιού στα επεκτατά αρχεία

Ο πρώτος μετασχηματισμός είναι μια ΣΚ που απεικονίζει με τυχαίο τρόπο ένα διάστημα κλειδιών σε ένα σταθερό διάστημα συναρτήσεων. Μερικά πρώτα ψηφία εξάγονται και χρησιμοποιούνται ως είσοδος σε κατάλογο. Ο κατάλογος (directory) περιλαμβάνει δείκτες προς το αρχείο. Οι δείκτες δεν δείχνουν σε εγγραφές αλλά σε ομάδες εγγραφών που ονομάζονται buckets. Ένα bucket είναι μια μεγάλη ομάδα εγγραφών που διαβάζεται με μια μόνο φυσική ανάγνωση. Η μέθοδος τοποθέτησης εγγραφών μέσα σε ένα bucket δεν είναι σημαντική αφού δεν απαιτούνται επιπλέον φυσικές Ι/Ο λειτουργίες. Τα buckets μπορούν να προστίθενται και να διαγράφονται από το αρχείο οποιαδήποτε στιγμή.

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

• Ομοιόμορφη και τυχαία κατανομή των κλειδιών σ’ όλη την έκταση του αρχείου.

• Μικρές διακυμάνσεις του κλειδιού να οδηγούν σε μεγάλες διακυμάνσεις στις τιμές της συνάρτησης.

• Τα συνώνυμα να συμβαίνουν τόσο όσο η τυχαία πιθανότητα το επιτρέπει.

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

Οι ΣΚ που παρουσιάσθηκαν σε προηγούμενο κεφάλαιο εφαρμόζονται και εδώ. Ιδιαίτερα η απαίτηση να είναι πρώτος αριθμός ο χώρος διευθύνσεων της ΣΚ πρέπει να τηρείται. Μια και η ΣΚ δεν αντιστοιχεί κατευθείαν σε αριθμούς εγγραφών η επιλογή του διαστήματος της ΣΚ είναι κατά κάποιο τρόπο τυχαία και δεν συνδέεται με το πλήθος των εγγραφών του αρχείου. Γι’ αυτό είναι σωστότερο να επιλέγεται ο μεγαλύτερος πρώτος ακέραιος που είναι ο αμέσως μικρότερος από την δυαδική δύναμη. Π.χ. ο μεγαλύτερος πρώτος μικρότερος του 2¹⁶ είναι ο 65521.

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

Εικόνα 8.3 : Επεκτατός κατακερματισμός

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

Εικόνα 8.4 : Κατάλογος τάξης d = 3 με 4 buckets

Οι μετασχηματισμοί που φαίνονται στο παραπάνω σχήμα χρησιμοποίησαν τα 3 πρώτα ψηφία της ΣΚ για να διαμοιραστεί ο χώρος διευθύνσεων της ΣΚ σε 8 ισοδύναμα τμήματα (2^d = 2³ = 8). Αυτά τα 8 τμήματα αντιστοιχούν σε 2 δείκτες του καταλόγου

Π.χ. ας υποθέσουμε ότι H(key) = 0010100101100101 σε δυαδική μορφή. Τα 3 πρώτα ψηφία, 011, έχουν τιμή 3. Χρησιμοποιώντας τον 3 ως δείκτη του καταλόγου, οδηγούμαστε στο bucket C.

Η πλήρης ακολουθία για την αναζήτηση μιας εγγραφής στον επεκτατό κατακερματισμό γίνεται σε 5 βήματα.

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

Το αποτέλεσμα της διάσπασης φαίνεται στην παραπάνω εικόνα. Ας σημειωθεί ότι πριν την διάσπαση όλες οι εγγραφές για τις οποίες ίσχυε H(key) = 1 βρίσκονταν στο bucket D. Μετά την διάσπαση του D οι εγγραφές που ο μετασχηματισμός του κλειδιού αρχίζει από 10 αποθηκεύονται στο D και στο Ε αυτές για τις οποίες ισχύει H(key) = 11. Κάθε bucket συνοδεύεται από μια παράμετρο d’ που δηλώνει το πλήθος των ψηφίων της H’(key) που είναι κοινός για τα κλειδιά όλων των εγγραφών του bucket. Η τιμή αυτής της παραμέτρου πρέπει να είναι ίση ή μικρότερη από το πλήθος των ψηφίων, d. Άρα το πλήθος των δεικτών που αναφέρονται σε συγκεκριμένο bucket είναι πάντα 2^(d-d’).

Η διάσπαση των buckets μπορεί να συνεχισθεί όσο το αρχείο αυξάνει και όσο τουλάχιστον 2 δείκτες αναφέρονται στο bucket που πρόκειται να διασπασθεί. Αν ένα bucket στο οποίο αναφέρεται ένας μόνο δείκτης (d = d’) υπερχειλίσει, ο κατάλογος πρέπει να επεκταθεί πριν το bucket διασπαστεί. Π.χ. αν το bucket C, στην παραπάνω εικόνα, υπερχειλίσει, ένα νέο bucket F, αποδίδεται στο αρχείο. Ωστόσο δεν υπάρχει χώρος στον κατάλογο για να αντιστοιχίσει δείκτες στα bucket C και F. Έτσι ο κατάλογος πρέπει να μεγαλώσει για να επιτραπεί η αποθήκευση νέων δεικτών.

Ο κατάλογος διπλασιάζει το πλήθος των στοιχείων του. Κάθε δείκτης του αρχικού καταλόγου διπλασιάζεται και καταλαμβάνει 2 διαδοχικές θέσεις στον νέο κατάλογο. Ο κατάλογος της παραπάνω εικόνας περιλαμβάνει τις παρακάτω τιμές δεικτών Α, Α, Β, C, D, D, E, E. Μετά τον διπλασιασμό θα περιλαμβάνει A, A, A, A, B, B, C, C, D, D, D, D, E, E, E, E.

Εικόνα 8.6 : Κατανομή των κλειδιών στα buckets μετά τον διπλασιασμό του καταλόγου και την διάσπαση του bucket C

Η διαδικασία μείωσης του αρχείου είναι αντίστροφη της αύξησης αυτού. Τα buckets θα συνδυαστούν αν ισχύουν 3 συνθήκες.

Ο μέσος όρος παράγοντα φόρτισης για τα 2 buckets δεν πρέπει να ξεπερνά το 50%, αλλιώς δεν θα υπάρχει χώρος για τα συνδυασμένα buckets για όλες τις εγγραφές.

Τα συνδυαζόμενα buckets πρέπει να έχουν την ίδια τιμή του d’.

Τα κλειδιά των εγγραφών και στα 2 buckets πρέπει να έχουν κοινά τα πρώτα (d’-1) ψηφία της H(key).

Στο παράδειγμά μας τα buckets D και Ε ικανοποιούν όλες τις συνθήκες. Ο κατάλογος πρέπει να μειωθεί όταν τα ζεύγη των δεικτών έχουν την ίδια τιμή, π.χ. ο κατάλογος με τιμές δεικτών Α, Α, Α, Α, Β, Β, C, C, D, D, D, D, E, E, F, F, θα μειωθεί και θα υποδιπλασιαθεί. Η τιμή κάθε ζεύγους δεικτών του παλιού καταλόγου χρησιμοποιείται ως τιμή του νέου καταλόγου και έτσι θα έχουμε A, A, B, C, D, D, E, F. Ομως αν ένας κατάλογος με τιμές δεικτών Α, Α, Α, Β, Β, Β, C, C, D, D, D, D, E, E, F, F δεν μπορεί να μειωθεί λόγω του ζεύγους (Α, Β) που οι τιμές δεν είναι ίσες. Επειδή είναι δυνατόν να μην υπάρχει διαθέσιμο bucket για να συνδυαστούν, όταν ο παράγοντας φόρτισης ενός bucket πέσει κάτω από 50%, γι’ αυτό δεν μπορούμε να εγγυηθούμε ότι ο παράγοντας φόρτισης ενός bucket ή του αρχείου δεν θα πέσει κάτω από 50%. Βέβαια, αν η ΣΚ μπορεί να κατακερματίσει τυχαία τα κλειδιά, τότε η πιθανότητα να πέσει κάτω από 50% ο παράγοντας φόρτισης είναι μηδαμινός. Όπως θα δειχθεί παρακάτω κανονικά είναι γύρω στο 69%.

Το μέσο πλήθος buckets και στοιχείων του καταλόγου μετά αρκετές προσθήκες και διαγραφές είναι:

πλήθος buckets =                             (1)

πλήθος στοιχείων καταλόγου =         (2)

όπου Ν = πλήθος εγγραφών αρχείου

Β = πλήθος εγγραφών που χωρούν στο bucket

Ο τύπος (2) αναφέρεται σε μέση τιμή. Ο τρέχον αριθμός στοιχείων οποιαδήποτε στιγμή είναι δύναμη του 2. Ο κατάλογος σχεδόν πάντα θα περιλαμβάνει περισσότερους δείκτες από το πλήθος των buckets μια και σε κάποια buckets θα αναφέρονται περισσότεροι του ενός δείκτες. Η μέση αναλογία δεικτών προς buckets είναι ή 1.44. Και επειδή ο μέσος όρος παράγοντα φόρτισης όπως προκύπτει από την (2) είναι 69%, ο μέσος όρος δεικτών θα είναι περίπου .

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

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

Υπάρχουν αρκετές ικανοποιητικές λύσεις, χωρίς σαφή προτίμηση μεταξύ τους.

Μια απλή δομή η σειριακή - χρονολογική οργάνωση με bit map είναι δυνατή. Για να εντοπισθεί η επιθυμητή εγγραφή ελέγχεται ακολουθιακά κάθε εγγραφή στο bucket και το κλειδί της συγκρίνεται με το δοθέν κλειδί μέχρι να ταυτισθούν οι τιμές ή να συναντήσουμε το τέλος του bucket. Μπορούν να χρησιμοποιηθούν και πιο έξυπνες τεχνικές με μείωση του χρόνου της CPU και με μικρή αύξηση της πολυπλοκότητας.

Ως ταξινομημένο σχετικό αρχείο θα μπορούσε να δομηθεί εσωτερικά το bucket και με τη χρήση της δυαδικής αναζήτησης να εντοπισθεί η αναζητούμενη εγγραφή. Το πρόβλημα προσθήκης και διαγραφής λύνεται με μετακίνηση ομάδων (blocks) εγγραφών τόσες όσες χρειάζονται για να δημιουργηθεί χώρος για νέα εγγραφή ή για να κλείσει το κενό από την διαγραφή εγγραφής. Συνεπώς η αναδιοργάνωση είναι συνεχής και μπορεί να γίνει εξολοκλήρου στην κύρια μνήμη. Συχνά χρησιμοποιείται η άμεση προσπέλαση που προκαλεί λιγότερες μετακινήσεις εγγραφών. Σε κάθε κλειδί εφαρμόζεται ξανά η ΣΚ χρησιμοποιώντας άλλον αλγόριθμο κατακερματισμού απ’ αυτόν που χρησιμοποιείται για τον εντοπισμό του bucket. Σ’ αυτή την περίπτωση τα συνώνυμα θα τα χειριστούμε με μια από τις μεθόδους που έχουν παρουσιασθεί.

Το επεκτατό αρχείο είναι μια ειδική κατηγορία μιας μεγάλης οικογένειας δομών που χρησιμοποιούν δενδρική αναζήτηση για τον εντοπισμό ενός επιθυμητού στοιχείου. Ποιο συγκεκριμένα, χρησιμοποιούν το radix tree ή trie. Όταν η radix είναι 2 τότε το radix δένδρο είναι το δυαδικό δένδρο.

Εικόνα 8.7 : Ο κατάλογος της εικόνας 8.6 ανακατασκευασμένος ως δυαδικό δένδρο

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

Εικόνα 8.8 : Κατάλογος δυαδικού δένδρου χρησιμοποιούμενο σε δυναμικό κατακερματισμό

Το τελευταίο δένδρο παρουσιάζει το πλεονέκτημα να είναι μικρότερο μια και αντιστοιχεί ένας τερματικός κόμβος για κάθε bucket. Δεν εξαναγκάζεται να είναι ισοζυγισμένο όπως το δένδρο με τον άμεσο επεκτατό κατακερματισμό. Όταν ο κατάλογος του επεκτατού κατακερματισμού αντικαθίσταται με ένα δένδρο όμοιο με το παραπάνω τότε η τεχνική λέγεται δυναμικός κατακερματισμός (dynamic hashing).

Το τελευταίο δένδρο είναι ελάχιστα ισοζυγισμένο. Αν χρησιμοποιηθεί κάποια τεχνική δυναμικού κατακερματισμού που θα περιλαμβάνει και έναν αλγόριθμο περιστροφής θα διατηρήσει το δένδρο ισοζυγισμένο. Παρ’ όλα αυτά δεν είναι αναγκαίο στις περισσότερες περιπτώσεις. Αν η ΣΚ είναι ικανή να τυχαιοποιήσει καλά τα κλειδιά, οι τιμές της H(key) θα κατανεμηθούν ομοιόμορφα στο διάστημα και το προκύπτον δένδρο θα είναι σχεδόν ισοζυγισμένο, με την μόνη εξαίρεση όταν το πλήθος των εγγραφών του αρχείου είναι μικρό και το μέγεθος του bucket μικρό. Έτσι το ενδεικτικό (sample) μέγεθος είναι πολύ μικρό για να είναι φανερή η ικανοποίηση της κατανομής. Αυτή η ίδια ομοιομορφία της κατανομής θα κρατήσει τα buckets στον ίδιο παράγοντα φόρτισης. Αυτό σημαίνει ότι όταν οι εγγραφές πρόκειται να προστεθούν στο αρχείο, όλα τα buckets θα τείνουν να υπερχειλίσουν την ίδια χρονική στιγμή. Έτσι ο παράγοντας φόρτισης θα κυμαίνεται περιοδικά μεταξύ άνω του 50% και κάτω του 100% καθώς το πλήθος των εγγραφών αυξάνεται.

Εκτός του δυναμικού κατακερματισμού υπάρχουν κι αρκετές άλλες μέθοδοι, όπως το expandable hashing και εικονικός κατακερματισμός (virtual hashing).

Αρκετοί παράγοντες σχεδίασης του επεκτατού κατακερματισμού θα πρέπει να αναφερθούν.

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

Οσο το διάστημα της ΣΚ είναι μεγάλο ένα κάτω όριο θα πρέπει να λαμβάνεται υπόψη, δηλαδή, θα πρέπει να υπάρχει ένας ικανός αριθμός ψηφίων στο διάστημα της ΣΚ για να δεικτοδοτεί τον κατάλογο στο μέγιστο μέγεθος του. Μ’ άλλα λόγια πρέπει να υπάρχουν το λιγότερο d ψηφία στην τιμή της ΣΚ για το μεγαλύτερο d που μπορεί να υπάρξει για το αρχείο. Π.χ. το διάστημα των 16 bits θα είναι κατάλληλο για ένα αρχείο 6 εκατομμυρίων εγγραφών με περιεκτικότητα ίση με 50. Μια και δεν υπάρχει άνω όριο είναι σοφό να επιλέγεται διάστημα που να είναι κάτι περισσότερο από ικανοποιητικό για το αρχείο.

Το σύνολο των βασικών πράξεων για το επεκτατό αρχείο είναι παρόμοιο μ’ αυτό που χρησιμοποιήθηκε και με τους άλλους τύπους αρχείων με την εξαίρεση ότι οι πράξεις της ανάγνωσης και της εγγραφής αναφέρονται σ’ όλο το bucket αντί για μια εγγραφή. Επιπλέον είναι αναγκαίο να διαθέτουμε πράξεις για την κατανομή νέων buckets που δεν χρειάζονται πλέον στο αρχείο. Υπάρχουν αρκετές μέθοδοι για την διαχείριση της κατανομής και της ανακατανομής (deallocation) των buckets μέσα στο αρχείο. Γι’ αυτόν τον τύπο οργάνωσης αρχείου θα εισάγουμε 2 νέες βασικές πράξεις για την διαχείριση της κατανομής και ανακατανομής των buckets.

Οι βασικές πράξεις για τα επεκτατά αρχεία είναι :

OPEN

READ_DIRECT : τοποθετεί τον δείκτη ανάγνωσης στο καθορισμένο bucket και επιστρέφει το bucket στον χρήστη

WRITE_DIRECT

UPDATE

CLOSE

VALID

ALLOCATE : κατανέμει ένα νέο bucket στο αρχείο από τον ελεύθερο χώρο του αρχείου. Ο αριθμός του bucket επιστρέφεται μέσω συνάρτησης.

DEALLOCATE : αφαιρεί ένα bucket από το αρχείο και επιστρέφει τον ελεύθερο χώρο.

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

• Integer function H(key) : η ΣΚ όπως έχει περιγραφεί. Το διάστημα της συνάρτησης κυμαίνεται από 0 έως Ν-1, όπου Ν πρώτος αριθμός ελάχιστα μικρότερος από κατάλληλη δύναμη του 2.

• Integer function EXTRACT(j, d) : Εξάγει τα πρώτα d ψηφία υψηλής τάξης από τον j και τα επιστρέφει ως ακέραιο.

• Function KEY(recordbuffer) : Επιστρέφει την τιμή του κλειδιού που αντιστοιχείται με την εγγραφή που είναι αποθηκευμένη στον buffer.

• Procedure GET(bucketbuffer, key, recordbuffer) : Αντιγράφει μια εγγραφή της οποίας η τιμή του κλειδιού είναι ίση με “key” από το bucket που είναι αποθηκευμένο στη μεταβλητή bucketbuffer στη μεταβλητή recordbuffer. Η τιμή της VALID γίνεται false αν δεν υπάρχει εγγραφή στο bucket που η τιμή του κλειδιού να ταιριάζει με τη τιμή της “key”.

• Procedure GET_NEXT(bucketbuffer, recordbuffer) : Αντιγράφει την επόμενη έγκαιρη εγγραφή από το bucketbuffer στον recordbuffer. Η πρώτη κλήση μετά το φόρτωμα του bucketbuffer επιστρέφει την πρώτη έγκαιρη εγγραφή. Η συνθήκη EOF καθίσταται true αν η GET_NEXT καλείται μετά την ανάγνωση της τελευταίας έγκυρης εγγραφής από το bucketbuffer.

• Procedure PUT(bucketbuffer, recordbuffer) : Αντιγράφει την εγγραφή από το recordbuffer στο bucket που βρίσκεται στο bucketbuffer. H VALID λαμβάνει την τιμή false αν δεν υπάρχει θέση για την εγγραφή στον buffer.

• Procedure DELETE(bucketbuffer, key, load) : Διαγράφει την εγγραφή από το bucket που είναι αποθηκευμένο στο bucketbuffer του οποίου το κλειδί ταυτίζεται με το “key”. Η μεταβλητή “Load καθίσταται ίση με τον παράγοντα φόρτισης του bucket μετά την πραγματοποίηση της διαγραφής. Η VALID γίνeται false αν δεν μπορεί να βρεθεί εγγραφή που να ταιριάζει η τιμή του κλειδιού με το “key”.

• Procedure PARAM(filename, bucket, dp, load) : Επιστρέφει την τοπική τάξη (local order) dp και τον παράγοντα φόρτισης δοσμένου bucket.

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

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

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

• Συμπληρωματικοί αλγόριθμοι

PRΟCEDURE EXPAND(directory, d)

Ο πρώτος συμπληρωματικός αλγόριθμος αυξάνει τον κατάλογο όταν χρειάζεται. Έχει 2 παραμέτρους, τον πίνακα που περιλαμβάνει τον κατάλογο και την τάξη του καταλόγου d. Ο τρέχων κατάλογος πρέπει να έχει 2^d στοιχεία και ο νέος κατάλογος θα έχει διπλάσιο αριθμό. Ο πίνακας- κατάλογος πρέπει να είναι αρκετά μεγάλος ώστε να περιέχει όλα τα στοιχεία μετά την αύξηση. Τόσο ο πίνακας όσο και η d είναι παράμετροι αναφοράς (by reference) και η τιμή του d αυξάνεται και έτσι δηλώνεται η νέα τάξη του καταλόγου. Ο αλγόριθμος αυξάνει τον κατάλογο αντί να αντιγράφει τους δείκτες σε νέο πίνακα.

procedure EXPAND(directory, d);

{doubles the size of the directory and increases the order by 1}

{original directory has 2d entries numbered 0 to 2d -1}

FOR i := (2^d -1) DOWNTO 0 DO BEGIN {dublicate each entry}

directory(2*i+1) := directrory(i);

directory(2*i) := directory(i);

END;

d := d+1;

Procedure CONTRACT

Ομοία η διαδικασία CONTRACT μειώνει το μέγεθος του καταλόγου στο μισό και μειώνει κατά 1 την τιμή του d. Λόγω της απαίτησης και οι 2 αριθμοί κάθε ζεύγους δεικτών να έχουν την ίδια τιμή πριν την μείωση του καταλόγου, είναι αναγκαίο να ελέγξουμε κάθε ζεύγος αν πληροί αυτή την απαίτηση. Αν κάποιο ζεύγος αποτύχει, η παράμετρος λάθους θα γίνει true και ο κατάλογος θα παραμείνει αμετάβλητος. Αν ο κατάλογος μειωθεί επιτυχώς, η παράμετρος λάθους θα γίνει false.

{halves the size of the directory and decrases the order by 1 iff each pair of pointers has the same value}

{first check pair values}

i := 0;

error := false;

WHILE i < 2d and not error DO BEGIN              {check each pair}

IF directory(i) <> directory(i+1) THEN error := true;

i := i+2;

END;

{now remove the odd entries and contract}

IF not error THEN BEGIN

d := d-1;

FOR i := 1 to (2d -1) DO directory(i) := directory(2*i);

Ακολουθούν οι διαδικασίες που αναφέρονται στην διάσπαση και συγκέντρωση των buckets.

Procedure SPLIT

Η SPLIT απαιτεί 3 παραμέτρους. Η oldbucket είναι δείκτης στο αρχικό bucket. H newbucket είναι δείκτης για το νέο bucket. Και οι 2 περνιούνται δι’ αναφοράς. Η τοπική τάξη του oldbucket περνιέται ως dp ( d prime). Η τιμή της αυξάνεται κατά 1 και επιστρέφεται μέσω της διαδικασίας.

procedure SPLIT(filename, oldbucket, newbucket, dp);

{gets new bucket and divides the records in oldbucket between the two buckets, increments dp by 1}

ALLOCATE(filename, newbucket); {first get a new bucket}

READ_DIRECT(filename, oldbucketbuf, oldbucket); {read oldbucket}

WHILE not EOF(oldbucketbuf) DO BEGIN

{loop once for each record in the oldbucket}

GET_NEXT(oldbucketbuf, recbuf);                          {get one record form bucket}

IF (EXTRACT(H(Key(recbuf)), (dp+1))) mod 2 = 1 THEN BEGIN

{for this record the next bit of H(key) after the first dp bits is a 1; this record must be moved to the new bucket}

DELETE(oldbucketbuf, key(recbuf));

{deletes current record in buffer of the old bucket}

PUT(newbucketbuf, recbuf);

{insert current record in buffer of the new bucket}

END;                                          {of testing one record}

END;                                          {all records have been moved to the buffer of the new bucket}

WRITE_DIRECT(filename, oldbucketbuf, oldbucket);

{write back the old bucket from its buffer}

WRITE_DIRECT(filename, newbucketbuf, newbucket);

{write out the new bucket from its buffer}

dp := dp+1; {increase the local order by 1}

Procedure JOIN

H διαδικασία JOIN συνενώνει εγγραφές δυο buckets σε έναν και διαγράφει το άλλο bucket από το αρχείο. Αν υπάρχουν πολλές εγγραφές για να χωρέσουν σε ένα buckets, η error γίνεται true και το αρχείο δεν αλλάζει. Αλλιώς η error γίνεται false και η d’ μειώνεται κατά 1.

procedure JOIN(bucket1, bucket2, dp, error);

{combines records from both buckets into bucket1 and deletes bucket2}

{first load the bucket buffers from the file}

READ_DIRECT(filename, bucketbuf1, bucket1);

READ_DIRECT(filename, bucketbuf2, bucket2);

error := false; {initialize error flag}

{now copy the records from bucket2 to bucket1}

WHILE not EOF(bucket2) and not error DO BEGIN

{loop once for each record moved}

GET_NEXT(bucketbuf2, recbuf);

IF not EOF(bucketbuf2) THEN BEGIN

PUT(bucketbuf1, recbuf);                  {move the record to bucket1);

IF not VALID(bucketbuf1) THEN error := true;

{overflow in bucket1}

END;

END;                      {all records copied}

IF not error THEN BEGIN                                  {put the file in order}

WRITE_DIRECT(filename, bucketbuf1, bucket1);

{write out the new bucket1 with all the records}

DEALLOCATE(filename, bucket2);                  {delete empty bucket}

dp := dp-1;                                  {decrement the local order}

END;

• Αλγόριθμοι για τις βασικές διαδικασίες

• Προσθήκη

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

procedure ADD(filename, directory, d, recbuf);

{recbuf holds the ne w record to be added}

h := H(key(recbuf));                  {hash the key of the new record}

index := EXCTRACT(h, d);              {get the high-order bits for the index}

bucket := directory(index)                  {find the bucket pointer}

READ_DIRECT(filename, bucketbuf, bucket);          {read the bucket}

PUT(bucketbuf, recbuf);                  {insert record into the bucket}

IF not VALID(bucketbuf) THEN BEGIN              {overflow must split bucket}

IF dp = d THEN EXPAND(directory, d);              {expand the directory}

{calculate the indexes for the first and last pointes to the current bucket}

first :=(2d-dp )*EXTRACT(h, dp);

last := first+2(d-dp) -1;

{now split the bucket}

SPLIT(filename, bucket, newbucket, dp);

{insert pointer(s) in the directory for the new bucket}

{calculate the index of the first pointer to be changed}

first := first+(first-last+1)/2;

FOR index := first TO last DO directory(index) := newbucket;

{all expansion is done, call ADD recursively to insert record}

ADD(filename, recbuf); {guaranteed to work the second time}

END

ELSE {write the updated bucket back to the file}

WRITE_DIRECT(filename, bucketbuf, bucket);

• Διαγραφή

Η διαδικασία delete είναι όμοια με την Add. Εντούτις η διαγραφή μπορεί να προκαλέσει υποχείλιση (underflow) του bucket και τότε θα πρέπει να γίνει προσπάθεια συνένωσης των buckets. Η προσπάθεια δεν είναι πάντα επιτυχής λόγω περιορισμών που αφορούν συνένωση buckets. Ο αλγόριθμος 6_2 εκτελεί την διαδικασία της διαγραφής και αποτελείται από 2 διαδικασίες την βασική DELETE η οποία καλεί μια δεύτερη την TEST, η οποία με τη σειρά της προσδιορίζει αν ένα δοσμένο ζεύγος buckets μπορεί να συνδυασθεί.

procedure DELETE(filename, key);

{key is key of record to be deleted}

h := H(key);                      {hash the key for future use}

index := EXTRACT(h, d);              {calculate index}

bucket := directory(index);              {get bucket pointer from directory}

READ_DIRECT(filename, bucketbuf, bucket);              {read the bucket}

DELETE(bucketbuf, key, load);                          {delete the record}

IF VALID(bucketbuf) THEN BEGIN                  {record deleted OK, continue}

{write the bucket back to the file}

WRITE_DIRECT(filename, bucketbuf, bucket);

IF load < 0.5 THEN BEGIN {bucket underflow}

{three conditions are necessary for two buckets to be combined

1. their average load factor £ 50 %

2. their local orders are the same

3. all keys in both buckets share a common value of the first (dp-1) bits of H(key)}

{assertion: only the two buckets whose pointers are adjacent in the directory to those of the current bucket can meet the third condition}

{calculate the indexes for the first and last pointers in the directory for the current bucket}

first := 2(^d-dp)*EXTRACT(h, dp);

last := first+2(^d-dp)-1;

{check the previous bucket}

p := first-1;

IF p > 0 THEN TEST(filename, p, ok);

IF not ok and last = 2(^d-1) THEN BEGIN

{check next bucket}

p := last;

TEST(filename, p, ok);

p := p+1; {set this index to the other bucket}

END;

IF ok THEN BEGIN {join the qualified buckets}

JOIN(bucket, directory(p), dp, error);

{reflect the change in the directory pointers}

IF not error THEN directory(p) := bucket;

{attempt to contract the directory}

CONTRACT(directroy, d, error);

END;

END;

END;

procedure TEST(filename, p, ok);

{tests the bucket whose pointer is at directory(p) with the bucket whose pointer is at directrory(p+1) to see if the three necessary conditions are all met for combining the buckets. ok is set to true if all conditions are met.

othewise it is false}

{get the parameters of both buckets}

PARAM(filename, directory(p), dp1, load1);

PARAM(filename, directory(p+1), dp2, load2);

ok := true; {until proven false}

{first condition}

ELSE IF dp1 <>dp2 THEN ok := false                  {second condition}

ELSE IF EXTRACT(p, dp1) ? EXTRACT((p+1), dp2) THEN ok := false;

{third condition}

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

Ο αλγόριθμος 6_3 για την εξαντλητική ανάγνωση αρχείου με οποιαδήποτε διάταξη χρησιμοποιεί τον κατάλογο για να προσδιορίσει το τρέχον σύνολο buckets. Όλος ο κατάλογος διαβάζεται ακολουθιακά και κάθε νέο bucket εισάγεται στο buffer. Μετά διαβάζεται κάθε εγγραφή του bucket.

procedure READ_ALL(filename);

{reads and processes all records in the file}

oldbucket := null;

FOR i := 0 to 2d-1 DO BEGIN              {read each directory entry}

bucket := directrory(i)                  {get the next bucket pointer}

IF bucket <> oldbucket THEN BEGIN

{this is a new bucket, process it}

READ_DIRECT(filename, bucketbuf, bucket);

WHILE not EOF(bucketbuf) DO BEGIN

{process each record in the bucket}

GET_NEXT(bucketbuf, recordbuf);

PROCESS_RECORD(recbuf);

END;

END;

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

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

procedure READ_BY_KEY(filename, key, recbuf);

{this procedure returns the desired record in recbuf. if a record whose key value matches «key» cannot be found, a null value is placed in recbuf}

h := H(key); {hash the key}

bucket := directrory(EXTRACT(h, d); {loop up the bucket number}

READ_DIRECT(filename, bucketbuf, bucket); {read the bucket}

GET(bucketbuf, key, recbuf); {copy the record to the buffer}

IF not VALID(bucketbuf) THEN recbuf := null; {record not found}

• Ενημέρωση εγγραφής

Η τελευταία διαδικασία που αναφέρεται στην ενημέρωση δεν απαιτεί κάποιο νέο αλγόριθμο. Όταν η εγγραφή διαβαστεί με την βοήθεια του αλγόριθμου. 6_3 ή 6_4 η τροποποιημένη εγγραφή ξαναγράφεται στη μεταβλητή bucketbuffer και ενημερώνεται η bucket. Βέβαια στην ενημέρωση δεν συμπεριλαμβάνεται το κλειδί. Αν χρειαστεί να αλλάξει το κλειδί τότε πρώτα διαγράφεται και μετά εισάγεται η εγγραφή στο αρχείο με την νέα τιμή κλειδιού.

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

Το επεκτατό αρχείο είναι μια δυναμική δομή αρχείου που επιτρέπει την αυτόματη αύξηση και μείωση διατηρώντας ένα μέσο παράγοντα φόρτισης γύρω στα 69%. Οι εγγραφές αποθηκεύονται σε μεγάλες ομάδες εγγραφών που λέγονται buckets. Μια εγγραφή μπορεί να εντοπισθεί αν δοθεί η τιμή του πρωτεύοντος κλειδιού η οποία προέρχεται από την εφαρμογή της ΣΚ. Τα υψηλής τάξης bits του αποτελέσματος χρησιμοποιούνται ως δείκτης σε κατάλογο πίνακα όπου ένας δείκτης του δεικτοδοτεί το bucket που περιέχει την επιθυμητή εγγραφή. Η εσωτερική δομή του bucket δεν έχει καμία σχέση με την βασική δομή του αρχείου και οποιαδήποτε κατάλληλη μέθοδος μπορεί να χρησιμοποιηθεί. Το αρχείο αυξάνεται αυτόματα όταν είναι αναγκαίο να δεχθεί νέες εγγραφές. Ομοίως μειώνεται αυτόματα για να διατηρηθεί η υψηλή τιμή του παράγοντα φόρτισης. Τα buckets διασπώνται όταν το αρχείο αυξάνει και συνενώνονται (combined) όταν το αρχείο μειώνεται. Οι αυξήσεις και μειώσεις γίνονται με κατανομή και ανακατανομή των buckets από τον ελεύθερο χώρο του αρχείου. Επίσης ο κατάλογος αυξάνεται (expand) και μειώνεται (contract) σύμφωνα με το μέγεθος του αρχείου. Σχεδόν για όλα τα μεγέθη αρχείων συνήθως ο κατάλογος χωράει στην RAM και δίνεται η δυνατότητα να διαβάζουμε εγγραφές με μια προσπέλαση στον δίσκο.

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