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

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

1. Το Binary search απαιτεί αρκετές αναζητήσεις (seeks). Η αναζήτηση ενός κλειδιού στον δίσκο σημαίνει αναζητήσεις (seeking) σε διαφορετικά tracks του δίσκου. Καθόσον κάθε προσπέλαση σε κάποιο σημείο του δίσκου είναι αρκετά δαπανηρή , αναζήτηση που θα περιλαμβάνει 3 ή 4 αναζητήσεις πριν εντοπισθεί το κλειδί δεν είναι επιθυμητή. Είναι γνωστό ότι για αναζήτηση ενός κλειδιού σ’ έναν κατάλογο με 1000 εγγραφές χρειάζονται κατά μέσο όρο 9.5 προσπελάσεις στον δίσκο χρησιμοποιώντας binary search. Άρα χρειάζεται να βρεθεί άλλος τρόπος που θα πετυχαίνουμε το αποτέλεσμα που θέλουμε με λιγότερες προσπελάσεις.

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

Δενδρικός κατάλογος (tree index) είναι ένας κατάλογος με συγκεκριμένη ιεραρχία επιπέδων καταλόγων. Η ρίζα ή το πρώτο επίπεδο του καταλόγου δεικτοδοτεί προς το δεύτερο επίπεδο του καταλόγου κτλ. Το τελευταίο επίπεδο, τα φύλλα, περιέχουν δείκτες προς το αρχείο δεδομένων. Οι δενδρικοί κατάλογοι διακρίνονται σε δυο είδη : ετερογενή δένδρα (heterogeneous trees) και ομογενή δένδρα (homogeneous trees). Ετερογενή είναι τα δένδρα που περιέχουν ένα μόνο είδος δεικτών αλλά οι δείκτες αυτοί είναι διαφορετικοί για τους κόμβους των ενδιαμέσων επιπέδων απ’ ότι για το τελευταίο επίπεδο. Σε αντίθεση στα ομογενή δένδρα υπάρχουν δυο είδη δεικτών, δείκτες δεδομένων (data pointers) και δενδρικοί δείκτες (tree pointers). Στα ενδιάμεσα επίπεδα και οι δυο τύποι είναι ενεργοί, ενώ στο τελευταίο επίπεδο είναι ενεργοί μόνο οι δείκτες δεδομένων.

Ένας τύπος δενδρικού καταλόγου είναι το Δυαδικό Δένδρο Αναζήτησης ΔΔΑ (Binary search tree). Το πρόβλημα που υπάρχει με το ΔΔΑ είναι ότι αν δοθούν κλειδιά σχεδόν ταξινομημένα τότε το δένδρο εκφυλίζεται δηλαδή δεν είναι ισοζυγισμένο (balanced tree). Ισοζυγισμένο είναι το δένδρο όπου το μακρύτερο μονοπάτι από την ρίζα προς τα φύλλα διαφέρει από το συντομότερο μονοπάτι όχι περισσότερο από ένα επίπεδο. Ακόμη στο ΔΔΑ όταν διαγράφεται κόμβος πιθανόν να χρειαστεί αναδιοργάνωση του δένδρου.

Έτσι οδηγήθηκαν στην έννοια του Β-Δένδρου (B-Tree). Με τα ΔΔΑ η κατασκευή του δένδρου ξεκινάει από την ρίζα και προχωράει προς τα κάτω. Όταν υπήρχε πρόβλημα με τη ρίζα προσπαθούσαν να βρουν τρόπους να την αλλάξουν. Έτσι οι Bayer και McCreight αντελήφτηκαν ότι το πρόβλημα ήταν η ρίζα και διαπίστωσαν ότι αντί να προσπαθούν να την αλλάξουν κατασκεύασαν έναν αλγόριθμο δημιουργίας δένδρου όπου γίνεται προσπάθεια να “αναδυθεί” η ρίζα.

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

• Κάθε κόμβος περιέχει το μέγιστο 2d κλειδιά και 2d + 1 δείκτες.

• Κανένας κόμβος εκτός της ρίζας δεν μπορεί να έχει λιγότερο από d κλειδιά.

• Όλοι οι εξωτερικοί κόμβοι βρίσκονται στο ίδιο επίπεδο.

Ως παράγοντας διακλάδωσης (fan-out factor) ορίζεται το πλήθος των δεικτών που είναι αποθηκευμένα σε κάθε κόμβο δένδρου.

Άρα με βάση τα παραπάνω 3 χαρακτηριστικά σ’ ένα Β-δένδρο ο παράγοντας διακλάδωσης θα είναι μεταξύ d + 1 και 2d + 1. Το Β-δένδρο αυξάνεται καθώς γίνεται προσθήκη νέων κλειδιών. Όταν ένα κλειδί εισάγεται σε κόμβο που είναι γεμάτος, τότε ο κόμβος διασπάται σε 3 φάσεις. Το μεσαίο κλειδί ανεβαίνει ένα επίπεδο προς τα πάνω, στον κόμβο πατέρα όλα τα κλειδιά αριστερά του μεσαίου μένουν στον κόμβο, ενώ τα δεξιά κλειδιά του μεσαίου κλειδιού τοποθετούνται σε νέο κόμβο. Κατά τη διαγραφή συμβαίνουν αντίστροφες διαδικασίες αυτής της προσθήκης κλειδιού με το επιπλέον βήμα ότι ένας κόμβος δεν μπορεί να έχει λιγότερο από d κλειδιά. Αυτό επιτυγχάνεται με την περιστροφή κλειδιών μεταξύ κόμβων και τέλος με συνδυασμό κόμβων.

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

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

Κατά τις διαδικασίες της προσθήκης και διαγραφής κλειδιού στο Β-δένδρο ο Buffer που χρησιμοποιείται για την αποθήκευση του περιεχομένου κάθε κόμβου, είναι λίγο μεγαλύτερου μεγέθους από το μέγεθος του κόμβου. Έτσι ο buffer πρέπει να χωράει 2d + 1 κλειδιά και 2d + 2 δείκτες. Ακόμη κερδίζουμε από περιττές αναγνώσεις από τον δίσκο αν χρησιμοποιηθεί κάποια μέθοδος για την αποθήκευση στην RAM κόμβων που είναι αποθηκευμένοι μεταξύ της ρίζας και τερματικού κόμβου. Κατάλληλη δομή για την αποθήκευση των κόμβων - buffer είναι η στοίβα, ώστε όταν χρειασθεί να μετακινηθούμε προς τα πίσω στο δένδρο, ο κόμβος που θα χρειασθεί θα βρίσκεται στην κορυφή της στοίβας. Μόνο οι κόμβοι που τροποποιήθηκαν μετά από προσθήκη ή διαγραφή κλειδιού χρειάζεται να αποθηκευθούν εκ νέου στο αρχείο κατάλογο.

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

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

Παράδειγμα 1ο

Έστω ότι θα δημιουργήσω ένα Β-δένδρο με τάξη 1 και έστω ότι θα εισάγουμε τις λέξεις

Η δημιουργία του παραπάνω Β-δένδρου έγινε χωρίς ανακατανομή (redistribution). Δηλαδή κάθε φορά που είχαμε υπερχείλιση σε κόμβο κάναμε προαγωγή (promotion) και διάσπαση (split) χωρίς να ελέγχουμε αν ήταν ανακατανομή. Θα εφαρμόσουμε τα ίδια δεδομένα κάνοντας ανακατανομή, όπου θα δούμε ότι θα προκύψει πιο θαμνώδες δένδρο, δηλαδή δεν θα αυξηθεί το ύψος του.

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

Παράδειγμα 2ο

Εικ. 9.3: Ο κόμβος (1) υπερχειλίζει μετά την προσθήκη του “Bill”

Η 1η εικόνα παρουσιάζει ένα Β-δένδρο 2 επιπέδων. Θα εισάγουμε τα κλειδιά “Bob” και “Bill”. Η προσθήκη του “Bob” γίνεται χωρίς προβλήματα αφού ο κόμβος (1) δεν είναι πλήρης. Αυτός ο τύπος προσθήκης είναι κανόνας και όχι εξαίρεση. Η προσθήκη του κλειδιού “Bill” προκαλεί υπερχείλιση στον κόμβο (1). Οι σημειωμένες με τελείες γραμμές της εικ. 9.3 δηλώνουν χώρο που είναι διαθέσιμος στον κόμβο-buffer κι όχι στον κόμβο του αρχείου καταλόγου. Η υπερχείλιση πρέπει να διορθωθεί πριν ξαναγραφεί το περιεχόμενο του κόμβου-buffer στον κόμβο του αρχείου καταλόγου. Η υπερχείλιση του κόμβου (1) διορθώνεται με την ανακατανομή. Ανακατανομή σημαίνει ότι τα πλεονάζοντα κλειδιά μοιράζονται σε γειτονικό αδελφό κόμβο που δεν είναι πλήρης. Στην περίπτωσή μας ο κόμβος (2) δεν είναι πλήρης και επιλέγεται για ανακατανομή. Τα στοιχεία μεταξύ των 2 κόμβων μοιράζονται εξίσου. Στην περίπτωσή μας (5 + 3) / 2 = 4 στοιχεία σε κάθε κόμβο.

Όμως το κλειδί David δεν μπορεί να μετακινηθεί στον κόμβο (2) γιατί το κλειδί “Ed” του κόμβου (0) που χωρίζει τους κόμβους (1) και (2) θα ήταν λάθος τοποθετημένο. Η ανακατανομή γίνεται ως εξής: τίθενται σε λεξικογραφική διάταξη όλα τα κλειδιά των κόμβων (1) και (2) (αδελφών κόμβων) αλλά και το κλειδί του κόμβου (0) που τα χωρίζει. Έτσι έχουμε:

Any, Bill, Bob, Chris, David, Ed, Frank, George, Hans

Εικ.9.4 : Το Β-δένδρο μετά την ανακατανομή των κλειδιών μεταξύ των κόμβων 0, 1, 2

Εικ. 9.5 : Ο κόμβος 1 υπερχειλίζει με την εισαγωγή του “Cal”

Εικόνα 9.8 : Το Β-δένδρο μετά τον διαχωρισμό των κόμβων 0 και 1

• Προσθήκη

Ο αλγόριθμος 7_1 δεν είναι περίπλοκος σε γενικές γραμμές, αλλά οι λεπτομέρειες που αφορούν στην ανάγνωση, εγγραφή, κόμβους-buffer και η μετακίνηση μεταξύ κόμβων είναι αρκετά πολύπλοκες. Η διαδικασία προσθήκης κλειδιού σε Β-δένδρο απαιτεί μεγάλο πλήθος άλλων διαδικασιών αν θέλουμε να δοθεί σε λεπτομερή έκφραση. Για να μην χαθούμε όμως σε λεπτομέρειες ο αλγόριθμος παρουσιάζεται σε ψευδοκώδικα όπου για τις διαδικασίες Insert, Find, Redistribute έχει γίνει αντιληπτό από το παράδειγμα τι υλοποιούν.

procedure ADD(tree, entry);

FIND LEAF node FOR KEY OF entry;

INSERT entry INTO node;

CHECK_FOR_OVERFLOW(tree, node);

procedure CHECK_FOR_OVERFLOW(tree, node);

IF number_of_entries > 2*d THEN

IF left-brother-node-entries < 2*d OR right-brother-node-entries

THEN REDISTRIBUTE

ELSE BEGIN

SPLIT-NODE;

IF root-node-was-split THEN BEGIN

GET-NEW-NODE;

INSERT middle-entry INTO

new-root-node;

END

ELSE BEGIN

INSERT middle-entry INTO father-node;

CHECK-FOR-OVERFLOW(tree, father-node);

END;

END;

Η βασική διαδικασία Add είναι απλή εκτός από την περίπτωση να συμβεί υπερχείλιση. Η περίπτωση να συμβεί υπερχείλιση σε κόμβο ελέγχεται από την διαδικασία Check-for -overflow. Η διαδικασία αυτή διαπιστώνει αν ένας κόμβος έχει υπερχείλιση. Αν ναι τότε προσπαθεί πρώτα να κάνει ανακατανομή. Αν αποτύχει διασπά τον κόμβο και προωθεί τον μεσαίο στοιχείο στον κόμβο πατέρα. Αν υπερχειλίσει και ο πατέρας τότε εφαρμόζει πάλι την ίδια διαδικασία. Η Check-for -overflow καλεί τον εαυτό της αναδρομικά. Θα πρέπει να θυμόμαστε ότι η περίπτωση να συμβεί υπερχείλιση ακόμη και σε τερματικό κόμβο είναι 1/d. Έτσι η διαδικασία Check-for -overflow δεν καλείται και τόσο συχνά.

• Διαγραφή

Ο αλγόριθμος αυτός θα λέγαμε ότι είναι σχεδόν ο αντίστροφος του Add. H μόνη διαφορά είναι όταν το στοιχείο που διαγράφεται δεν ανήκει σε τερματικό κόμβο. Όταν συμβούν διαγραφές σε τερματικό κόμβο, όπως συνήθως συμβαίνει, το στοιχείο απομακρύνεται από τον κόμβο. Μετά απ’ αυτό χρειάζεται να γίνει έλεγχος μήπως συμβεί υποχείλιση. Αυτό συμβαίνει όταν οποιοσδήποτε κόμβος έχει λιγότερα στοιχεία από d (εκτός της ρίζας).

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

Εικόνα 9.9 : Το Β-δένδρο μετά τη διαγραφή του «Cal» και την ανακατανομή

Εικόνα 9.10 : B-Δένδρο μετά τη διαγραφή του «Bill» και τον συνδυασμό κόμβων

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

Ο αλγόριθμος 7_2 υλοποιεί τα προηγούμενα. Η διαδικασία Check-for underflow είναι ανάλογη της Check-for overflow.

procedure DELETE(tree, key);

FIND node WITH entry THAT MATCHES KEY;

IF node-is-leaf THEN BEGIN

DELETE entry FROM node;

CHECK-FOR-UNDEFLOW(tree, node);

END

ELSE BEGIN

FIND RIGHTMOST leaf-node of left-subtree;

REPLACE entry THAT MATCHES key WITH RIGHTMOST entry of leaf-node;

CHECK-FOR-UNDERFLOW(tree, leaf-node);

END;

procedure CHECK_FOR_UNDERFLOW(tree, node);

IF number-of-entries < d THEN

IF left-brother-node-entries > d or right-brother-node-entries > d THEN REDISTRIBUTE

ELSE BEGIN

COMBINE-NODES;

DELETE entry FROM father-node;

IF father-node-is-not-root and root-node-is-empty THEN

RETURN_OLD_NODE(root, node);

ELSE

IF father-node-is-root THEN

CHECK_FOR_UNDEFLOW(tree, father-node);

END;

Και εδώ η βασική διαδικασία είναι απλή εκτός κι αν συμβεί υποχείλιση. Η Check-for underflow χρησιμοποιείται όταν σε κάποιο κόμβο συμβεί υποχείλιση και στους προγόνους της.

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

Αυτός ο αλγόριθμος είναι λιγότερο περίπλοκος από τους αλγόριθμους Add και Delete. Κατ’ αρχήν εξετάζεται η ρίζα για να διαπιστωθεί είτε 1) μια τιμή κλειδιού που να ταυτίζεται με το αναζητούμενο κλειδί ή 2) τη θέση μέσα στην ακολουθία κλειδιών όπου το αναζητούμενο κλειδί θα μπορούσε να τοποθετηθεί. Αν συμβεί το (1) τότε επιστρέφεται η τιμή του δείκτη δεδομένων. Αν δεν συμβεί το (1) χρησιμοποιείται ο κατάλληλος δείκτης δένδρου για να αναζητηθεί ο κατάλληλος κόμβος στο επόμενο επίπεδο του δένδρου. Αν δεν υπάρχει επόμενο επίπεδο, η αναζήτηση αποτυγχάνει και επιστρέφεται η τιμή null. Ο αλγόριθμος είναι αναδρομικός καλώντας τον εαυτό του κάθε φορά που κατεβαίνει ένα επίπεδο στο δένδρο. Οι συναρτήσεις KEY, LEFT, RIGHT, POINTER χρησιμοποιούνται για να μας επιστραφεί η τιμή του κλειδιού, του αριστερού δείκτη δένδρου, του δεξιού δείκτη δένδρου και δείκτη δεδομένων που αντιστοιχούν σε συγκεκριμένο κλειδί. Τα κλειδιά ενός κόμβου αριθμούνται από αριστερά προς τα δεξιά, αρχίζοντας από την τιμή 1. Η COUNT είναι συνάρτηση που επιστρέφει το πλήθος των ενεργών κλειδιών στον αντίστοιχο κόμβο. Υποθέτουμε ότι κάθε κόμβος αντιστοιχεί σε μια φυσική εγγραφή του αρχείο.

integer function FIND(tree, node, givenkey);

{returns data pointer if match found, null value if not found}

{node is the root node for the initial call}

i :=1; {start search of node with first key in node}

WHILE KEY(node, i) < givenkey and i < COUNT(node) DO

i := i+1; {sequentail search of current node}

IF KEY(node, i) = givenkey THEN FIND := POINTER(i);

{match found}

ELSE BEGIN

IF KEY(node, i) > givenkey THEN p := LEFT(node, i);

{search left subtree}

ELSE p := RIGHT(node, i); {search right subtree}

IF p <> null THEN BEGIN {search next level of the tree}

READ_DIRECT(tree, nextnode, p)

{read node at next level}

FIND := FIND(tree, nextnode, giventree);

END

ELSE FIND := null; {no next level, search has failed}

END;

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

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

Ο αλγόριθμος 7_4 αποτελεί γενίκευση της Indorder διάσχισης. Αντί να ξεκινάει από το πρώτο στοιχείο και να ψάχνει όλο το δένδρο, επιτρέπει η αναζήτηση να ξεκινήσει απ’ οποιοδήποτε στοιχείο και να τερματίζει σ’ οποιοδήποτε υψηλότερη τιμή. Έτσι είναι πιθανόν να αναγνωσθούν όλα τα κλειδιά για δοθέν διάστημα κλειδιών. Οι συναρτήσεις KEY, LEFT, RIGHT, POINTER, COUNT χρησιμοποιούνται όπως και στον αλγόριθμο 7_3.

Η διαδικασία TRAVERSE καλείται για να γίνει διάσχιση του Β-δένδρου. Το δένδρο και η ρίζα του δένδρου είναι οι 2 πρώτοι παράμετροι. Οι 2 επόμενες αντιστοιχούν στη μεγαλύτερη και στη μικρότερη τιμή του κλειδιού (lokey, hikey) για την διάσχιση. Η TRAVERSE καλεί την FIND-START για να εντοπίσει το πρώτο στοιχείο και να δημιουργηθεί η αρχική στοίβα. Οι διαδικασίες GET-NEXT-KEY και PROCESS καλούνται μετά επαναληπτικά. Η GET-NEXT-KEY προσδιορίζει τον δείκτη δεδομένων που αντιστοιχεί στο επόμενο κλειδί της διάσχισης και το επιστρέφει για να το επεξεργαστεί η PROCESSS. H GET-NEXT-KEY επιστρέφει την τιμή false όταν δεν υπάρχουν στοιχεία του δένδρου και η TRAVERSE τερματίζει.

Όταν γίνεται διάσχιση του δένδρου είναι αναγκαίο να γνωρίζουμε που βρισκόμαστε, που ήμασταν και που θα πάμε. Η στοίβα είναι η κατάλληλη δομή. Γι’ αυτό σ’ αυτόν τον αλγόριθμο θα χρησιμοποιήσουμε την στοίβα ως τοπική παράμετρο με το όνομα “nodestack”. Κάθε στοιχείο της στοίβας είναι ένα ζεύγος τιμών αποτελούμενο από τον κόμβο του δένδρου και έναν ακέραιο i. Ενα στοιχείο εισέρχεται στην στοίβα αν και μόνο αν ικανοποιoύνται 3 συνθήκες.

KEY(node, i) > lokey

l £ i £ COUNT(node)

για όλα τα j για τα οποία ισχύειl £ j < i , ΚΕΥ(node, j) < lokey ή το έχουμε επεξεργαστεί

Η διαδικασία PUSH(nodestack, (node, i)), προσθέτει ένα ζεύγος στη στοίβα. Η συνάρτηση POP(nodestack, (node, i)) εξάγει από τη στοίβα το ζεύγος που βρίσκεται στην κορυφή της στοίβας εφ’ όσον δεν είναι κενή. Σ’ αυτή την περίπτωση η POP επιστρέφει true αλλιώς false.

procedure TRAVERSE(tree, node, lokey, hikey);

{ calls FIND_FIRST to locate starting point in tree, calls GET-NEXT-KEY to fetch the data pointer for each qualified key, and calls PROCESS to process each data record}

local nodestack := null; {start with the node stack empty}

FIND_FIRST(tree, lokey, node, nodestack);

WHILE GET_NEXT_KEY(tree, hikey, nodestack. ptr) DO

PROCESS(ptr);

procedure FIND_FIRST(tree, lokey, node, nodestack);

{builds nodestack such that top entry is the first key ? lokey}

i := 1;

WHILE i £ COUNT(node) and KEY(node, i) DO

i := i+1;

IF i £ COUNT(node) THEN BEGIN

{KEY(node, i) ³ lokey and 1 £ j < i implies that KEY(node, j) < lokey}

PUSH(nodestack, (node, i)); {save this node for future traversal}

np := LEFT(node, i); {starting entry may be in left subtree}

END

ELSE {any possible beginning point must be in rightmost subtree}

np := RIGHT(node, COUNT(node));

{observe that no (node, i) pair is pushed onto nodestack because no key in this node is included in the traversal}

READ_DIRECT(tree, node, np); {get next node of subtree}

FIND_FIRST(tree, lokey, node, nodestack);

{recursive call for subtree}

END;

logical procedure GET_NEXT_KEY(tree, hikey, nodestack, ptr);

{if there is another key entry in the stack within the specified range, this procedure returns a value of true and ptr contains a pointer to the corresponding data record, otherwise, a value of false is returned}

ok := POP(nodestack, (node, i)); {get the top entry from the node stack}

IF ok {nodestack not empty} THEN BEGIN

IF KEY(node, i) = hikey THEN {end of the range}

ok := false;

ELSE BEGIN {key is valid}

ptr := POINTER(node, i);

np := RIGHT(node, i);

IF i = COUNT(node, i) THEN BEGIN

i := i+1; {move to next entry}

PUSH(nodestack, (node, i)) {replace node on stack}

END;

WHILE np <> null DO BEGIN {find leftmost leaf of subtree if any}

READ_DIRECT(tree, node, np);

PUSH(nodestack, (node, 1);

np := LEFT(node, 1);

END;

END; {if key is valid}

GET_NEXT_KEY := ok;

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

Μια βελτίωση μπορεί να γίνει και στην Add και στην Delete επιτρέποντας την ανακατανομή να γίνει σε περισσότερο από 2 κόμβους. Αυτό θα οδηγήσει σε δένδρο με καλύτερη ισορροπία και λιγότερους κόμβους.

Περίληψη

Το Β-δένδρο είναι μια αποτελεσματική δομή για κατάλογο. Έχει μόνο καλές ιδιότητες, όπως: πολυπλοκότητα log(N), αυτοισορροπείται, μικρό ύψος και αποτελεσματικά στατιστικά.