Omezení tradičních binárních vyhledávacích stromů může být frustrující. Seznamte se s B-Stromem, multitalentovanou datovou strukturou, která snadno zvládne obrovské množství dat. Pokud jde o ukládání a vyhledávání velkého množství dat, tradiční binární vyhledávací stromy se mohou stát nepraktickými kvůli jejich nízkému výkonu a vysokému využití paměti. B-Stromy, také známé jako B-Strom nebo Balanced Tree, jsou typem samovyvažujícího stromu, který byl speciálně navržen k překonání těchto omezení.
Na rozdíl od tradičních binárních vyhledávacích stromů se B-stromy vyznačují velkým počtem klíčů, které mohou uložit do jednoho uzlu, a proto jsou také známé jako velké stromy klíčů. Každý uzel v B-stromu může obsahovat více klíčů, což umožňuje stromu mít větší faktor větvení a tím i menší výšku. Tato malá výška vede k menšímu počtu vstupů a výstupů disku, což má za následek rychlejší operace vyhledávání a vkládání. B-Stromy jsou zvláště vhodné pro úložné systémy, které mají pomalý a objemný přístup k datům, jako jsou pevné disky, flash paměti a CD-ROMy.
B-Trees udržuje rovnováhu tím, že zajišťuje, že každý uzel má minimální počet klíčů, takže strom je vždy vyvážený. Tato rovnováha zaručuje, že časová složitost operací, jako je vkládání, mazání a vyhledávání, je vždy O(log n), bez ohledu na počáteční tvar stromu.
Časová složitost B-stromu:
| pan č. | Algoritmus | Časová složitost |
|---|---|---|
| 1. | Vyhledávání | O(log n) |
| 2. | Vložit | O(log n) |
| 3. | Vymazat | O(log n) |
Poznámka: n je celkový počet prvků v B-stromu
binární vyhledávací strom vs binární strom
Vlastnosti B-stromu:
- Všechny listy jsou na stejné úrovni.
- B-Strom je definován termínem minimální stupeň „ t ‘. Hodnota ' t ‘ závisí na velikosti bloku disku.
- Každý uzel kromě kořene musí obsahovat alespoň t-1 klíčů. Kořen může obsahovat minimálně 1 klíč.
- Všechny uzly (včetně kořenového) mohou obsahovat nejvýše ( 2*t – 1 ) klíče.
- Počet potomků uzlu se rovná počtu klíčů v něm plus 1 .
- Všechny klíče uzlu jsou seřazeny ve vzestupném pořadí. Dítě mezi dvěma klíči k1 a k2 obsahuje všechny klíče v rozsahu od k1 a k2 .
- B-Strom roste a zmenšuje se z kořene, což je na rozdíl od Binary Search Tree. Binární vyhledávací stromy rostou směrem dolů a také se směrem dolů zmenšují.
- Stejně jako u jiných vyvážených binárních vyhledávacích stromů je časová složitost vyhledávání, vkládání a mazání O(log n).
- Vložení uzlu do B-stromu se děje pouze v listovém uzlu.
Následuje příklad B-stromu minimálního řádu 5
Poznámka: že v praktických B-stromech je hodnota minimální objednávky mnohem vyšší než 5.
Ve výše uvedeném diagramu můžeme vidět, že všechny listové uzly jsou na stejné úrovni a všechny nelistové nemají žádný prázdný podstrom a mají klíče o jeden méně, než je počet jejich potomků.
Zajímavá fakta o B-stromech:
- Minimální výška B-stromu, která může existovat s n počtem uzlů a m je maximální počet potomků, které může mít uzel, je:
- Maximální výška B-stromu, která může existovat s n počtem uzlů a t je minimální počet potomků, které může mít nekořenový uzel, je:
a
Průjezd v B-stromu:
Traversal je také podobný Inorder traversal Binary Tree. Začneme od nejlevějšího potomka, rekurzivně vytiskneme nejlevějšího potomka a poté opakujeme stejný postup pro zbývající děti a klíče. Nakonec rekurzivně vytiskněte dítě nejvíce vpravo.
strojový jazyk
Vyhledávací operace v B-stromu:
Vyhledávání je podobné vyhledávání ve stromu binárního vyhledávání. Nechť klíč, který se má hledat, je k.
- Začněte od kořene a rekurzivně přejděte dolů.
- Pro každý navštívený nelistový uzel
- Pokud má uzel klíč, jednoduše uzel vrátíme.
- Jinak se vrátíme dolů k příslušnému potomkovi (Dítě, které je těsně před prvním větším klíčem) uzlu.
- Pokud dosáhneme listového uzlu a nenajdeme k v listovém uzlu, vrátíme hodnotu NULL.
Hledání B-stromu je podobné jako hledání binárního stromu. Algoritmus je podobný a jde s rekurzí. Na každé úrovni je vyhledávání optimalizováno tak, že pokud hodnota klíče není přítomna v rozsahu nadřazené položky, pak je klíč přítomen v jiné větvi. Protože tyto hodnoty omezují vyhledávání, jsou také známé jako mezní hodnoty nebo separační hodnoty. Pokud dosáhneme listového uzlu a nenajdeme požadovaný klíč, zobrazí se NULL.
Algoritmus pro vyhledávání prvku v B-stromu:-
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->key[i]) {> >i++;> >}> >if> (i n && k == x->klíč[i]) {> >return> x;> >}> >if> (x->list) {> >return> nullptr;> >}> >return> BtreeSearch(x->dítě[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)> |
>
>
Jáva
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 if i a k == x.key[i]: return x if x.leaf: return None 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); }> |
>
>
Příklady:
Vstup: Hledejte 120 v daném B-stromu.
Řešení:
sql počet odlišný
V tomto příkladu můžeme vidět, že naše vyhledávání bylo omezeno pouze omezením šancí, kde by mohl být klíč obsahující hodnotu přítomen. Podobně, pokud ve výše uvedeném příkladu musíme hledat 180, pak se ovládání zastaví v kroku 2, protože program zjistí, že klíč 180 je přítomen v aktuálním uzlu. A podobně, pokud má vyhledat 90, pak jako 90 <100, takže to půjde automaticky do levého podstromu, a proto tok ovládání půjde podobně, jak je ukázáno ve výše uvedeném příkladu.
math.pow java
Níže je uvedena implementace výše uvedeného přístupu:
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->traverse();> >}> >// function to search a key in this tree> >BTreeNode* search(>int> k)> >{> >return> (root == NULL) ? NULL : root->hledat(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]->přejít(); cout<< ' ' << keys[i]; } // Print the subtree rooted with last child if (leaf == false) C[i]->přejít(); } // Funkce pro hledání klíče k v podstromu zakořeněném tímto uzlem BTreeNode* BTreeNode::search(int k) { // Najděte první klíč větší nebo roven k int i = 0; while (i klíče[i]) i++; // Pokud je nalezený klíč roven k, vrátí tento uzel if (keys[i] == k) return this; // Pokud zde klíč není nalezen a toto je listový uzel if (list == true) return NULL; // Přejít na příslušného potomka return C[i]->search(k); }> |
>
>
Jáva
// 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 a 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) # Rozdělit potomka 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] pokud ne y.list: z.child = y.child[t: 2 * t] y. child = y.child[0: t - 1] # Tisk stromu def print_tree(self, x, l=0): print('Úroveň ', 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) # Klíč hledání ve stromu def search_key(self, k, x=None): pokud x není None: i = 0 zatímco 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> |
>
>
Poznámka: Výše uvedený kód neobsahuje program ovladače. Kompletní program přineseme v příštím příspěvku Vložení B-stromu .
Existují dvě konvence pro definování B-stromu, jedna je definovat minimálním stupněm, druhá je definovat pořadím. Dodrželi jsme konvenci o minimálních stupních a budeme se řídit stejným v příštích příspěvcích na B-Stromu. Názvy proměnných použité ve výše uvedeném programu jsou také zachovány
Aplikace B-stromů:
- Používá se ve velkých databázích pro přístup k datům uloženým na disku
- Vyhledávání dat v datové sadě lze pomocí B-Stromu dosáhnout za podstatně kratší dobu
- Pomocí funkce indexování lze dosáhnout víceúrovňového indexování.
- Většina serverů také používá přístup B-tree.
- B-stromy se používají v CAD systémech k organizování a vyhledávání geometrických dat.
- B-stromy se používají také v jiných oblastech, jako je zpracování přirozeného jazyka, počítačové sítě a kryptografie.
Výhody B-stromů:
- B-stromy mají zaručenou časovou složitost O(log n) pro základní operace, jako je vkládání, mazání a vyhledávání, díky čemuž jsou vhodné pro velké soubory dat a aplikace v reálném čase.
- B-stromy jsou samovyvažující.
- Vysoká souběžnost a vysoká propustnost.
- Efektivní využití úložiště.
Nevýhody B-stromů:
- B-stromy jsou založeny na datových strukturách na disku a mohou mít vysoké využití disku.
- Ne nejlepší pro všechny případy.
- Pomalé ve srovnání s jinými datovými strukturami.
Vkládání a mazání:
Vložení B-stromu
Vymazání B-stromu