Β-δέντρο

Σε αυτό το σεμινάριο, θα μάθετε τι είναι ένα δέντρο B. Επίσης, θα βρείτε λειτουργικά παραδείγματα λειτουργίας αναζήτησης σε ένα δέντρο B σε C, C ++, Java και Python.

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

Είναι επίσης γνωστό ως ισορροπημένο ύψος δέντρο.

Β-δέντρο

Γιατί Β-δέντρο;

Η ανάγκη για B-tree προέκυψε με την αύξηση της ανάγκης για μικρότερο χρόνο στην πρόσβαση στα φυσικά μέσα αποθήκευσης όπως ένας σκληρός δίσκος. Οι δευτερεύουσες συσκευές αποθήκευσης είναι πιο αργές με μεγαλύτερη χωρητικότητα. Υπήρχε ανάγκη για τέτοιου είδους τύπους δομών δεδομένων που ελαχιστοποιούν τις προσβάσεις στο δίσκο.

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

Ωστόσο, το B-tree μπορεί να αποθηκεύσει πολλά κλειδιά σε έναν μόνο κόμβο και μπορεί να έχει πολλούς θυγατρικούς κόμβους. Αυτό μειώνει σημαντικά το ύψος επιτρέποντας ταχύτερες προσβάσεις στο δίσκο.

Ιδιότητες B-tree

Για κάθε κόμβο x, τα κλειδιά αποθηκεύονται σε αυξανόμενη σειρά.
Σε κάθε κόμβο, υπάρχει μια δυαδική τιμή x. φύλλο που ισχύει εάν το x είναι φύλλο.
Εάν n είναι η σειρά του δέντρου, κάθε εσωτερικός κόμβος μπορεί να περιέχει το πολύ πλήκτρα n - 1 μαζί με ένα δείκτη σε κάθε παιδί.
Κάθε κόμβος εκτός από το root μπορεί να έχει το πολύ n παιδιά και τουλάχιστον n / 2 παιδιά.
Όλα τα φύλλα έχουν το ίδιο βάθος (δηλαδή ύψος-h του δέντρου).
Η ρίζα έχει τουλάχιστον 2 παιδιά και περιέχει τουλάχιστον 1 κλειδί.
Εάν n ≧ 1, τότε για κάθε n-κλειδί Β-δέντρο ύψους h και ελάχιστος βαθμός t ≧ 2, .h ≧ log_t (n+1)/2

Λειτουργίες

Ερευνητικός

Η αναζήτηση ενός στοιχείου σε ένα δέντρο B είναι η γενικευμένη μορφή αναζήτησης ενός στοιχείου σε ένα δέντρο δυαδικής αναζήτησης. Ακολουθούνται τα ακόλουθα βήματα.

Ξεκινώντας από τον ριζικό κόμβο, συγκρίνετε το k με το πρώτο κλειδί του κόμβου.
Εάν k = the first key of the node, επιστρέψτε τον κόμβο και το ευρετήριο.
Εάν k.leaf = true, επιστρέψτε NULL (δηλ. Δεν βρέθηκε).
Εάν k < the first key of the root node, αναζητήστε το αριστερό παιδί αυτού του κλειδιού αναδρομικά.
Εάν υπάρχουν περισσότερα από ένα κλειδιά στον τρέχοντα κόμβο και k> the first key, συγκρίνετε το k με το επόμενο κλειδί στον κόμβο.
Εάν k < next key, αναζητήστε το αριστερό παιδί αυτού του κλειδιού (δηλ. Το k βρίσκεται μεταξύ του πρώτου και του δεύτερου πλήκτρου).
Αλλιώς, αναζητήστε το σωστό παιδί του κλειδιού.
Επαναλάβετε τα βήματα 1 έως 4 μέχρι να φτάσει το φύλλο.

Παράδειγμα αναζήτησης

Ας αναζητήσουμε το κλειδί k = 17στο δέντρο κάτω του βαθμού 3. Β-δέντρο
Το k δεν βρίσκεται στη ρίζα, συγκρίνετέ το με το βασικό κλειδί. Το k δεν βρίσκεται στον ριζικό κόμβο
Από τότε k> 11, μεταβείτε στο δεξί παιδί του ριζικού κόμβου. Μεταβείτε στο σωστό υποδένδρο
Συγκρίνετε k με 16. Από τότε k> 16, συγκρίνετε k με το επόμενο πλήκτρο 18. Συγκρίνετε με τα πλήκτρα από αριστερά προς τα δεξιά
Δεδομένου ότι k < 18, το k βρίσκεται μεταξύ 16 και 18. Η αναζήτηση στο δεξί παιδί του 16 ή το αριστερό παιδί του 18 k βρίσκεται μεταξύ 16 και 18
βρέθηκε το k. βρέθηκε το k

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

 BtreeSearch(x, k) i = 1 while i ≦ n(x) and k ≧ keyi(x) // n(x) means number of keys in x node do i = i + 1 if i n(x) and k = keyi(x) then return (x, i) if leaf (x) then return NIL else return BtreeSearch(ci(x), k)

Για να μάθετε περισσότερα σχετικά με τις διάφορες λειτουργίες B-tree, επισκεφθείτε τη διεύθυνση

Εισαγωγή στο δέντρο B
Διαγραφή στο δέντρο B

Παραδείγματα Python, Java και C / C ++

Python Java C C ++

# Searching a key on a B-tree in Python # Create node class BTreeNode: def __init__(self, leaf=False): self.leaf = leaf self.keys = () self.child = () class BTree: def __init__(self, t): self.root = BTreeNode(True) self.t = t # Print the tree def print_tree(self, x, l=0): print("Level ", l, " ", len(x.keys), end=":") for i in x.keys: print(i, end=" ") print() l += 1 if len(x.child)> 0: for i in x.child: self.print_tree(i, l) # Search key def search_key(self, k, x=None): if x is not None: i = 0 while i x.keys(i)(0): i += 1 if i  = 0 and k(0)  = 0 and k(0)  x.keys(i)(0): i += 1 self.insert_non_full(x.child(i), k) # Split def split(self, x, i): t = self.t y = x.child(i) z = BTreeNode(y.leaf) x.child.insert_key(i + 1, z) x.keys.insert_key(i, y.keys(t - 1)) z.keys = y.keys(t: (2 * t) - 1) y.keys = y.keys(0: t - 1) if not y.leaf: z.child = y.child(t: 2 * t) y.child = y.child(0: t - 1) def main(): B = BTree(3) for i in range(10): B.insert_key((i, 2 * i)) B.print_tree(B.root) if B.search_key(8) is not None: print("Found") else: print("Not found") if __name__ == '__main__': main()

 // Searching a key on a B-tree in Java public class BTree ( private int T; // Node creation public class Node ( int n; int key() = new int(2 * T - 1); Node child() = new Node(2 * T); boolean leaf = true; public int Find(int k) ( for (int i = 0; i < this.n; i++) ( if (this.key(i) == k) ( return i; ) ) return -1; ); ) public BTree(int t) ( T = t; root = new Node(); root.n = 0; root.leaf = true; ) private Node root; // Search key private Node Search(Node x, int key) ( int i = 0; if (x == null) return x; for (i = 0; i < x.n; i++) ( if (key < x.key(i)) ( break; ) if (key == x.key(i)) ( return x; ) ) if (x.leaf) ( return null; ) else ( return Search(x.child(i), key); ) ) // Splitting the node private void Split(Node x, int pos, Node y) ( Node z = new Node(); z.leaf = y.leaf; z.n = T - 1; for (int j = 0; j < T - 1; j++) ( z.key(j) = y.key(j + T); ) if (!y.leaf) ( for (int j = 0; j = pos + 1; j--) ( x.child(j + 1) = x.child(j); ) x.child(pos + 1) = z; for (int j = x.n - 1; j>= pos; j--) ( x.key(j + 1) = x.key(j); ) x.key(pos) = y.key(T - 1); x.n = x.n + 1; ) // Inserting a value public void Insert(final int key) ( Node r = root; if (r.n == 2 * T - 1) ( Node s = new Node(); root = s; s.leaf = false; s.n = 0; s.child(0) = r; Split(s, 0, r); insertValue(s, key); ) else ( insertValue(r, key); ) ) // Insert the node final private void insertValue(Node x, int k) ( if (x.leaf) ( int i = 0; for (i = x.n - 1; i>= 0 && k  = 0 && k x.key(i)) ( i++; ) ) insertValue(x.child(i), k); ) ) public void Show() ( Show(root); ) // Display private void Show(Node x) ( assert (x == null); for (int i = 0; i < x.n; i++) ( System.out.print(x.key(i) + " "); ) if (!x.leaf) ( for (int i = 0; i < x.n + 1; i++) ( Show(x.child(i)); ) ) ) // Check if present public boolean Contain(int k) ( if (this.Search(root, k) != null) ( return true; ) else ( return false; ) ) public static void main(String() args) ( BTree b = new BTree(3); b.Insert(8); b.Insert(9); b.Insert(10); b.Insert(11); b.Insert(15); b.Insert(20); b.Insert(17); b.Show(); if (b.Contain(12)) ( System.out.println("found"); ) else ( System.out.println("not found"); ) ; ) )

// Searching a key on a B-tree in C #include #include #define MAX 3 #define MIN 2 struct BTreeNode ( int val(MAX + 1), count; struct BTreeNode *link(MAX + 1); ); struct BTreeNode *root; // Create a node struct BTreeNode *createNode(int val, struct BTreeNode *child) ( struct BTreeNode *newNode; newNode = (struct BTreeNode *)malloc(sizeof(struct BTreeNode)); newNode->val(1) = val; newNode->count = 1; newNode->link(0) = root; newNode->link(1) = child; return newNode; ) // Insert node void insertNode(int val, int pos, struct BTreeNode *node, struct BTreeNode *child) ( int j = node->count; while (j> pos) ( node->val(j + 1) = node->val(j); node->link(j + 1) = node->link(j); j--; ) node->val(j + 1) = val; node->link(j + 1) = child; node->count++; ) // Split node void splitNode(int val, int *pval, int pos, struct BTreeNode *node, struct BTreeNode *child, struct BTreeNode **newNode) ( int median, j; if (pos> MIN) median = MIN + 1; else median = MIN; *newNode = (struct BTreeNode *)malloc(sizeof(struct BTreeNode)); j = median + 1; while (j val(j - median) = node->val(j); (*newNode)->link(j - median) = node->link(j); j++; ) node->count = median; (*newNode)->count = MAX - median; if (pos val(node->count); (*newNode)->link(0) = node->link(node->count); node->count--; ) // Set the value int setValue(int val, int *pval, struct BTreeNode *node, struct BTreeNode **child) ( int pos; if (!node) ( *pval = val; *child = NULL; return 1; ) if (val val(1)) ( pos = 0; ) else ( for (pos = node->count; (val val(pos) && pos> 1); pos--) ; if (val == node->val(pos)) ( printf("Duplicates are not permitted"); return 0; ) ) if (setValue(val, pval, node->link(pos), child)) ( if (node->count < MAX) ( insertNode(*pval, pos, node, *child); ) else ( splitNode(*pval, pval, pos, node, *child, child); return 1; ) ) return 0; ) // Insert the value void insert(int val) ( int flag, i; struct BTreeNode *child; flag = setValue(val, &i, root, &child); if (flag) root = createNode(i, child); ) // Search node void search(int val, int *pos, struct BTreeNode *myNode) ( if (!myNode) ( return; ) if (val val(1)) ( *pos = 0; ) else ( for (*pos = myNode->count; (val val(*pos) && *pos> 1); (*pos)--) ; if (val == myNode->val(*pos)) ( printf("%d is found", val); return; ) ) search(val, pos, myNode->link(*pos)); return; ) // Traverse then nodes void traversal(struct BTreeNode *myNode) ( int i; if (myNode) ( for (i = 0; i count; i++) ( traversal(myNode->link(i)); printf("%d ", myNode->val(i + 1)); ) traversal(myNode->link(i)); ) ) int main() ( int val, ch; insert(8); insert(9); insert(10); insert(11); insert(15); insert(16); insert(17); insert(18); insert(20); insert(23); traversal(root); printf(""); search(11, &ch, root); )

// Searching a key on a B-tree in C++ #include using namespace std; class TreeNode ( int *keys; int t; TreeNode **C; int n; bool leaf; public: TreeNode(int temp, bool bool_leaf); void insertNonFull(int k); void splitChild(int i, TreeNode *y); void traverse(); TreeNode *search(int k); friend class BTree; ); class BTree ( TreeNode *root; int t; public: BTree(int temp) ( root = NULL; t = temp; ) void traverse() ( if (root != NULL) root->traverse(); ) TreeNode *search(int k) ( return (root == NULL) ? NULL : root->search(k); ) void insert(int k); ); TreeNode::TreeNode(int t1, bool leaf1) ( t = t1; leaf = leaf1; keys = new int(2 * t - 1); C = new TreeNode *(2 * t); n = 0; ) void TreeNode::traverse() ( int i; for (i = 0; i traverse(); cout << " " 
 search(k); ) void BTree::insert(int k) ( if (root == NULL) ( root = new TreeNode(t, true); root->keys(0) = k; root->n = 1; ) else ( if (root->n == 2 * t - 1) ( TreeNode *s = new TreeNode(t, false); s->C(0) = root; s->splitChild(0, root); int i = 0; if (s->keys(0) C(i)->insertNonFull(k); root = s; ) else root->insertNonFull(k); ) ) void TreeNode::insertNonFull(int k) ( int i = n - 1; if (leaf == true) ( while (i>= 0 && keys(i)> k) ( keys(i + 1) = keys(i); i--; ) keys(i + 1) = k; n = n + 1; ) else ( while (i>= 0 && keys(i)> k) i--; if (C(i + 1)->n == 2 * t - 1) ( splitChild(i + 1, C(i + 1)); if (keys(i + 1) insertNonFull(k); ) ) void TreeNode::splitChild(int i, TreeNode *y) ( TreeNode *z = new TreeNode(y->t, y->leaf); z->n = t - 1; for (int j = 0; j keys(j) = y->keys(j + t); if (y->leaf == false) ( for (int j = 0; j C(j) = y->C(j + t); ) y->n = t - 1; for (int j = n; j>= i + 1; j--) C(j + 1) = C(j); C(i + 1) = z; for (int j = n - 1; j>= i; j--) keys(j + 1) = keys(j); keys(i) = y->keys(t - 1); n = n + 1; ) int main() ( BTree t(3); t.insert(8); t.insert(9); t.insert(10); t.insert(11); t.insert(15); t.insert(16); t.insert(17); t.insert(18); t.insert(20); t.insert(23); cout << "The B-tree is: "; t.traverse(); int k = 10; (t.search(k) != NULL) ? cout << endl << k << " is found" : cout << endl << k << " is not Found"; k = 2; (t.search(k) != NULL) ? cout << endl << k << " is found" : cout << endl << k << " is not Found"; )