B + TREE: Παράδειγμα αναζήτησης, εισαγωγής και διαγραφής λειτουργιών

Πίνακας περιεχομένων:

Anonim

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

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

Σε αυτό το σεμινάριο B + Tree, θα μάθετε:

  • Τι είναι το δέντρο B +;
  • Κανόνες για το B + Tree
  • Γιατί να χρησιμοποιήσετε το δέντρο B +
  • B + Tree εναντίον B Tree
  • Λειτουργία αναζήτησης
  • Εισαγωγή λειτουργίας
  • Διαγραφή λειτουργίας

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

Εδώ είναι βασικοί κανόνες για το δέντρο B +.

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

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

Εδώ είναι οι λόγοι για τη χρήση του δέντρου B +:

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

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

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

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

Λειτουργία αναζήτησης

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

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

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

Αλγόριθμος λειτουργίας αναζήτησης

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

Έξοδος :

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

Εισαγωγή λειτουργίας

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

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

Εισαγωγή αλγορίθμου λειτουργίας

1. Even inserting at-least 1 entry into the leaf container does not make it full then add the record2. 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 treeb. 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 + εξηγείται στα παρακάτω βήματα:

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

Διαγραφή λειτουργίας

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

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

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

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

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

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

Διαγραφή αλγορίθμου λειτουργίας

1) Start at the root and go up to leaf node containing the key K2) Find the node n on the path from the root to the leaf node containing KA. If n is root, remove Ka. if root has more than one key, doneb. if root has only Ki) if any of its child nodes can lend a nodeBorrow key from the child and adjust child linksii) Otherwise merge the children nodes. It will be a new rootc. If n is an internal node, remove Ki) 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 nodeAdjust child linksElseMerge n with its siblingAdjust child linksd. If n is a leaf node, remove Ki) If n has at least ceil(M/2) elements, done!In case the smallest key is deleted, push up the next keyii) If n has less than ceil(m/2) elementsIf the sibling can lend a keyBorrow key from a sibling and adjust keys in n and its parent nodeElseMerge n and its siblingAdjust keys in the parent node

Έξοδος :

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

Περίληψη:

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