Begrensningene til tradisjonelle binære søketrær kan være frustrerende. Møt B-Tree, den multitalentfulle datastrukturen som enkelt kan håndtere enorme mengder data. Når det gjelder lagring og søk i store mengder data, kan tradisjonelle binære søketrær bli upraktiske på grunn av deres dårlige ytelse og høye minnebruk. B-Tree, også kjent som B-Tree eller Balanced Tree, er en type selvbalanserende tre som ble spesielt designet for å overvinne disse begrensningene.
I motsetning til tradisjonelle binære søketrær, kjennetegnes B-Trær av det store antallet nøkler som de kan lagre i en enkelt node, og det er derfor de også er kjent som store nøkkeltrær. Hver node i et B-tre kan inneholde flere nøkler, noe som gjør at treet kan ha en større forgreningsfaktor og dermed en grunnere høyde. Denne grunne høyden fører til mindre disk I/O, noe som resulterer i raskere søk og innsettingsoperasjoner. B-Trees er spesielt godt egnet for lagringssystemer som har langsom, voluminøs datatilgang som harddisker, flash-minne og CD-ROM-er.
B-Trees opprettholder balansen ved å sikre at hver node har et minimum antall nøkler, slik at treet alltid er balansert. Denne balansen garanterer at tidskompleksiteten for operasjoner som innsetting, sletting og søk alltid er O(log n), uavhengig av den opprinnelige formen til treet.
Tidskompleksiteten til B-tre:
| Mr. Nei. | Algoritme | Tidskompleksitet |
|---|---|---|
| 1. | Søk | O(log n) |
| 2. | Sett inn | O(log n) |
| 3. | Slett | O(log n) |
Merk: n er det totale antallet elementer i B-treet
sett inn vannmerke i word
Egenskaper til B-Tree:
- Alle bladene er på samme nivå.
- B-Tree er definert av begrepet minimumsgrad ' t ‘. Verdien av ' t ' avhenger av diskblokkstørrelsen.
- Hver node unntatt roten må inneholde minst t-1-nøkler. Roten kan inneholde minimum 1 nøkkel.
- Alle noder (inkludert rot) kan inneholde maksimalt ( 2*t – 1 ) nøkler.
- Antall barn til en node er lik antall nøkler i den pluss 1 .
- Alle nøklene til en node er sortert i økende rekkefølge. Barnet mellom to nøkler k1 og k2 inneholder alle nøkler i området fra k1 og k2 .
- B-Tree vokser og krymper fra roten som er ulikt Binary Search Tree. Binære søketrær vokser nedover og krymper også nedover.
- Som andre balanserte binære søketrær, er tidskompleksiteten for å søke, sette inn og slette O(log n).
- Innsetting av en Node i B-Tree skjer kun ved Leaf Node.
Følgende er et eksempel på et B-tre med minimum ordre 5
Merk: at i praktiske B-Trær er verdien av minimumsbestillingen mye mer enn 5.
Vi kan se i diagrammet ovenfor at alle bladnodene er på samme nivå og at alle ikke-blader ikke har noe tomt undertre og har nøkler en mindre enn antallet barn.
Interessante fakta om B-Trees:
- Minimumshøyden på B-treet som kan eksistere med n antall noder og m er det maksimale antallet barn av en node kan ha er:
- Den maksimale høyden på B-treet som kan eksistere med n antall noder og t er minimumsantallet barn som en ikke-rotnode kan ha er:
og
Traversering i B-Tree:
Traversal ligner også på Inorder-traversal av binært tre. Vi starter fra barnet lengst til venstre, skriver rekursivt ut barnet lengst til venstre, og gjentar deretter samme prosess for de resterende barna og nøklene. Til slutt, rekursivt skrive ut barnet lengst til høyre.
Søkeoperasjon i B-Tree:
Søk ligner på søket i Binary Search Tree. La nøkkelen som skal søkes er k.
- Start fra roten og gå rekursivt nedover.
- For hver besøkte node uten blader,
- Hvis noden har nøkkelen, returnerer vi ganske enkelt noden.
- Ellers går vi tilbake til det aktuelle barnet (barnet som er like før den første større nøkkelen) til noden.
- Hvis vi når en løvnode og ikke finner k i løvnoden, returnerer du NULL.
Å søke i et B-tre ligner på å søke i et binært tre. Algoritmen er lik og går med rekursjon. På hvert nivå er søket optimalisert som om nøkkelverdien ikke er tilstede i området til overordnet, så er nøkkelen til stede i en annen gren. Siden disse verdiene begrenser søket, er de også kjent som grenseverdier eller separasjonsverdier. Hvis vi når en bladnode og ikke finner den ønskede nøkkelen, vil den vise NULL.
Algoritme for å søke etter et element i et B-tre:-
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->tast[i]) {> >i++;> >}> >if> (i n && k == x->nøkkel[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 og 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); }> |
>
>
Eksempler:
grunnleggende selen
Inndata: Søk 120 i det gitte B-treet.
Løsning:
java tilføy streng
I dette eksemplet kan vi se at søket vårt ble redusert ved bare å begrense sjansene for at nøkkelen som inneholder verdien kan være til stede. Tilsvarende hvis vi i eksemplet ovenfor må se etter 180, vil kontrollen stoppe ved trinn 2 fordi programmet vil finne at nøkkelen 180 er til stede i den nåværende noden. Og på samme måte, hvis det er å søke opp 90, så som 90 <100, så vil det automatisk gå til venstre undertre, og derfor vil kontrollflyten gå på samme måte som vist i eksemplet ovenfor.
Nedenfor er implementeringen av tilnærmingen ovenfor:
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->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]->traverse(); cout<< ' ' << keys[i]; } // Print the subtree rooted with last child if (leaf == false) C[i]->traverse(); } // Funksjon for å søke nøkkel k i undertreet som er forankret med denne noden BTreeNode* BTreeNode::search(int k) { // Finn den første nøkkelen større enn eller lik k int i = 0; while (i tastene[i]) i++; // Hvis den funnet nøkkelen er lik k, returner denne noden hvis (nøkler[i] == k) returnerer denne; // Hvis nøkkelen ikke finnes her og dette er en bladnode hvis (blad == sant) returner NULL; // Gå til riktig underordnet 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 og k[0] 0]: i -= 1 i += 1 hvis 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) # Del barnet def split_child(selv, x, i): t = selv .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.taster[t: (2 * t) - 1] y.taster = y.taster[0: t - 1] hvis ikke y.blad: z.barn = y.barn[t: 2 * t] y. barn = y.barn[0: t - 1] # Skriv ut treet def print_tree(selv, x, l=0): print('Nivå ', l, ' ', len(x.keys), end=':') for i i x.keys: print(i, end=' ') print() l += 1 hvis len(x.child)> 0: for i i x.child: self.print_tree(i, l) # Søktast i treet def search_key(selv, k, x=Ingen): hvis x ikke er Ingen: i = 0 mens 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> |
>
>
Merk: Koden ovenfor inneholder ikke driverprogrammet. Vi vil dekke hele programmet i neste innlegg B-treinnsetting .
Det er to konvensjoner for å definere et B-tre, den ene er å definere ved minimumsgrad, den andre er å definere etter rekkefølge. Vi har fulgt minimumsgradskonvensjonen og vil følge det samme i kommende innlegg på B-Tree. Variabelnavnene som brukes i programmet ovenfor beholdes også
velg sql fra flere tabeller
Bruksområder for B-Trees:
- Den brukes i store databaser for å få tilgang til data som er lagret på disken
- Å søke etter data i et datasett kan oppnås på betydelig kortere tid ved å bruke B-Tree
- Med indekseringsfunksjonen kan indeksering på flere nivåer oppnås.
- De fleste av serverne bruker også B-tree-tilnærmingen.
- B-Trær brukes i CAD-systemer for å organisere og søke i geometriske data.
- B-Trær brukes også på andre områder som naturlig språkbehandling, datanettverk og kryptografi.
Fordeler med B-trær:
- B-Trær har en garantert tidskompleksitet på O(log n) for grunnleggende operasjoner som innsetting, sletting og søk, noe som gjør dem egnet for store datasett og sanntidsapplikasjoner.
- B-trær er selvbalanserende.
- Høy samtidighet og høy gjennomstrømning.
- Effektiv lagringsutnyttelse.
Ulemper med B-trær:
- B-Trees er basert på diskbaserte datastrukturer og kan ha høy diskbruk.
- Ikke det beste for alle tilfeller.
- Treg i forhold til andre datastrukturer.
Innsetting og sletting:
B-treinnsetting
B-tre sletting