B ΔΕΝΤΡΟ στη δομή δεδομένων: Παράδειγμα αναζήτησης, εισαγωγής, διαγραφής λειτουργίας

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

Anonim

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

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

Το B-Tree είναι ένα ειδικό είδος δέντρου σε μια δομή δεδομένων. Το 1972, αυτή η μέθοδος εισήχθη για πρώτη φορά από τον McCreight και η Bayer το ονόμασε Height Balanced m-way Search Tree. Σας βοηθά να διατηρείτε δεδομένα ταξινομημένα και να επιτρέπουν διάφορες λειτουργίες όπως Εισαγωγή, αναζήτηση και διαγραφή σε λιγότερο χρόνο.

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

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

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

Εδώ είναι σημαντικοί κανόνες για τη δημιουργία του B_Tree

  • Όλα τα φύλλα θα δημιουργηθούν στο ίδιο επίπεδο.
  • Το B-Tree καθορίζεται από έναν αριθμό βαθμών, ο οποίος ονομάζεται επίσης "τάξη" (καθορίζεται από έναν εξωτερικό ηθοποιό, όπως ένας προγραμματιστής), που αναφέρεται ως 
    m
    εμπρός. Η αξία του 
    m
    εξαρτάται από το μέγεθος μπλοκ στο δίσκο στον οποίο βρίσκονται κυρίως τα δεδομένα.
  • Το αριστερό υποδένδρο του κόμβου θα έχει μικρότερες τιμές από τη δεξιά πλευρά του υποδέντρου. Αυτό σημαίνει ότι οι κόμβοι ταξινομούνται επίσης σε αύξουσα σειρά από αριστερά προς τα δεξιά.
  • Ο μέγιστος αριθμός θυγατρικών κόμβων, ένας ριζικός κόμβος καθώς και οι θυγατρικοί κόμβοι του μπορούν να περιέχουν υπολογίζονται με αυτόν τον τύπο: 
    m - 1
    Για παράδειγμα: 
    m = 4max keys: 4 - 1 = 3

  • Κάθε κόμβος, εκτός από το root, πρέπει να περιέχει ελάχιστα κλειδιά του 
    [m/2]-1
    Για παράδειγμα: 
    m = 4min keys: 4/2-1 = 1
  • Ο μέγιστος αριθμός θυγατρικών κόμβων που μπορεί να έχει ένας κόμβος είναι ίσος με τον βαθμό του, δηλαδή 
    m
  • Το ελάχιστο παιδί που μπορεί να έχει ένας κόμβος είναι το ήμισυ της παραγγελίας, που είναι m / 2 (λαμβάνεται η τιμή οροφής).
  • Όλα τα πλήκτρα σε έναν κόμβο ταξινομούνται με αυξανόμενη σειρά.

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

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

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

Ιστορία του Β Δέντρου

  • Τα δεδομένα αποθηκεύονται στο δίσκο σε μπλοκ, αυτά τα δεδομένα, όταν εισέρχονται στην κύρια μνήμη (ή RAM) ονομάζεται δομή δεδομένων.
  • Σε περίπτωση τεράστιων δεδομένων, η αναζήτηση μιας εγγραφής στο δίσκο απαιτεί την ανάγνωση ολόκληρου του δίσκου. Αυτό αυξάνει την κατανάλωση χρόνου και κύριας μνήμης λόγω της υψηλής συχνότητας πρόσβασης στο δίσκο και του μεγέθους δεδομένων.
  • Για να ξεπεραστεί αυτό, δημιουργούνται πίνακες ευρετηρίου που αποθηκεύουν την αναφορά εγγραφής των εγγραφών με βάση τα μπλοκ που βρίσκονται. Αυτό μειώνει δραστικά την κατανάλωση χρόνου και μνήμης.
  • Δεδομένου ότι έχουμε τεράστια δεδομένα, μπορούμε να δημιουργήσουμε πίνακες ευρετηρίου πολλαπλών επιπέδων.
  • Το ευρετήριο πολλαπλών επιπέδων μπορεί να σχεδιαστεί χρησιμοποιώντας το B Tree για τη διατήρηση των δεδομένων ταξινομημένων με τρόπο αυτο-εξισορρόπησης

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

Η λειτουργία αναζήτησης είναι η απλούστερη λειτουργία στο B Tree.

Εφαρμόζεται ο ακόλουθος αλγόριθμος:

  • Αφήστε το κλειδί (η τιμή) να αναζητηθεί από το "k".
  • Ξεκινήστε την αναζήτηση από τη ρίζα και διαδοχικά προς τα κάτω.
  • Εάν το k είναι μικρότερο από την τιμή ρίζας, αναζητήστε αριστερό υποδένδρο, εάν το k είναι μεγαλύτερο από την τιμή ρίζας, αναζητήστε το σωστό υποδένδρο
  • Εάν ο κόμβος έχει το εύρημα k, απλώς επιστρέψτε τον κόμβο.
  • Εάν το k δεν βρίσκεται στον κόμβο, διασχίστε το παιδί με ένα μεγαλύτερο κλειδί.
  • Εάν δεν βρεθεί k στο δέντρο, επιστρέφουμε NULL.

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

Δεδομένου ότι το B Tree είναι ένα δέντρο εξισορρόπησης, δεν μπορείτε να πιέσετε να εισαγάγετε ένα κλειδί σε οποιονδήποτε κόμβο.

Ισχύει ο ακόλουθος αλγόριθμος:

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

ΥΠΟΔΕΙΞΗ

Τα ακόλουθα δεν ισχύουν για τον αλγόριθμο εισαγωγής:

Δεδομένου ότι ο κόμβος είναι πλήρης, επομένως θα διαχωριστεί και στη συνέχεια θα εισαχθεί μια νέα τιμή

Στο παραπάνω παράδειγμα:

  • Αναζήτηση στην κατάλληλη θέση στον κόμβο για το κλειδί
  • Εισαγάγετε το κλειδί στον κόμβο προορισμού και ελέγξτε για κανόνες
  • Μετά την εισαγωγή, ο κόμβος έχει περισσότερο από ίσο με έναν ελάχιστο αριθμό κλειδιών, που είναι 1; Σε αυτήν την περίπτωση, ναι, το κάνει. Ελέγξτε τον επόμενο κανόνα.
  • Μετά την εισαγωγή, ο κόμβος έχει περισσότερο από έναν μέγιστο αριθμό κλειδιών, που είναι 3; Σε αυτήν την περίπτωση, όχι, όχι. Αυτό σημαίνει ότι το δέντρο δεν παραβιάζει κανόνες και η εισαγωγή έχει ολοκληρωθεί.

Στο παραπάνω παράδειγμα:

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

Στο παραπάνω παράδειγμα:

  • Ο κόμβος έχει λιγότερα από μέγιστα πλήκτρα
  • 1 εισάγεται δίπλα στο 3, αλλά παραβιάζεται ο κανόνας της αύξουσας παραγγελίας
  • Για να το διορθώσετε, τα πλήκτρα ταξινομούνται

Παρομοίως, τα 13 και 2 μπορούν να εισαχθούν εύκολα στον κόμβο καθώς πληρούν τον κανόνα των κλειδιών λιγότερο από το μέγιστο.

Στο παραπάνω παράδειγμα:

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

Ομοίως, βάσει των παραπάνω κανόνων και περιπτώσεων, οι υπόλοιπες τιμές μπορούν να εισαχθούν εύκολα στο B Tree.

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

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

Ισχύει ο ακόλουθος αλγόριθμος:

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

Εάν το κλειδί στόχος βρίσκεται στον κόμβο των φύλλων

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

Εάν το κλειδί προορισμού βρίσκεται σε έναν εσωτερικό κόμβο

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

Εάν το κλειδί προορισμού βρίσκεται σε έναν ριζικό κόμβο

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

Τώρα, ας κατανοήσουμε τη λειτουργία διαγραφής με ένα παράδειγμα.

Το παραπάνω διάγραμμα εμφανίζει διαφορετικές περιπτώσεις λειτουργίας διαγραφής σε ένα B-Tree. Αυτό το B-Tree είναι της τάξης 5, που σημαίνει ότι ο ελάχιστος αριθμός θυγατρικών κόμβων που μπορεί να έχει ένας κόμβος είναι 3 και ο μέγιστος αριθμός θυγατρικών κόμβων που μπορεί να έχει ένας κόμβος είναι 5. Ενώ ο ελάχιστος και μέγιστος αριθμός κλειδιών οποιοσδήποτε κόμβος μπορεί να έχει 2 και 4, αντίστοιχα.

Στο παραπάνω παράδειγμα:

  • Ο κόμβος στόχος έχει το κλειδί προορισμού για διαγραφή
  • Ο κόμβος στόχος έχει κλειδιά περισσότερα από τα ελάχιστα κλειδιά
  • Απλώς διαγράψτε το κλειδί

Στο παραπάνω παράδειγμα:

  • Ο κόμβος στόχος έχει κλειδιά ίσο με τα ελάχιστα πλήκτρα, οπότε δεν μπορείτε να το διαγράψετε απευθείας καθώς θα παραβιάζει τους όρους

Τώρα, το παρακάτω διάγραμμα εξηγεί πώς να διαγράψετε αυτό το κλειδί:

  • Ο κόμβος στόχος θα δανειστεί ένα κλειδί από τον άμεσο αδελφό, σε αυτήν την περίπτωση, τον προκάτοχο κατά σειρά (αριστερός αδελφός) επειδή δεν έχει διάδοχο στη σειρά (δεξιό αδελφό)
  • Η μέγιστη τιμή του προκάτοχου inorder θα μεταφερθεί στον γονέα και ο γονέας θα μεταφέρει τη μέγιστη τιμή στον κόμβο προορισμού (δείτε το παρακάτω διάγραμμα)

Το ακόλουθο παράδειγμα δείχνει πώς να διαγράψετε ένα κλειδί που χρειάζεται μια τιμή από τον διάδοχό του.

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

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

Δείτε τη διαδικασία διαγραφής ενός τέτοιου κλειδιού:

  • Συγχωνεύστε τον κόμβο στόχου με οποιοδήποτε από τα άμεσα αδέλφια του μαζί με το γονικό κλειδί
    • Το κλειδί από τον γονικό κόμβο επιλέγεται ότι τα αδέλφια μεταξύ των δύο συγχωνευμένων κόμβων
  • Διαγράψτε το κλειδί προορισμού από τον συγχωνευμένο κόμβο

Διαγραφή του ψευδοκώδικα λειτουργίας

private int removeBiggestElement(){if (root has no child)remove and return the last elementelse {answer = subset[childCount-1].removeBiggestElement()if (subset[childCount-1].dataCount < MINIMUM)fixShort (childCount-1)return answer}}

Έξοδος :

Το μεγαλύτερο στοιχείο διαγράφεται από το B-Tree.

Περίληψη:

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