Begränsningarna för traditionella binära sökträd kan vara frustrerande. Möt B-Tree, den mångbegåvade datastrukturen som kan hantera enorma mängder data med lätthet. När det gäller att lagra och söka i stora mängder data kan traditionella binära sökträd bli opraktiska på grund av deras dåliga prestanda och höga minnesanvändning. B-Trees, även känd som B-Tree eller Balanced Tree, är en typ av självbalanserande träd som designades speciellt för att övervinna dessa begränsningar.
Till skillnad från traditionella binära sökträd kännetecknas B-Trees av det stora antalet nycklar som de kan lagra i en enda nod, varför de också är kända som stora nyckelträd. Varje nod i ett B-träd kan innehålla flera nycklar, vilket gör att trädet får en större förgreningsfaktor och därmed en grundare höjd. Denna grunda höjd leder till mindre disk I/O, vilket resulterar i snabbare sökning och insättningsoperationer. B-Trees är särskilt väl lämpade för lagringssystem som har långsam, skrymmande dataåtkomst som hårddiskar, flashminne och CD-ROM-skivor.
B-Trees upprätthåller balansen genom att se till att varje nod har ett minsta antal nycklar, så att trädet alltid är balanserat. Denna balans garanterar att tidskomplexiteten för operationer som infogning, radering och sökning alltid är O(log n), oavsett trädets initiala form.
Tidskomplexitet för B-Tree:
| Mr. Nej. | Algoritm | Tidskomplexitet |
|---|---|---|
| 1. | Sök | O(log n) |
| 2. | Föra in | O(log n) |
| 3. | Radera | O(log n) |
Notera: n är det totala antalet element i B-trädet
år in i kvartalen
Egenskaper för B-Tree:
- Alla blad är på samma nivå.
- B-Tree definieras av termen minimigrad ' t ’. Värdet av ' t ’ beror på diskblockets storlek.
- Varje nod utom roten måste innehålla minst t-1 nycklar. Roten kan innehålla ett minimum av 1 nyckel.
- Alla noder (inklusive rot) kan innehålla högst ( 2*t – 1 ) nycklar.
- Antalet barn till en nod är lika med antalet nycklar i den plus 1 .
- Alla nycklar i en nod sorteras i ökande ordning. Barnet mellan två nycklar k1 och k2 innehåller alla nycklar i intervallet från k1 och k2 .
- B-Tree växer och krymper från roten vilket är till skillnad från Binary Search Tree. Binära sökträd växer nedåt och krymper också nedåt.
- Liksom andra balanserade binära sökträd är tidskomplexiteten att söka, infoga och radera O(log n).
- Infogning av en Nod i B-Tree sker endast vid Leaf Node.
Följande är ett exempel på ett B-träd med minsta order 5
Notera: att i praktiska B-Trees är värdet på minimibeställningen mycket mer än 5.
Vi kan se i diagrammet ovan att alla lövnoder är på samma nivå och alla icke-löv har inget tomt underträd och har nycklar en mindre än antalet barn.
Intressanta fakta om B-Trees:
- Den minsta höjden på B-trädet som kan existera med n antal noder och m är det maximala antalet barn till en nod kan ha är:
- Den maximala höjden på B-trädet som kan existera med n antal noder och t är det minsta antalet barn som en icke-rotnod kan ha är:
och
Traversering i B-Tree:
Traversal liknar också Inorder-traversal av binärt träd. Vi utgår från barnet längst till vänster, skriver rekursivt ut barnet längst till vänster och upprepar sedan samma process för de återstående barnen och nycklarna. I slutändan, skriv rekursivt ut barnet längst till höger.
Sökoperation i B-Tree:
Sökningen liknar sökningen i Binary Search Tree. Låt nyckeln som ska sökas är k.
- Börja från roten och gå rekursivt nedåt.
- För varje besökt nod som inte är löv,
- Om noden har nyckeln returnerar vi helt enkelt noden.
- Annars återkommer vi ner till lämpligt barn (Barnet som är precis före den första större nyckeln) i noden.
- Om vi når en lövnod och inte hittar k i lövnoden, returnera NULL.
Att söka i ett B-träd liknar att söka i ett binärt träd. Algoritmen är liknande och går med rekursion. På varje nivå optimeras sökningen som om nyckelvärdet inte finns inom intervallet för föräldern då nyckeln finns i en annan gren. Eftersom dessa värden begränsar sökningen kallas de även för gränsvärden eller separationsvärden. Om vi når en lövnod och inte hittar den önskade nyckeln kommer den att visa NULL.
Algoritm för att söka efter ett element i ett B-träd:-
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->nyckel[i]) {> >i++;> >}> >if> (i n && k == x->nyckel[i]) {> >return> x;> >}> >if> (x->blad) {> >return> nullptr;> >}> >return> BtreeSearch(x->barn[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)> |
>
>
Java
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 och 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); }> |
>
>
Exempel:
javatable
Inmatning: Sök 120 i det givna B-trädet.
Lösning:
if-else uttalande java
I det här exemplet kan vi se att vår sökning reducerades genom att bara begränsa chanserna där nyckeln som innehåller värdet kan vara närvarande. På liknande sätt om vi i exemplet ovan måste leta efter 180, kommer kontrollen att stanna vid steg 2 eftersom programmet kommer att finna att nyckeln 180 finns i den aktuella noden. Och på liknande sätt, om det är att söka efter 90 så som 90 <100 så kommer det att gå till vänster underträd automatiskt, och därför kommer kontrollflödet att gå på liknande sätt som visas i exemplet ovan.
Nedan är implementeringen av ovanstående tillvägagångssätt:
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->travers();> >}> >// function to search a key in this tree> >BTreeNode* search(>int> k)> >{> >return> (root == NULL) ? NULL : root->sök(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]->korsa(); cout<< ' ' << keys[i]; } // Print the subtree rooted with last child if (leaf == false) C[i]->korsa(); } // Funktion för att söka nyckel k i underträd som är rotat med denna nod BTreeNode* BTreeNode::search(int k) { // Hitta den första nyckeln större än eller lika med k int i = 0; while (i tangenter[i]) i++; // Om den hittade nyckeln är lika med k, returnera denna nod om (nycklar[i] == k) returnerar denna; // Om nyckeln inte hittas här och detta är en lövnod om (blad == sant) returnera NULL; // Gå till lämplig underordnad retur C[i]->sök(k); }> |
>
>
Java
// 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 och k[0] 0]: i -= 1 i += 1 om len(x.child[i].keys) == (2 * self.t) - 1: self.split_child(x, i) om k[0]> x.keys[i][0]: i += 1 self.insert_non_full(x.child[i], k) # Dela barnet 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] om inte y.leaf: z.child = y.child[t: 2 * t] y. child = y.child[0: t - 1] # Skriv ut trädet def print_tree(self, x, l=0): print('Nivå ', l, ' ', len(x.keys), end=':') för i i x.keys: print(i, end=' ') print() l += 1 om len(x.child)> 0: för i i x.child: self.print_tree(i, l) # Söknyckel i trädet def search_key(self, k, x=Ingen): om x inte är Ingen: i = 0 medan 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> |
>
>
Notera: Ovanstående kod innehåller inte drivrutinsprogrammet. Vi kommer att täcka hela programmet i vårt nästa inlägg B-trädinsättning .
Det finns två konventioner för att definiera ett B-träd, en är att definiera med minsta grad, den andra är att definiera genom ordning. Vi har följt minimiexamenskonventionen och kommer att följa detsamma i kommande inlägg på B-Tree. Variabelnamnen som används i programmet ovan hålls också desamma
c++ strängdelning
Tillämpningar av B-Trees:
- Den används i stora databaser för att komma åt data som lagras på disken
- Att söka efter data i en datamängd kan uppnås på betydligt kortare tid med B-Tree
- Med indexeringsfunktionen kan indexering på flera nivåer uppnås.
- De flesta av servrarna använder också B-tree-metoden.
- B-Trees används i CAD-system för att organisera och söka geometrisk data.
- B-Trees används också inom andra områden som naturlig språkbehandling, datornätverk och kryptografi.
Fördelar med B-Trees:
- B-Trees har en garanterad tidskomplexitet O(log n) för grundläggande operationer som infogning, radering och sökning, vilket gör dem lämpliga för stora datamängder och realtidsapplikationer.
- B-Trees är självbalanserande.
- Hög samtidighet och hög genomströmning.
- Effektivt lagringsutnyttjande.
Nackdelar med B-Trees:
- B-Trees är baserade på diskbaserade datastrukturer och kan ha hög diskanvändning.
- Inte det bästa för alla fall.
- Långsam i jämförelse med andra datastrukturer.
Insättning och radering:
B-trädinsättning
B-träd radering