Δομή B+ δέντρου Αναζήτηση Εισαγωγή Applet Τάξη Links Δομές Δεδομένων

Η δομή του Β+ δένδρου.

Ένα B+ δένδρο είναι ένα ειδικά σχεδιασμένο δένδρο αναζήτησης το οποίο έχει την ιδιότητα ότι είναι ισοζυγισμένο. Τα στοιχεία που αποθηκεύονται στο δένδρο αυτό είναι από κάποιο διατεταγμένο σύνολο τιμών S και αποθηκεύονται μόνο στα φύλλα του δέντρου. Οι εσωτερικοί κόμβοι έχουν ενδιάμεσες τιμές που βοηθούν στην αναζήτηση.
Λέμε ότι ένα B+ δένδρο είναι τάξης p όταν ο κάθε εσωτερικός κόμβος έχει το πολύ p παιδιά (ή δείκτες) και p-1 ενδιάμεσες τιμές αναζήτησης στην ακόλουθη διάταξη  <P1,K2,P2,K2,...,Pq-1,Kq-1,Pq> όπου Pi είναι ένας δείκτης προς έναν κόμβο-παιδί (ή δείκτης null), και Ki είναι μια τιμή αναζήτησης. Στην πραγματικότητα τα στοιχεία του συνόλου S αποθηκεύονται στα φύλλα ενώ κάποιες τιμές του S επαναλαμβάνονται στους εσωτερικούς κόμβους. Στο σχήμα 1  φαίνονται τα στοιχεία του συνόλου S τα οποία  έχουν αποθηκευτεί στα φύλλα του δέντρου. Οι τιμές 3, 50, 80, 200, 74 επαναλαμβάνονται στους εσωτερικούς κόμβους και διευκολύνουν την αναζήτηση κάποιου στοιχείου του S.

Σχήμα 1

 Χρησιμότητα του B+ δέντρου.

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

Το δέντρο προσφέρει γρήγορη αναζήτηση στοιχείου Κ που ανήκει στο πεδίο ευρετηριοποίησης. Συγκεκριμένα χρειάζονται h αναγνώσεις σελίδων προκειμένου να φέρουμε στη μνήμη την εγγραφή που περιέχει το Κ. 
Για περισσότερες λεπτομέρειες διαβάστε τη λειτουργία αναζήτησης στοιχείου στο B+ δέντρο.

Δομή εσωτερικών κόμβων B+ δέντρου τάξης p.

  1. Κάθε εσωτερικός κόμβος είναι της μορφής
                            <P1,K1,P2,K2,...,Pq-1,Kq-1,Pq>
    όπου q<p , Pi είναι ένας δείκτης δέντρου και Ki αριθμήσιμη ποσότητα.
  2. Σε κάθε εσωτερικό κόμβο, Κ1<Κ2<...<Κq-1.
  3. Για όλες τις τιμές  X του πεδίου αναζήτησης στο υποδέντρο που δείχνει το Pi, έχουμε Κi-1£X<Ki για 1<i<q, X<Ki για i=1 και Κi-1£X για i=q.
  4. Κάθε εσωτερικός κόμβος έχει το πoλύ p δείκτες δέντρου.
  5. Κάθε εσωτερικός κόμβος, εκτός από τη ρίζα, έχει το λιγότερο ι(p/2)ω   δείκτες δέντρου. Ο κόμβος-ρίζα έχει τουλάχιστον δύο δείκτες δέντρου αν είναι εσωτερικός κόμβος.
  6. Ένας εσωτερικός κόμβος με q δείκτες, q£p, έχει q-1 τιμές πεδίου αναζήτησης.
Στη διπλανή εικόνα βλέπουμε πως ο δείκτης Pi δείχνει ένα υποδέντρο στο οποίο τα στοιχεία αναζήτησης X έχουν τιμές μεταξύ Ki-1 και Ki.

Σχήμα 2: Γραφική απεικόνιση εσωτερικού κόμβου

Δομή κόμβων φύλλων ενός B+ δέντρου.

  1. Κάθε κόμβος φύλλο είναι της μορφής
                                <  <K1,Pr1>,<K2,Pr2>,...,<Kq-1,Prq-1>,Pnext >
    όπου q £ p, κάθε Pri είναι ένας δείκτης δεδομένων, και το  Pnext  δείχνει στον επόμενο κόμβο-φύλλο του B+ δέντρου.
  2. Σε κάθε κόμβο-φύλλο, K1<K2<...<Kq-1, q £ p.
  3. Κάθε Pri είναι ένας δείκτης που δείχνει στην εγγραφή της οποίας η τιμή στο πεδίο αναζήτησης είναι Ki.
  4. Κάθε κόμβος-φύλλο έχει τουλάχιστον ι(p/2)ω τιμές.
  5. Όλοι οι κόμβοι-φύλλα βρίσκονται στο ίδιο επίπεδο.

Σχήμα 3: Γραφική απεικόνιση κόμβου φύλλου