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

KEY(i-1) £ KEY(i) £ KEY(i+1)

H παραπάνω σχέση προφανώς επιδρά τόσο κατά τη δημιουργία του αρχείου όσο και κατά τη διατήρηση του. Τα ταξινομημένα αρχεία διακρίνονται σε ταξινομημένα σειριακά αρχεία (ordered sequential files) και σε ταξινομημένα σχετικά αρχεία (ordered relatives files). Αν και μοιάζουν παρ’ όλα αυτά τα πρώτα είναι καταλληλότερα για ταινία ενώ τα δεύτερα για δίσκο.

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

Τα ταξινομημένα σχετικά αρχεία είναι όπως τα σχετικά με τις παρακάτω διαφορές

είναι ταξινομημένα

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

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

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

Το μεγαλύτερο πλεονέκτημα είναι η χρήση της μεθόδου της δυαδικής αναζήτησης (binary search BS) που είναι αρκετά αποτελεσματική μέθοδος για τον εντοπισμό εγγραφής για δοσμένο εσωτερικό κλειδί. Βέβαια δεν μπορεί να χρησιμοποιηθεί η μέθοδος BS για ταινία αφού η πράξη READ-DIRECT δεν είναι διαθέσιμη για ταινία.

Για τα ταξινομημένα σειριακά αρχεία είναι αυτές των σειριακών αρχείων.

Για τα ταξινομημένα σχετικά αρχεία είναι:

OPEN

READ_NEXT

READ_DIRECT

APPEND

CLOSE

EOF

VALID

Η πράξη APPEND χρησιμοποιείται για την εγγραφή νέων εγγραφών καθ’ όσον δεν υπάρχουν άδειες σχισμές για τη προσθήκη εγγραφών με την WRITE_DIRECT που είναι ενδεδειγμένη. Η APPEND χρησιμοποιείται κατά τη δημιουργία του αρχείου.

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

OPEN, READ_NEXT, WRITE_NEXT, CLOSE, EOF, VALID

• Αναδιοργάνωση

Η αναδιοργάνωση του αρχείου επιτυγχάνεται με την συγχώνευση (merge) του αρχικού αρχείου (original file) με το αρχείο μεταβολών (change file) σε ένα νέο αρχείο. Μετά τη δημιουργία του νέου αρχείου το αρχικό και το αρχείο μεταβολών διαγράφονται από το δίσκο. Το αρχείο μεταβολών πρέπει να περιλαμβάνει εγγραφές με την ίδια δομή με το αρχικό αρχείο εκτός από ένα επιπλέον πεδίο που δηλώνει το είδος της αλλαγής που θα γίνει. Το πεδίο αυτό δηλώνει αν η συγκεκριμένη εγγραφή του αρχείου μεταβολών θα προστεθεί ως νέα εγγραφή ή θα διαγραφεί η εγγραφή. Το αρχείο μεταβολών είναι και αυτό ταξινομημένο με βάση το κλειδί που είναι ταξινομημένο και το αρχικό αρχείο. Τόσο το αρχικό όσο και το αρχείο μεταβολών διαβάζονται σειριακά και το νέο αρχείο επίσης δημιουργείται σειριακά.

Reogranization (Algorithm 3_1)

{initialize by opening all files and reading first records}

OPEN(oldfile);

OPEN(newfile);

OPEN(changefile);

READ_NEXT(oldfile, oldbuf);

READ_NEXT(changefile, chgbuf);

WHILE not EOF(oldfile) or not EOF(changefile) DO BEGIN

{loop until there are no more records to process}

IF not EOF(oldfile) and not EOF(changefile)THEN

{both files have more record to process}

IF Key(oldbuff) = Key(chgbuf) THEN BEGIN

IF Flag(chgbuff) = «add» THEN BEGIN

APPEND(newfile, chgbuf);

APPEND(newfile, oldbuf);

{puts both into new file. no action required for the delete case}

END;

READ_NEXT(oldfile, oldbuf);

READ_NEXT(chgfile, chgbuf);

{refill buffers}

END

ELSE IF Key(oldbuf) < Key(chgbuf) THEN BEGIN

APPEND(newfile, oldbuf); {copy old record}

READ_NEXT(oldfile, oldbuf);

END

ELSE IF Key(oldbuf) > key(chgbuf) THEN BEGIN

{add new record}

IF Flag(chgbuf) = «add» THEN APPEND(newfile, chgbuf)

ELSE {error trying to delete nonexistent record}

READ_NEXT(changefile, chgbuf);

{refill buffer}

END;

ELSE IF EOF(changefile) THEN BEGIN

{copy from oldfile to newfile}

APPEND(newfile, oldbuf);

READ_NEXT(oldfile, oldbuf);

END

ELSE IF EOF(oldfile) THEN

{copy from changefile to newfile}

IF Flag(chgbuf) = «add» THEN APPEND(newfile, chgbuf)

ELSE {error trying to delete nonexistent record}

READ_NEXT(changefile, chgbuf);

END;

CLOSE(oldfile);

CLOSE(newfile);

CLOSE(changefile);

Ο παραπάνω αλγόριθμος μπορεί να εφαρμοσθεί τόσο για ταξινομημένα σειριακά αρχεία όσο και για ταξινομημένα σχετικά αρχεία και μπορεί να αντικατασταθεί η πράξη APPEND με την πράξη WRITE_NEXT. Ο παραπάνω αλγόριθμος δημιουργεί το νέο αρχείο συγκρίνοντας κάθε φορά τις επόμενες εγγραφές από το αρχικό αρχείο και το αρχείο μεταβολών. Εκείνη η εγγραφή με τη μικρότερη τιμή κλειδιού προστίθεται στο νέο αρχείο. Αν και τα κλειδιά των 2 εγγραφών έχουν την ίδια τιμή και η τιμή του πεδίου flag είναι ADD τότε προστίθεται η εγγραφή στο νέο αρχείο. Αν είναι DELETE τότε δεν προστίθεται εγγραφή στο νέο αρχείο.

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

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

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

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

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

Read all records in any order (as Algorithm 1_2)

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

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

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

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

{returns true iff record found. n is number of records in file}

lo : = 0; {pointer to the lowest-numbered record of interest}

hi := n-1; {pointer to the highest numbered record of interest}

found := false;

WHILE not found and lo £ hi DO BEGIN

{search until match found or no records of interest exist}

rec := (lo + hi)/2; {find the midpoint of the range}

READ_DIRECT(file, buffer, rec);

{compare given key with buffer}

IF givenkey = KEY(buffer) THEN {a match has been found}

found := true

ELSE IF givenkey > key(buffer) THEN

lo := rec+1 {all records of interest > rec}

ELSE IF givenkey < key(buffer) THEN

hi := rec-1; {all records of interest < rec}

END;

BINSRCH := found;

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

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

Περίληψη

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

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

Ο αλγόριθμος BS χρησιμοποιείται για τον εντοπισμό μιας εγγραφής με βάση το κλειδί οργάνωσης του αρχείου. Ο χρόνος που χρειάζεται για τον εντοπισμό της εγγραφής είναι της τάξης [log(N)] σε αντίθεση με (Ν) τάξη όπως συμβαίνει με τη σειριακή αναζήτηση.