B-drzewo

W tym samouczku dowiesz się, czym jest B-drzewo. Znajdziesz również działające przykłady operacji wyszukiwania w B-drzewie w językach C, C ++, Java i Python.

B-drzewo to specjalny typ równoważącego się drzewa wyszukiwania, w którym każdy węzeł może zawierać więcej niż jeden klucz i więcej niż dwoje dzieci. Jest to uogólniona forma binarnego drzewa wyszukiwania.

Jest również znane jako drzewo o zrównoważonej wysokości.

B-drzewo

Dlaczego B-tree?

Potrzeba B-tree pojawiła się wraz ze wzrostem zapotrzebowania na krótszy czas na dostęp do fizycznych nośników danych, takich jak dysk twardy. Dodatkowe urządzenia pamięci masowej są wolniejsze i mają większą pojemność. Istniała potrzeba takich struktur danych, które minimalizują dostęp do dysku.

Inne struktury danych, takie jak drzewo wyszukiwania binarnego, drzewo AVL, drzewo czerwono-czarne itp., Mogą przechowywać tylko jeden klucz w jednym węźle. Jeśli musisz przechowywać dużą liczbę kluczy, wysokość takich drzew staje się bardzo duża, a czas dostępu wydłuża się.

Jednak B-drzewo może przechowywać wiele kluczy w jednym węźle i może mieć wiele węzłów podrzędnych. Zmniejsza to znacznie wysokość, umożliwiając szybszy dostęp do dysku.

Właściwości B-drzewa

  1. Dla każdego węzła x klucze są przechowywane w kolejności rosnącej.
  2. W każdym węźle znajduje się wartość logiczna x.leaf, która jest prawdą, jeśli x jest liściem.
  3. Jeśli n jest porządkiem w drzewie, każdy węzeł wewnętrzny może zawierać najwyżej n - 1 kluczy wraz ze wskaźnikiem do każdego dziecka.
  4. Każdy węzeł poza korzeniem może mieć co najwyżej n dzieci i co najmniej n / 2 dzieci.
  5. Wszystkie liście mają tę samą głębokość (tj. Wysokość-h drzewa).
  6. Korzeń ma co najmniej 2 dzieci i zawiera co najmniej 1 klucz.
  7. Jeśli n ≧ 1, po czym dla dowolnego n drzewa b klucz o wysokości h i minimalnym stopniu t ≧ 2, .h ≧ logt (n+1)/2

Operacje

Badawczy

Wyszukiwanie elementu w B-drzewie jest uogólnioną formą wyszukiwania elementu w Binarnym drzewie wyszukiwania. Następujące kroki są przestrzegane.

  1. Zaczynając od węzła głównego, porównaj k z pierwszym kluczem węzła.
    Jeśli k = the first key of the nodezwróć węzeł i indeks.
  2. Jeśli k.leaf = true, zwraca NULL (tj. Nie znaleziono).
  3. Jeśli k < the first key of the root node, przeszukaj lewe dziecko tego klucza rekurencyjnie.
  4. Jeśli w bieżącym węźle jest więcej niż jeden klucz i k> the first keyporównaj k z następnym kluczem w węźle.
    Jeśli k < next keyprzeszukaj lewe dziecko tego klucza (np. K leży pomiędzy pierwszym a drugim klawiszem).
    W przeciwnym razie wyszukaj właściwe dziecko klucza.
  5. Powtarzaj kroki od 1 do 4, aż do skrzydła.

Przykład wyszukiwania

  1. Poszukajmy klucza k = 17w drzewie poniżej 3. B-drzewa
  2. k nie znajduje się w katalogu głównym, więc porównaj je z kluczem głównym. k nie został znaleziony w węźle głównym
  3. Ponieważ k> 11przejdź do prawego dziecka węzła głównego. Przejdź do prawego poddrzewa
  4. Porównaj k z 16. Ponieważ k> 16porównaj k z następnym klawiszem 18. Porównaj z klawiszami od lewej do prawej
  5. Ponieważ k < 18k mieści się w przedziale od 16 do 18 lat. Przeszukaj prawe dziecko w wieku 16 lat lub lewe dziecko w wieku 18 lat. K należy do przedziału od 16 do 18 lat
  6. znaleziono k. znaleziono k

Algorytm wyszukiwania elementu

 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)

Aby dowiedzieć się więcej o różnych operacjach drzewa B, odwiedź

  • Wstawienie na drzewo B.
  • Usunięcie w drzewie B.

Przykłady w Pythonie, Javie i 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"; )

Przeszukiwanie złożoności na drzewie B.

Najgorszy przypadek Złożoność czasowa: Θ(log n)

Przypadek średni Złożoność czasowa: Θ(log n)

Najlepszy przypadek Złożoność czasu: Θ(log n)

Przypadek średni Złożoność przestrzeni: Θ(n)

Najgorszy przypadek Złożoność przestrzeni: Θ(n)

Aplikacje B Tree

  • bazy danych i systemy plików
  • do przechowywania bloków danych (dodatkowe nośniki danych)
  • indeksowanie wielopoziomowe

Interesujące artykuły...