INTRODUCCIÓ DE B-TREE - TECHCODEVIEW.COM

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.	Algoritme	Complexitat temporal
1.	Cerca	O(log n)
2.	Insereix	O(log n)
3.	Suprimeix	O(log n)

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

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} pis$ i $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:

Entrada: Cerca 120 a l'arbre B donat.

Solució:

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 i x.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  
      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