B+ TREE : Αναζήτηση, Εισαγωγή και Διαγραφή Operations Παράδειγμα

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

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

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

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

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

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

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

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

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

Εδώ, είναι οι κύριες διαφορές μεταξύ B+ Tree έναντι B Tree

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

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

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

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

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

Αναζήτηση 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.	Even 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 ως στοιχείο δείκτη.
• Τώρα, δημιουργείται μια ιεραρχία δεξιά ενός δέντρου και οι υπόλοιπες τιμές δεδομένων προσαρμόζονται ανάλογα, λαμβάνοντας υπόψη τους ισχύοντες κανόνες ίσων ή μεγαλύτερων από τιμές έναντι των κόμβων-τιμής κλειδιού στα δεξιά.

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

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

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

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

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

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

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

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

1) Start at the root and go up to 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 και στους γονικούς κόμβους του, εάν χρειάζεται.

Σύνοψη

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