logo

TechCodeview

Introducció de B-Tree

Les limitacions dels arbres de cerca binaris tradicionals poden ser frustrants. Coneix el B-Tree, l'estructura de dades multitalent que pot gestionar grans quantitats de dades amb facilitat. Quan es tracta d'emmagatzemar i cercar grans quantitats de dades, els arbres de cerca binaris tradicionals poden arribar a ser poc pràctics a causa del seu baix rendiment i un gran ús de memòria. Els B-Trees, també coneguts com a B-Tree o Balanced Tree, són un tipus d'arbre d'autoequilibri que es va dissenyar específicament per superar aquestes limitacions.

A diferència dels arbres de cerca binaris tradicionals, els B-Trees es caracteritzen per la gran quantitat de claus que poden emmagatzemar en un sol node, per això també es coneixen com a grans arbres de claus. Cada node d'un arbre B pot contenir diverses claus, cosa que permet que l'arbre tingui un factor de ramificació més gran i, per tant, una alçada menor. Aquesta poca alçada condueix a menys E/S de disc, el que resulta en operacions de cerca i inserció més ràpides. Els B-Trees són especialment adequats per a sistemes d'emmagatzematge que tenen accés a dades lent i voluminós, com ara discs durs, memòria flaix i CD-ROM.



B-Trees manté l'equilibri assegurant-se que cada node té un nombre mínim de claus, de manera que l'arbre sempre està equilibrat. Aquest equilibri garanteix que la complexitat del temps per a operacions com ara la inserció, la supressió i la cerca sigui sempre O(log n), independentment de la forma inicial de l'arbre.

Complexitat temporal de l'arbre B:

Sr. No.AlgoritmeComplexitat temporal
1.CercaO(log n)
2.InsereixO(log n)
3.SuprimeixO(log n)


Nota: n és el nombre total d'elements de l'arbre B

codi de mostra c#

Propietats de B-Tree:

  • Totes les fulles estan al mateix nivell.
  • B-Tree es defineix pel terme grau mínim ' t ‘. El valor de ' t ' depèn de la mida del bloc de disc.
  • Cada node, excepte l'arrel, ha de contenir almenys t-1 claus. L'arrel pot contenir un mínim de 1 clau.
  • Tots els nodes (inclòs l'arrel) poden contenir com a màxim ( 2*t – 1 ) claus.
  • El nombre de fills d'un node és igual al nombre de claus més 1 .
  • Totes les claus d'un node s'ordenen en ordre creixent. El nen entre dues claus k1 i k2 conté totes les claus del rang de k1 i k2 .
  • B-Tree creix i es redueix des de l'arrel, que és a diferència de Binary Search Tree. Els arbres de cerca binaris creixen cap avall i també es redueixen de cap avall.
  • Com altres arbres de cerca binaris equilibrats, la complexitat de temps per cercar, inserir i eliminar és O(log n).
  • La inserció d'un node a B-Tree només es fa al node de fulla.


A continuació es mostra un exemple d'un B-Tree d'ordre mínim 5
Nota: que en els B-Trees pràctics, el valor de la comanda mínima és molt més que 5.




Podem veure al diagrama anterior que tots els nodes fulla estan al mateix nivell i totes les que no són fulles no tenen un subarbre buit i tenen claus una menys que el nombre dels seus fills.

Dades interessants sobre B-Trees:

  • L'alçada mínima de l'arbre B que pot existir amb n nombre de nodes i m és el nombre màxim de fills que pot tenir un node és: h_{min} =lceillog_m (n + 1) ceil - 1
  • L'alçada màxima de l'arbre B que pot existir amb n nombre de nodes i t és el nombre mínim de fills que pot tenir un node no arrel és: h_{max} =lpislog_tfrac {n + 1}{2} pisi t = lceilfrac {m}{2} ceil

Travessia a B-Tree:

Traversal també és similar a Inorder traversal de Binary Tree. Comencem des del fill més esquerre, imprimim recursivament el fill més esquerre i, a continuació, repetim el mateix procés per als fills i les claus restants. Al final, imprimiu recursivament el fill més a la dreta.



Operació de cerca a B-Tree:

La cerca és similar a la cerca a l'arbre de cerca binari. Sigui k la clau a buscar.

  • Comenceu des de l'arrel i recorreu recursivament cap avall.
  • Per a cada node no full visitat,
    • Si el node té la clau, simplement retornem el node.
    • En cas contrari, tornem al fill adequat (el nen que està just abans de la primera clau més gran) del node.
  • Si arribem a un node fulla i no trobem k al node fulla, retornem NULL.

Cercar un arbre B és similar a cercar un arbre binari. L'algorisme és similar i va amb recursivitat. A cada nivell, la cerca s'optimitza com si el valor de la clau no estigués present a l'interval del pare, llavors la clau està present en una altra branca. Com que aquests valors limiten la cerca, també es coneixen com a valors límit o valors de separació. Si arribem a un node fulla i no trobem la clau desitjada, mostrarà NULL.

Algorisme per cercar un element en un arbre 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->clau[i]) {> >i++;> >}> >if> (i n && k == x->clau [i]) {> >return> x;> >}> >if> (x->fulla) {> >return> nullptr;> >}> >return> BtreeSearch(x->fill[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); }>
>
>

Python 3

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 si i i k == x.key[i]: retorna x si x.leaf: retorna Cap retorn 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); }>
>
>

Exemples:

dfs vs bfs

Entrada: Cerca 120 a l'arbre B donat.



Solució:

esborra el fitxer en java



En aquest exemple, podem veure que la nostra cerca es va reduir només limitant les possibilitats que la clau que conté el valor pogués estar present. De la mateixa manera, si a l'exemple anterior hem de buscar 180, aleshores el control s'aturarà al pas 2 perquè el programa trobarà que la clau 180 està present dins del node actual. I de la mateixa manera, si es tracta de buscar 90, com a 90 <100, de manera que anirà automàticament al subarbre esquerre i, per tant, el flux de control anirà de la mateixa manera com es mostra a l'exemple anterior.

A continuació es mostra la implementació de l'enfocament anterior:

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->travessa();> >}> >// function to search a key in this tree> >BTreeNode* search(>int> k)> >{> >return> (root == NULL) ? NULL : root->cerca (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]->travessa(); cout<< ' ' << keys[i]; } // Print the subtree rooted with last child if (leaf == false) C[i]->travessa(); } // Funció per cercar la clau k en un subarbre arrelat amb aquest node BTreeNode* BTreeNode::search(int k) { // Troba la primera clau més gran o igual que k int i = 0; while (tecles i [i]) i++; // Si la clau trobada és igual a k, retorna aquest node si (claus[i] == k) retorna això; // Si la clau no es troba aquí i aquest és un node full si (fulla == true) retorna NULL; // Anar al fill adequat retorn C[i]->cerca(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);> >}> }> 
    
>
    
>
 
Python 3
                    
 # 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 si 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) # Divideix el fill 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] si no y.leaf: z.child = y.child[t: 2 * t] y. fill = y.child[0: t - 1] # Imprimeix l'arbre def print_tree(self, x, l=0): print('Level ', l, ' ', len(x.keys), end=':') per i a x.keys: print(i, end=' ') print() l += 1 si len(x.child)> 0: per i a x.child: self.print_tree(i, l) # Clau de cerca a l'arbre def search_key(self, k, x=None): si x no és Cap: i = 0 mentre ix.keys[i][0]: i += 1 si 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> 
    
>
    
>
 
  
    Nota:    El codi anterior no conté el programa del controlador. Cobrirem el programa complet a la nostra propera publicació Inserció B-Tree .
 
Hi ha dues convencions per definir un arbre B, una és definir per grau mínim, la segona és definir per ordre. Hem seguit la convenció de grau mínim i seguirem la mateixa en properes publicacions a B-Tree. Els noms de variables utilitzats en el programa anterior també es mantenen iguals
forma completa iskcon

 
    Aplicacions de B-Trees:    
  • S'utilitza en grans bases de dades per accedir a les dades emmagatzemades al disc
  • La cerca de dades en un conjunt de dades es pot aconseguir en molt menys temps amb el B-Tree
  • Amb la funció d'indexació, es pot aconseguir una indexació multinivell.
  • La majoria dels servidors també utilitzen l'enfocament de l'arbre B.
  • Els B-Trees s'utilitzen en sistemes CAD per organitzar i cercar dades geomètriques.
  • Els B-Trees també s'utilitzen en altres àrees com el processament del llenguatge natural, les xarxes informàtiques i la criptografia.
    Avantatges de B-Trees:    
  • Els B-Trees tenen una complexitat de temps garantida d'O(log n) per a operacions bàsiques com la inserció, la supressió i la cerca, cosa que els fa adequats per a grans conjunts de dades i aplicacions en temps real.
  • Els arbres B s'autoequilibren.
  • Alta concurrència i alt rendiment.
  • Ús eficient de l'emmagatzematge.
    Desavantatges dels B-Trees:    
  • Els B-Trees es basen en estructures de dades basades en disc i poden tenir un ús elevat de disc.
  • No és el millor per a tots els casos.
  • Lent en comparació amb altres estructures de dades.
Inserció i eliminació:  
 Inserció B-Tree    
 Eliminació de l'arbre B