B+ TREE: Αναζήτηση, Εισαγωγή και Διαγραφή Operaσεις

Τι είναι ένα δέντρο B+;

A B+ Δέντρο Χρησιμοποιείται κυρίως για την εφαρμογή δυναμικής ευρετηρίασης σε πολλαπλά επίπεδα. Σε σύγκριση με ένα B-Tree, το B+ Tree αποθηκεύει τους δείκτες δεδομένων μόνο στους κόμβους φύλλων του Tree, γεγονός που καθιστά τη διαδικασία αναζήτησης πιο ακριβή και ταχύτερη.

Κανόνες για το B+ Tree

Ακολουθούν οι βασικοί κανόνες για ένα δέντρο B+.

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

Γιατί να χρησιμοποιήσετε το B+ Tree

Ακολουθούν οι λόγοι για τη χρήση ενός δέντρου B+:

• Τα κλειδιά χρησιμοποιούνται κυρίως για να βοηθήσουν την αναζήτηση κατευθύνοντάς σας στο σωστό φύλλο.
• Ένα δέντρο B+ χρησιμοποιεί έναν «παράγοντα πλήρωσης» για να διαχειριστεί την αύξηση και τη μείωση σε ένα δέντρο.
• Στα δέντρα B+, πολλά κλειδιά μπορούν εύκολα να τοποθετηθούν στη σελίδα της μνήμης επειδή δεν έχουν τα δεδομένα που σχετίζονται με τους εσωτερικούς κόμβους. Επομένως, θα έχει γρήγορη πρόσβαση σε δεδομένα δέντρου που βρίσκονται στον κόμβο φύλλου.
• Μια ολοκληρωμένη πλήρης σάρωση όλων των στοιχείων χρειάζεται μόνο ένα γραμμικό πέρασμα επειδή όλοι οι κόμβοι φύλλων ενός δέντρου B+ συνδέονται μεταξύ τους.

B+ Tree εναντίον B Tree

Ακολουθούν οι κύριες διαφορές μεταξύ ενός δέντρου B+ και ενός δέντρου B.

Αναζήτηση Operaσμού

Σε ένα δέντρο B+, η αναζήτηση είναι μια από τις ευκολότερες διαδικασίες που πρέπει να εκτελεστεί και δίνει γρήγορα και ακριβή αποτελέσματα.

Ισχύει ο ακόλουθος αλγόριθμος αναζήτησης:

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

Αναζήτηση Operaαλγόριθμος tion

1. Call the binary search method on the records in the B+ Tree.
2. If the search parameters match the exact key
       The accurate result is returned and displayed to the user
   Else, if the node being searched is the current and the exact key is not found by the algorithm
       Display the statement "Recordset cannot be found."

Παραγωγή: Η αντιστοιχισμένη εγγραφή που έχει οριστεί με το ακριβές κλειδί εμφανίζεται στον χρήστη. Διαφορετικά, μια αποτυχημένη προσπάθεια εμφανίζεται στον χρήστη.

Κύριο θέμα Operaσμού

Ο ακόλουθος αλγόριθμος ισχύει για τη λειτουργία εισαγωγής:

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

Κύριο θέμα Operaαλγόριθμος tion

1. If inserting at least 1 entry into the leaf container does not make it full, then add the record.
2. Else, divide the node into more locations to fit more records.
   a. Assign a new leaf and transfer 50 percent of the node elements to a new placement in the tree.
   b. The minimum key of the binary tree leaf and its new key address are associated with the top-level node.
   c. Divide the top-level node if it gets full of keys and addresses.
      i. Similarly, insert a key in the center of the top-level node in the hierarchy of the Tree.
   d. Continue to execute the above steps until a top-level node is found that does not need to be divided anymore.
3. Build a new top-level root node of 1 key and 2 indicators.

Παραγωγή: Ο αλγόριθμος θα καθορίσει το στοιχείο και θα το εισαγάγει με επιτυχία στον απαιτούμενο κόμβο φύλλου.

Το παραπάνω παράδειγμα δείγματος B+ Tree εξηγείται στα παρακάτω βήματα:

• Αρχικά, έχουμε 3 κόμβους και τα πρώτα 3 στοιχεία, τα οποία είναι 1, 4 και 6, προστίθενται σε κατάλληλες θέσεις στους κόμβους.
• Η επόμενη τιμή στη σειρά δεδομένων είναι το 12, το οποίο πρέπει να γίνει μέρος του Δέντρου.
• Για να το πετύχουμε αυτό, διαιρούμε τον κόμβο και προσθέτουμε το 6 ως στοιχείο δείκτη.
• Τώρα, δημιουργείται μια δεξιά ιεραρχία ενός δέντρου και οι υπόλοιπες τιμές δεδομένων προσαρμόζονται ανάλογα από το keeping λάβετε υπόψη τους ισχύοντες κανόνες τιμών ίσων ή μεγαλύτερων από έναντι των κόμβων κλειδιού-τιμής στα δεξιά.

Διαγραφή Operaσμού

Η πολυπλοκότητα της διαδικασίας διαγραφής στο δέντρο B+ ξεπερνά αυτή της λειτουργίας εισαγωγής και αναζήτησης.

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

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

Το παραπάνω παράδειγμα απεικονίζει τη διαδικασία αφαίρεσης ενός στοιχείου από ένα δέντρο B+ συγκεκριμένης τάξης.

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

• Στο παραπάνω παράδειγμα, πρέπει να διαγράψουμε το 31 από το δέντρο.
• Πρέπει να εντοπίσουμε τις εμφανίσεις του 31 στο Index και στο Leaf.
• Μπορούμε να δούμε ότι το 31 είναι διαθέσιμο τόσο σε επίπεδο κόμβου Ευρετηρίου όσο και σε επίπεδο Φύλλου. Επομένως, το διαγράφουμε και από τις δύο περιπτώσεις.
• Αλλά πρέπει να συμπληρώσουμε τον δείκτη που δείχνει προς το 42. Τώρα θα εξετάσουμε το σωστό παιδί κάτω των 25 ετών και θα πάρουμε την ελάχιστη τιμή και θα την τοποθετήσουμε ως δείκτη. Έτσι, εφόσον το 42 είναι η μόνη τιμή που υπάρχει, θα γίνει ο δείκτης.

Διαγραφή Operaαλγόριθμος tion

1) Start at the root and go up to the leaf node containing the key K.
2) Find the node n on the path from the root to the leaf node containing K.
   A. If n is root, remove K
      a. if root has more than one key, done
      b. if root has only K
         i)  if any of its child nodes can lend a node
             Borrow key from the child and adjust child links
         ii) Otherwise merge the children nodes. It will be a new root
      c. If n is an internal node, remove K
         i)  If n has at least ceil(m/2) keys, done!
         ii) If n has less than ceil(m/2) keys,
             If a sibling can lend a key,
                Borrow key from the sibling and adjust keys in n and the parent node
                Adjust child links
             Else
                Merge n with its sibling
                Adjust child links
      d. If n is a leaf node, remove K
         i)  If n has at least ceil(M/2) elements, done!
             In case the smallest key is deleted, push up the next key
         ii) If n has less than ceil(m/2) elements
             If the sibling can lend a key
                Borrow key from a sibling and adjust keys in n and its parent node
             Else
                Merge n and its sibling
                Adjust keys in the parent node

Παραγωγή: Το κλειδί «K» διαγράφεται και δανείζονται κλειδιά από τα αδέλφια για την προσαρμογή τιμών στο n και στους γονικούς κόμβους του, εάν χρειάζεται.

Συχνές Ερωτήσεις