logo

TechCodeview

Introducerea B-Tree

Limitările arborilor tradiționali de căutare binare pot fi frustrante. Faceți cunoștință cu B-Tree, structura de date multi-talentată care poate gestiona cu ușurință cantități masive de date. Când vine vorba de stocarea și căutarea unor cantități mari de date, arborii tradiționali de căutare binare pot deveni nepractici din cauza performanței lor slabe și a utilizării mari a memoriei. B-Trees, cunoscuți și sub denumirea de B-Tree sau Balanced Tree, sunt un tip de arbore de auto-echilibrare care a fost conceput special pentru a depăși aceste limitări.

Spre deosebire de arborii de căutare binari tradiționali, B-Trees se caracterizează prin numărul mare de chei pe care le pot stoca într-un singur nod, motiv pentru care sunt cunoscuți și ca arbori chei mari. Fiecare nod dintr-un B-Tree poate conține mai multe chei, ceea ce permite arborelui să aibă un factor de ramificare mai mare și astfel o înălțime mai mică. Această înălțime mică duce la mai puține I/O pe disc, ceea ce duce la operațiuni de căutare și inserare mai rapide. B-Trees sunt deosebit de potrivite pentru sistemele de stocare care au acces lent la date voluminoase, cum ar fi hard disk-uri, memorie flash și CD-ROM-uri.



B-Trees menține echilibrul asigurându-se că fiecare nod are un număr minim de chei, astfel încât arborele este întotdeauna echilibrat. Acest echilibru garantează că complexitatea timpului pentru operațiuni precum inserarea, ștergerea și căutarea este întotdeauna O(log n), indiferent de forma inițială a arborelui.

Complexitatea timpului B-Tree:

domnule nr.AlgoritmComplexitatea timpului
1.CăutareO(log n)
2.IntroduceO(log n)
3.ȘtergeO(log n)


Notă: n este numărul total de elemente din arborele B

arhitectura java

Proprietățile B-Tree:

  • Toate frunzele sunt la același nivel.
  • B-Tree este definit de termenul de grad minim „ t ‘. Valoarea a ' t „ depinde de dimensiunea blocului de disc.
  • Fiecare nod, cu excepția rădăcinii, trebuie să conțină cel puțin t-1 chei. Rădăcina poate conține un minim de 1 cheie.
  • Toate nodurile (inclusiv rădăcina) pot conține cel mult ( 2*t – 1 ) cheile.
  • Numărul de copii ai unui nod este egal cu numărul de chei din el plus 1 .
  • Toate cheile unui nod sunt sortate în ordine crescătoare. Copilul dintre două chei k1 și k2 conține toate cheile din intervalul de la k1 și k2 .
  • B-Tree crește și se micșorează de la rădăcină, care este spre deosebire de Binary Search Tree. Arborii binari de căutare cresc în jos și, de asemenea, se micșorează din jos.
  • Ca și alți arbori de căutare binari echilibrați, complexitatea timpului de căutare, inserare și ștergere este O(log n).
  • Inserarea unui Nod în B-Tree are loc numai la Leaf Node.


Urmează un exemplu de arbore B de ordin minim 5
Notă: că în B-Trees practic, valoarea comenzii minime este mult mai mare de 5.




Putem vedea în diagrama de mai sus că toate nodurile frunze sunt la același nivel și toate non-frunzele nu au un subarboresc gol și au cheile cu una mai puțin decât numărul copiilor lor.

Fapte interesante despre B-Trees:

  • Înălțimea minimă a arborelui B care poate exista cu n număr de noduri și m este numărul maxim de copii pe care îl poate avea un nod este: h_{min} =lceillog_m (n + 1) ceil - 1
  • Înălțimea maximă a arborelui B care poate exista cu n număr de noduri și t este numărul minim de copii pe care un nod non-rădăcină îl poate avea este: h_{max} =lfloorlog_tfrac {n + 1}{2} floorși t = lceilfrac {m}{2} ceil

Traversare în B-Tree:

Traversal este, de asemenea, similar cu traversarea în ordine a arborelui binar. Începem de la copilul din stânga, imprimăm recursiv copilul din stânga, apoi repetăm ​​același proces pentru copiii și cheile rămase. În cele din urmă, imprimați recursiv copilul cel mai din dreapta.



diferența dintre firmă și companie

Operațiune de căutare în B-Tree:

Căutarea este similară cu căutarea în Arborele de căutare binar. Fie cheia de căutat este k.

  • Începeți de la rădăcină și traversați recursiv în jos.
  • Pentru fiecare nod non-frunză vizitat,
    • Dacă nodul are cheia, pur și simplu returnăm nodul.
    • În caz contrar, revenim la copilul corespunzător (copilul care se află chiar înaintea primei chei mai mari) al nodului.
  • Dacă ajungem la un nod frunză și nu găsim k în nodul frunză, atunci returnăm NULL.

Căutarea unui B-Tree este similară cu căutarea unui arbore binar. Algoritmul este similar și merge cu recursivitate. La fiecare nivel, căutarea este optimizată ca și cum valoarea cheii nu este prezentă în intervalul părintelui, atunci cheia este prezentă într-o altă ramură. Deoarece aceste valori limitează căutarea, ele sunt cunoscute și ca valori limită sau valori de separare. Dacă ajungem la un nod frunză și nu găsim cheia dorită, atunci va afișa NULL.

Algoritm pentru căutarea unui element într-un arbore 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->tasta[i]) {> >i++;> >}> >if> (i n && k == x->cheie[i]) {> >return> x;> >}> >if> (x->frunză) {> >return> nullptr;> >}> >return> BtreeSearch(x->copil[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 dacă i și k == x.key[i]: returnează x dacă 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); }>
>
>

Exemple:

Intrare: Căutați 120 în arborele B dat.



Soluţie:

amisha patel



În acest exemplu, putem vedea că căutarea noastră a fost redusă doar prin limitarea șanselor în care cheia care conține valoarea ar putea fi prezentă. În mod similar, dacă în exemplul de mai sus trebuie să căutăm 180, atunci controlul se va opri la pasul 2, deoarece programul va găsi că cheia 180 este prezentă în nodul curent. Și, în mod similar, dacă este să căutați 90, atunci ca 90 <100, astfel încât va merge automat în subarborele din stânga și, prin urmare, fluxul de control va merge în mod similar așa cum se arată în exemplul de mai sus.

bharti jha

Mai jos este implementarea abordării de mai sus:

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->traversează();> >}> >// function to search a key in this tree> >BTreeNode* search(>int> k)> >{> >return> (root == NULL) ? NULL : root->caută(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]->traversa(); cout<< ' ' << keys[i]; } // Print the subtree rooted with last child if (leaf == false) C[i]->traversa(); } // Funcție de căutare a tastei k în subarborele înrădăcinat cu acest nod BTreeNode* BTreeNode::search(int k) { // Găsiți prima cheie mai mare sau egală cu k int i = 0; în timp ce (i taste[i]) i++; // Dacă cheia găsită este egală cu k, returnează acest nod dacă (keys[i] == k) returnează acest; // Dacă cheia nu este găsită aici și acesta este un nod frunză dacă (frunză == adevărat) returnează NULL; // Accesați copilul corespunzător return C[i]->search(k); }>>>
>                      
 // 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 dacă 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) # Split the child def split_child(self, x, i): t = self .t y = x.copil[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] dacă nu y.leaf: z.child = y.child[t: 2 * t] y. copil = y.copil[0: t - 1] # Tipăriți arborele def print_tree(self, x, l=0): print('Level ', l, ' ', len(x.keys), end=':') pentru i în x.keys: print(i, end=' ') print() l += 1 dacă len(x.child)> 0: pentru i în x.child: self.print_tree(i, l) # Cheie de căutare în arbore def search_key(self, k, x=None): dacă x nu este None: i = 0 în timp ce ix.keys[i][0]: i += 1 dacă 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> 
    
>
    
>
 
  
    Notă:    Codul de mai sus nu conține programul de driver. Vom acoperi programul complet în următoarea noastră postare despre B-Tree Insertion .
 
Există două convenții pentru a defini un B-Tree, una este de a defini prin grad minim, a doua este de a defini prin ordine. Am respectat convenția de grad minim și vom urma aceeași în postările viitoare pe B-Tree. Numele variabilelor utilizate în programul de mai sus sunt, de asemenea, păstrate la fel
 
    Aplicații ale B-Trees:    
  • Este folosit în bazele de date mari pentru a accesa datele stocate pe disc
  • Căutarea datelor într-un set de date poate fi realizată într-un timp semnificativ mai mic folosind B-Tree
  • Cu funcția de indexare, se poate realiza indexarea pe mai multe niveluri.
  • Majoritatea serverelor folosesc, de asemenea, abordarea B-tree.
  • B-Trees sunt utilizați în sistemele CAD pentru a organiza și căuta date geometrice.
  • B-Trees sunt, de asemenea, utilizați în alte domenii, cum ar fi procesarea limbajului natural, rețelele de computere și criptografia.
    Avantajele B-Trees:    
  • B-Trees au o complexitate de timp garantată de O(log n) pentru operațiuni de bază precum inserarea, ștergerea și căutarea, ceea ce le face potrivite pentru seturi mari de date și aplicații în timp real.
  • B-Trees se auto-echilibrează.
  • Concurență ridicată și debit mare.
  • Utilizarea eficientă a stocării.
    Dezavantajele arborilor B:    
  • B-Trees se bazează pe structuri de date bazate pe disc și pot avea o utilizare mare a discului.
  • Nu este cel mai bun pentru toate cazurile.
  • Încet în comparație cu alte structuri de date.
Inserare și ștergere:  
 B-Tree Insertion    
 B-Tree Deletion