Δέντρο Β στη Δομή Δεδομένων: Αναζήτηση, Εισαγωγή, Διαγραφή

Τι είναι το 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

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

  m = 4
  min keys: 4/2 − 1 = 1

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

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

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

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

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

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

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

Η λειτουργία αναζήτησης είναι η απλούστερη λειτουργία σε ένα δέντρο Β. Εφαρμόζεται ο ακόλουθος αλγόριθμος:

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

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

Δεδομένου ότι ένα δέντρο B είναι ένα αυτοεξισορροπούμενο δέντρο, δεν μπορείτε να εισαγάγετε ένα κλειδί με επιβολή σε οποιονδήποτε κόμβο. Ισχύει ο ακόλουθος αλγόριθμος:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Διαγραφή OperaΨευδο Code

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.

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