Ograniczenia tradycyjnych drzew wyszukiwania binarnego mogą być frustrujące. Poznaj B-Tree, wszechstronną strukturę danych, która z łatwością radzi sobie z ogromnymi ilościami danych. Jeśli chodzi o przechowywanie i przeszukiwanie dużych ilości danych, tradycyjne drzewa wyszukiwania binarnego mogą stać się niepraktyczne ze względu na ich słabą wydajność i duże zużycie pamięci. B-Trees, znane również jako B-Tree lub Balanced Tree, to rodzaj samobalansującego drzewa, które zostało specjalnie zaprojektowane, aby pokonać te ograniczenia.
W przeciwieństwie do tradycyjnych drzew wyszukiwania binarnego, drzewa B charakteryzują się dużą liczbą kluczy, które mogą przechowywać w jednym węźle, dlatego nazywane są również dużymi drzewami kluczy. Każdy węzeł w drzewie B może zawierać wiele kluczy, co pozwala na to, aby drzewo miało większy współczynnik rozgałęzienia, a tym samym mniejszą wysokość. Ta niewielka wysokość prowadzi do mniejszej liczby operacji we/wy dysku, co skutkuje szybszymi operacjami wyszukiwania i wstawiania. B-Drzewa szczególnie dobrze nadają się do systemów pamięci masowej, które mają powolny i nieporęczny dostęp do danych, takich jak dyski twarde, pamięć flash i dyski CD-ROM.
B-Trees utrzymuje równowagę, zapewniając, że każdy węzeł ma minimalną liczbę kluczy, dzięki czemu drzewo jest zawsze zrównoważone. Bilans ten gwarantuje, że złożoność czasowa operacji takich jak wstawianie, usuwanie i wyszukiwanie wynosi zawsze O(log n), niezależnie od początkowego kształtu drzewa.
Złożoność czasowa drzewa B:
| Pan Nie. | Algorytm | Złożoność czasu |
|---|---|---|
| 1. | Szukaj | O(log n) |
| 2. | Wstawić | O(log n) |
| 3. | Usuwać | O(log n) |
Notatka: n jest całkowitą liczbą elementów w drzewie B
jsp javatpoint
Właściwości B-Tree:
- Wszystkie liście są na tym samym poziomie.
- B-Tree definiuje się mianem minimalnego stopnia „ T „. Wartość ' T ' zależy od rozmiaru bloku dysku.
- Każdy węzeł z wyjątkiem korzenia musi zawierać co najmniej klucze t-1. Korzeń może zawierać min 1 klucz.
- Wszystkie węzły (łącznie z korzeniem) mogą zawierać co najwyżej ( 2*t – 1 ) Klucze.
- Liczba dzieci węzła jest równa liczbie kluczy w nim plus 1 .
- Wszystkie klucze węzła są sortowane w kolejności rosnącej. Dziecko między dwoma kluczami k1 I k2 zawiera wszystkie klucze z zakresu od k1 I k2 .
- B-Tree rośnie i kurczy się od korzenia, w przeciwieństwie do drzewa wyszukiwania binarnego. Drzewa wyszukiwania binarnego rosną w dół, a także kurczą się w dół.
- Podobnie jak w przypadku innych zrównoważonych drzew wyszukiwania binarnego, złożoność czasowa wyszukiwania, wstawiania i usuwania wynosi O (log n).
- Wstawienie węzła do B-drzewa następuje tylko w węźle liścia.
Poniżej znajduje się przykład drzewa B o minimalnym rzędzie 5
Notatka: że w praktycznych drzewach B wartość minimalnego zamówienia jest znacznie większa niż 5.
Na powyższym diagramie widzimy, że wszystkie węzły-liście są na tym samym poziomie, a wszystkie nie-liście nie mają pustego poddrzewa i mają klucze o jeden mniej niż liczba ich dzieci.
Ciekawe fakty na temat drzew B:
- Minimalna wysokość drzewa B, które może istnieć z n liczbą węzłów, a m jest maksymalną liczbą dzieci, jakie może mieć węzeł, wynosi:
- Maksymalna wysokość drzewa B, które może istnieć z n liczbą węzłów, a t jest minimalną liczbą dzieci, jaką może mieć węzeł inny niż główny, wynosi:
I
Przechodzenie w drzewie B:
Przechodzenie jest również podobne do przechodzenia Inorder w drzewie binarnym. Zaczynamy od lewego dziecka, rekurencyjnie drukujemy skrajne lewe dziecko, a następnie powtarzamy ten sam proces dla pozostałych dzieci i kluczy. Na koniec rekurencyjnie wydrukuj najbardziej prawe dziecko.
Operacja wyszukiwania w B-Tree:
Wyszukiwanie jest podobne do wyszukiwania w drzewie wyszukiwania binarnego. Niech poszukiwanym kluczem będzie k.
- Zacznij od korzenia i rekurencyjnie przechodź w dół.
- Dla każdego odwiedzonego węzła innego niż liść
- Jeśli węzeł ma klucz, po prostu zwracamy węzeł.
- W przeciwnym razie wracamy do odpowiedniego dziecka (dziecka, które znajduje się tuż przed pierwszym większym kluczem) węzła.
- Jeśli dotrzemy do węzła liścia i nie znajdziemy k w węźle liścia, zwróć NULL.
Przeszukiwanie drzewa B jest podobne do przeszukiwania drzewa binarnego. Algorytm jest podobny i działa z rekurencją. Na każdym poziomie wyszukiwanie jest optymalizowane tak, jakby wartość klucza nie występowała w zakresie rodzica, to klucz znajdował się w innej gałęzi. Ponieważ wartości te ograniczają wyszukiwanie, są one również nazywane wartościami ograniczającymi lub wartościami separacji. Jeśli dotrzemy do węzła liścia i nie znajdziemy żądanego klucza, wyświetli się NULL.
Algorytm wyszukiwania elementu w drzewie B: -
C++
struct> Node {> >int> n;> >int> key[MAX_KEYS];> >Node* child[MAX_CHILDREN];> >bool> leaf;> };> Node* BtreeSearch(Node* x,>int> k) {> >int> i = 0;> >while> (i n && k>x->klawisz[i]) {> >i++;> >}> >if> (i n && k == x->klawisz[i]) {> >return> x;> >}> >if> (x->liść) {> >return> nullptr;> >}> >return> BtreeSearch(x->dziecko[i], k);> }> |
>
>
C
BtreeSearch(x, k)> >i = 1> > >// n[x] means number of keys in x node> >while> i ? n[x] and k ? keyi[x]> >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)> |
>
>
Jawa
class> Node {> >int> n;> >int>[] key =>new> int>[MAX_KEYS];> >Node[] child =>new> Node[MAX_CHILDREN];> >boolean> leaf;> }> Node BtreeSearch(Node x,>int> k) {> >int> i =>0>;> >while> (i = x.key[i]) {> >i++;> >}> >if> (i return x; } if (x.leaf) { return null; } return BtreeSearch(x.child[i], k); }> |
>
>
Python3
class> Node:> >def> __init__(>self>):> >self>.n>=> 0> >self>.key>=> [>0>]>*> MAX_KEYS> >self>.child>=> [>None>]>*> MAX_CHILDREN> >self>.leaf>=> True> def> BtreeSearch(x, k):> >i>=> 0> >while> i and k>= x.key[i]: i += 1 jeśli i oraz k == x.key[i]: return x jeśli x.leaf: return Brak return BtreeSearch(x.child[i], k)> |
>
>
C#
class> Node {> >public> int> n;> >public> int>[] key =>new> int>[MAX_KEYS];> >public> Node[] child =>new> Node[MAX_CHILDREN];> >public> bool> leaf;> }> Node BtreeSearch(Node x,>int> k) {> >int> i = 0;> >while> (i = x.key[i]) {> >i++;> >}> >if> (i return x; } if (x.leaf) { return null; } return BtreeSearch(x.child[i], k); }> |
>
>
JavaScript
// Define a Node class with properties n, key, child, and leaf> class Node {> >constructor() {> >this>.n = 0;> >this>.key =>new> Array(MAX_KEYS);> >this>.child =>new> Array(MAX_CHILDREN);> >this>.leaf =>false>;> >}> }> // Define a function BtreeSearch that takes in a Node object x and an integer k> function> BtreeSearch(x, k) {> >let i = 0;> >while> (i = x.key[i]) {> >i++;> >}> >if> (i return x; } if (x.leaf) { return null; } return BtreeSearch(x.child[i], k); }> |
>
>
Przykłady:
polecenie zip w systemie Linux
Wejście: Wyszukaj 120 w danym drzewie B.
Rozwiązanie:
tablica bajtów na ciąg Java
W tym przykładzie widzimy, że nasze wyszukiwanie zostało ograniczone poprzez ograniczenie szans na obecność klucza zawierającego wartość. Podobnie, jeśli w powyższym przykładzie będziemy musieli szukać 180, kontrola zatrzyma się w kroku 2, ponieważ program stwierdzi, że klucz 180 jest obecny w bieżącym węźle. I podobnie, jeśli ma wyszukać 90, to jako 90 <100, więc automatycznie przejdzie do lewego poddrzewa, a zatem przepływ sterowania będzie przebiegał podobnie jak pokazano w powyższym przykładzie.
Poniżej implementacja powyższego podejścia:
C++
// C++ implementation of search() and traverse() methods> #include> using> namespace> std;> // A BTree node> class> BTreeNode {> >int>* keys;>// An array of keys> >int> t;>// Minimum degree (defines the range for number> >// of keys)> >BTreeNode** C;>// An array of child pointers> >int> n;>// Current number of keys> >bool> leaf;>// Is true when node is leaf. Otherwise false> public>:> >BTreeNode(>int> _t,>bool> _leaf);>// Constructor> >// A function to traverse all nodes in a subtree rooted> >// with this node> >void> traverse();> >// A function to search a key in the subtree rooted with> >// this node.> >BTreeNode*> >search(>int> k);>// returns NULL if k is not present.> >// Make the BTree friend of this so that we can access> >// private members of this class in BTree functions> >friend> class> BTree;> };> // A BTree> class> BTree {> >BTreeNode* root;>// Pointer to root node> >int> t;>// Minimum degree> public>:> >// Constructor (Initializes tree as empty)> >BTree(>int> _t)> >{> >root = NULL;> >t = _t;> >}> >// function to traverse the tree> >void> traverse()> >{> >if> (root != NULL)> >root->przemierzać();> >}> >// function to search a key in this tree> >BTreeNode* search(>int> k)> >{> >return> (root == NULL) ? NULL : root->szukaj(k);> >}> };> // Constructor for BTreeNode class> BTreeNode::BTreeNode(>int> _t,>bool> _leaf)> {> >// Copy the given minimum degree and leaf property> >t = _t;> >leaf = _leaf;> >// Allocate memory for maximum number of possible keys> >// and child pointers> >keys =>new> int>[2 * t - 1];> >C =>new> BTreeNode*[2 * t];> >// Initialize the number of keys as 0> >n = 0;> }> // Function to traverse all nodes in a subtree rooted with> // this node> void> BTreeNode::traverse()> {> >// There are n keys and n+1 children, traverse through n> >// keys and first n children> >int> i;> >for> (i = 0; i // If this is not leaf, then before printing key[i], // traverse the subtree rooted with child C[i]. if (leaf == false) C[i]->trawers(); cout<< ' ' << keys[i]; } // Print the subtree rooted with last child if (leaf == false) C[i]->trawers(); } // Funkcja przeszukująca klucz k w poddrzewie zakorzenionym w tym węźle BTreeNode* BTreeNode::search(int k) { // Znajdź pierwszy klucz większy lub równy k int i = 0; podczas gdy (i klawisze [i]) i++; // Jeśli znaleziony klucz jest równy k, zwróć ten węzeł if (keys[i] == k) zwróć to; // Jeśli nie znaleziono tutaj klucza i jest to węzeł liścia if (leaf == true) return NULL; // Przejdź do odpowiedniego dziecka return C[i]->search(k); }> |
>
>
Jawa
// Java program to illustrate the sum of two numbers> // A BTree> class> Btree {> >public> BTreeNode root;>// Pointer to root node> >public> int> t;>// Minimum degree> >// Constructor (Initializes tree as empty)> >Btree(>int> t)> >{> >this>.root =>null>;> >this>.t = t;> >}> >// function to traverse the tree> >public> void> traverse()> >{> >if> (>this>.root !=>null>)> >this>.root.traverse();> >System.out.println();> >}> >// function to search a key in this tree> >public> BTreeNode search(>int> k)> >{> >if> (>this>.root ==>null>)> >return> null>;> >else> >return> this>.root.search(k);> >}> }> // A BTree node> class> BTreeNode {> >int>[] keys;>// An array of keys> >int> t;>// Minimum degree (defines the range for number> >// of keys)> >BTreeNode[] C;>// An array of child pointers> >int> n;>// Current number of keys> >boolean> >leaf;>// Is true when node is leaf. Otherwise false> >// Constructor> >BTreeNode(>int> t,>boolean> leaf)> >{> >this>.t = t;> >this>.leaf = leaf;> >this>.keys =>new> int>[>2> * t ->1>];> >this>.C =>new> BTreeNode[>2> * t];> >this>.n =>0>;> >}> >// A function to traverse all nodes in a subtree rooted> >// with this node> >public> void> traverse()> >{> >// There are n keys and n+1 children, traverse> >// through n keys and first n children> >int> i =>0>;> >for> (i =>0>; i <>this>.n; i++) {> >// If this is not leaf, then before printing> >// key[i], traverse the subtree rooted with> >// child C[i].> >if> (>this>.leaf ==>false>) {> >C[i].traverse();> >}> >System.out.print(keys[i] +>' '>);> >}> >// Print the subtree rooted with last child> >if> (leaf ==>false>)> >C[i].traverse();> >}> >// A function to search a key in the subtree rooted with> >// this node.> >BTreeNode search(>int> k)> >{>// returns NULL if k is not present.> >// Find the first key greater than or equal to k> >int> i =>0>;> >while> (i keys[i])> >i++;> >// If the found key is equal to k, return this node> >if> (keys[i] == k)> >return> this>;> >// If the key is not found here and this is a leaf> >// node> >if> (leaf ==>true>)> >return> null>;> >// Go to the appropriate child> >return> C[i].search(k);> >}> }> |
>
>
Python3
# Create a node> class> BTreeNode:> >def> __init__(>self>, leaf>=>False>):> >self>.leaf>=> leaf> >self>.keys>=> []> >self>.child>=> []> # Tree> class> BTree:> >def> __init__(>self>, t):> >self>.root>=> BTreeNode(>True>)> >self>.t>=> t> ># Insert node> >def> insert(>self>, k):> >root>=> self>.root> >if> len>(root.keys)>=>=> (>2> *> self>.t)>-> 1>:> >temp>=> BTreeNode()> >self>.root>=> temp> >temp.child.insert(>0>, root)> >self>.split_child(temp,>0>)> >self>.insert_non_full(temp, k)> >else>:> >self>.insert_non_full(root, k)> ># Insert nonfull> >def> insert_non_full(>self>, x, k):> >i>=> len>(x.keys)>-> 1> >if> x.leaf:> >x.keys.append((>None>,>None>))> >while> i>>=> 0> and> k[>0>] 0]: x.keys[i + 1] = x.keys[i] i -= 1 x.keys[i + 1] = k else: while i>= 0 i k[0] 0]: i -= 1 i += 1 if len(x.child[i].keys) == (2 * self.t) - 1: self.split_child(x, i) if k[0]> x.keys[i][0]: i += 1 self.insert_non_full(x.child[i], k) # Podziel dziecko def split_child(self, x, i): t = self .t y = x.child[i] z = BTreeNode(y.leaf) x.child.insert(i + 1, z) x.keys.insert(i, y.keys[t - 1]) z.keys = y.keys[t: (2 * t) - 1] y.keys = y.keys[0: t - 1] jeśli nie y.leaf: z.child = y.child[t: 2 * t] y. child = y.child[0: t - 1] # Wydrukuj drzewo def print_tree(self, x, l=0): print('Poziom ', l, ' ', len(x.keys), end=':') dla i w x.keys: print(i, end=' ') print() l += 1 if len(x.child)> 0: dla i w x.child: self.print_tree(i, l) # Klucz wyszukiwania w drzewie def search_key(self, k, x=None): jeśli x nie jest Brak: i = 0 podczas gdy i |
>
>
C#
// C# program to illustrate the sum of two numbers> using> System;> // A BTree> class> Btree {> >public> BTreeNode root;>// Pointer to root node> >public> int> t;>// Minimum degree> >// Constructor (Initializes tree as empty)> >Btree(>int> t)> >{> >this>.root =>null>;> >this>.t = t;> >}> >// function to traverse the tree> >public> void> traverse()> >{> >if> (>this>.root !=>null>)> >this>.root.traverse();> >Console.WriteLine();> >}> >// function to search a key in this tree> >public> BTreeNode search(>int> k)> >{> >if> (>this>.root ==>null>)> >return> null>;> >else> >return> this>.root.search(k);> >}> }> // A BTree node> class> BTreeNode {> >int>[] keys;>// An array of keys> >int> t;>// Minimum degree (defines the range for number> >// of keys)> >BTreeNode[] C;>// An array of child pointers> >int> n;>// Current number of keys> >bool> leaf;>// Is true when node is leaf. Otherwise false> >// Constructor> >BTreeNode(>int> t,>bool> leaf)> >{> >this>.t = t;> >this>.leaf = leaf;> >this>.keys =>new> int>[2 * t - 1];> >this>.C =>new> BTreeNode[2 * t];> >this>.n = 0;> >}> >// A function to traverse all nodes in a subtree rooted> >// with this node> >public> void> traverse()> >{> >// There are n keys and n+1 children, traverse> >// through n keys and first n children> >int> i = 0;> >for> (i = 0; i <>this>.n; i++) {> >// If this is not leaf, then before printing> >// key[i], traverse the subtree rooted with> >// child C[i].> >if> (>this>.leaf ==>false>) {> >C[i].traverse();> >}> >Console.Write(keys[i] +>' '>);> >}> >// Print the subtree rooted with last child> >if> (leaf ==>false>)> >C[i].traverse();> >}> >// A function to search a key in the subtree rooted with> >// this node.> >public> BTreeNode search(>int> k)> >{>// returns NULL if k is not present.> >// Find the first key greater than or equal to k> >int> i = 0;> >while> (i keys[i])> >i++;> >// If the found key is equal to k, return this node> >if> (keys[i] == k)> >return> this>;> >// If the key is not found here and this is a leaf> >// node> >if> (leaf ==>true>)> >return> null>;> >// Go to the appropriate child> >return> C[i].search(k);> >}> }> // This code is contributed by Rajput-Ji> |
>
>
JavaScript
// Javascript program to illustrate the sum of two numbers> // A BTree> class Btree> {> >// Constructor (Initializes tree as empty)> >constructor(t)> >{> >this>.root =>null>;> >this>.t = t;> >}> > >// function to traverse the tree> >traverse()> >{> >if> (>this>.root !=>null>)> >this>.root.traverse();> >document.write(>' '>);> >}> > >// function to search a key in this tree> >search(k)> >{> >if> (>this>.root ==>null>)> >return> null>;> >else> >return> this>.root.search(k);> >}> > }> // A BTree node> class BTreeNode> {> >// Constructor> >constructor(t,leaf)> >{> >this>.t = t;> >this>.leaf = leaf;> >this>.keys =>new> Array(2 * t - 1);> >this>.C =>new> Array(2 * t);> >this>.n = 0;> >}> >// A function to traverse all nodes in a subtree rooted with this node> >traverse()> >{> >// There are n keys and n+1 children, traverse through n keys> >// and first n children> >let i = 0;> >for> (i = 0; i <>this>.n; i++) {> > >// If this is not leaf, then before printing key[i],> >// traverse the subtree rooted with child C[i].> >if> (>this>.leaf ==>false>) {> >C[i].traverse();> >}> >document.write(keys[i] +>' '>);> >}> > >// Print the subtree rooted with last child> >if> (leaf ==>false>)> >C[i].traverse();> >}> > >// A function to search a key in the subtree rooted with this node.> >search(k)>// returns NULL if k is not present.> >{> > >// Find the first key greater than or equal to k> >let i = 0;> >while> (i keys[i])> >i++;> > >// If the found key is equal to k, return this node> >if> (keys[i] == k)> >return> this>;> > >// If the key is not found here and this is a leaf node> >if> (leaf ==>true>)> >return> null>;> > >// Go to the appropriate child> >return> C[i].search(k);> >}> }> // This code is contributed by patel2127> |
>
>
Notatka: Powyższy kod nie zawiera programu sterownika. Cały program omówimy w następnym poście na temat Wstawienie drzewa B .
Istnieją dwie konwencje definiowania drzewa B, jedna polega na określeniu minimalnego stopnia, druga polega na zdefiniowaniu kolejności. Przestrzegaliśmy konwencji dotyczącej minimalnego stopnia naukowego i będziemy się nią kierować w kolejnych postach na B-Tree. Nazwy zmiennych użyte w powyższym programie również pozostają takie same
polecenie linii AutoCAD
Zastosowania drzew B:
- Stosowany jest w dużych bazach danych w celu uzyskania dostępu do danych przechowywanych na dysku
- Wyszukiwanie danych w zbiorze danych można osiągnąć w znacznie krótszym czasie przy użyciu B-Tree
- Dzięki funkcji indeksowania można osiągnąć indeksowanie wielopoziomowe.
- Większość serwerów również korzysta z podejścia B-tree.
- B-Drzewa są używane w systemach CAD do organizowania i wyszukiwania danych geometrycznych.
- Drzewa B są również wykorzystywane w innych obszarach, takich jak przetwarzanie języka naturalnego, sieci komputerowe i kryptografia.
Zalety drzew B:
- Drzewa B mają gwarantowaną złożoność czasową O(log n) dla podstawowych operacji, takich jak wstawianie, usuwanie i wyszukiwanie, co czyni je odpowiednimi dla dużych zbiorów danych i aplikacji czasu rzeczywistego.
- B-Drzewa są samobalansujące.
- Wysoka współbieżność i wysoka przepustowość.
- Efektywne wykorzystanie pamięci.
Wady drzew B:
- B-Drzewa opierają się na dyskowych strukturach danych i mogą powodować duże wykorzystanie dysku.
- Nie jest to najlepsze rozwiązanie we wszystkich przypadkach.
- Powolny w porównaniu do innych struktur danych.
Wstawianie i usuwanie:
Wstawienie drzewa B
Usuwanie drzewa B