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

Τι είναι το B Tree;

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

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

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

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

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

    εμπρός. Η αξία του

    m

    εξαρτάται από το μέγεθος του μπλοκ στο δίσκο στον οποίο βρίσκονται κυρίως τα δεδομένα.

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

    Για παράδειγμα:

    m = 4
    max keys: 4 – 1 = 3
    

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

  • Κάθε κόμβος, εκτός από τη ρίζα, πρέπει να περιέχει ελάχιστα κλειδιά του
    [m/2]-1

    Για παράδειγμα:

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

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

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

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

Ιστορία του B Tree

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

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

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

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

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

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

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

Ισχύει ο παρακάτω αλγόριθμος:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ισχύει ο παρακάτω αλγόριθμος:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Το ακόλουθο παράδειγμα επεξηγεί τον τρόπο διαγραφής ενός κλειδιού που χρειάζεται μια τιμή από τον διάδοχό του κατά σειρά.

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

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

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

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

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

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

Διαγραφή Operation Ψευδοκώδικας

private int removeBiggestElement()
{
    if (root has no child)
        remove and return the last element
    else {
        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 αναζητά πρώτα το κλειδί προορισμού που πρόκειται να διαγραφεί, το διαγράφει, αξιολογεί την εγκυρότητα με βάση αρκετές περιπτώσεις, όπως τα ελάχιστα και μέγιστα κλειδιά του κόμβου προορισμού, των αδελφών και του γονέα.