Introducción de B-Tree – Part 1

Introducción: 
B-Tree es un árbol de búsqueda autoequilibrado. En la mayoría de los otros árboles de búsqueda autoequilibrados (como AVLy Red-Black Trees), se supone que todo está en la memoria principal. Para comprender el uso de B-Trees, debemos pensar en la enorme cantidad de datos que no caben en la memoria principal. Cuando el número de claves es alto, los datos se leen del disco en forma de bloques. El tiempo de acceso al disco es muy alto en comparación con el tiempo de acceso a la memoria principal. La idea principal de usar B-Trees es reducir la cantidad de accesos al disco. La mayoría de las operaciones del árbol (búsqueda, inserción, eliminación, máximo, mínimo, etc.) requieren accesos al disco O(h), donde h es la altura del árbol. B-tree es un árbol gordo. La altura de B-Trees se mantiene baja colocando el máximo de claves posibles en un Node de B-Tree. Generalmente, el tamaño del Node B-Tree se mantiene igual al tamaño del bloque del disco.
Complejidad temporal de B-Tree: 
 

“n” es el número total de elementos en el árbol B.
Propiedades de B-Tree: 
 

1. Todas las hojas están al mismo nivel.
2. Un B-Tree se define por el término grado mínimo ‘t’. El valor de t depende del tamaño del bloque de disco.
3. Cada Node, excepto el raíz, debe contener al menos t-1 claves. La raíz puede contener un mínimo de 1 clave.
4. Todos los Nodes (incluido el raíz) pueden contener como máximo 2*t – 1 claves.
5. El número de hijos de un Node es igual al número de claves en él más 1.
6. Todas las claves de un Node se ordenan en orden creciente. El hijo entre dos claves k1 y k2 contiene todas las claves en el rango de k1 y k2.
7. B-Tree crece y se encoge desde la raíz, a diferencia del Binary Search Tree. Los árboles de búsqueda binaria crecen hacia abajo y también se encogen hacia abajo.
8. Al igual que otros árboles de búsqueda binarios equilibrados, la complejidad del tiempo para buscar, insertar y eliminar es O (log n).
9. La inserción de un Node en B-Tree ocurre solo en el Node hoja.

A continuación se muestra un ejemplo de B-Tree de pedido mínimo 5. Tenga en cuenta que en los B-Tree prácticos, el valor del pedido mínimo es mucho mayor que 5. 
 

Podemos ver en el diagrama anterior que todos los Nodes de hoja están en el mismo nivel y todos los Nodes de hoja no tienen un subárbol vacío y tienen claves una menos que el número de sus hijos.
Datos interesantes: 

1. La altura mínima del B-Tree que puede existir con n número de Nodes y m es el número máximo de hijos de un Node que puede tener es: 
2. La altura máxima del B-Tree que puede existir con n número de Nodes y t es el número mínimo de hijos que puede tener un Node no raíz es:  y 

Recorrido en B-Tree: 
Recorrido también es similar al recorrido Inorder de Binary Tree. Comenzamos desde el hijo más a la izquierda, imprimimos recursivamente el hijo más a la izquierda, luego repetimos el mismo proceso para los niños y claves restantes. Al final, imprima recursivamente el hijo más a la derecha. 

Operación de búsqueda en B-Tree: 
La búsqueda es similar a la búsqueda en Binary Search Tree. Sea k la clave a buscar. Comenzamos desde la raíz y recorremos recursivamente hacia abajo. Para cada Node no hoja visitado, si el Node tiene la clave, simplemente devolvemos el Node. De lo contrario, recurrimos al hijo apropiado (el hijo que está justo antes de la primera clave mayor) del Node. Si llegamos a un Node hoja y no encontramos k en el Node hoja, devolvemos NULL.

Lógica: 
buscar en un árbol B es similar a buscar en un árbol binario. El algoritmo es similar y va con recursividad. En cada nivel, la búsqueda se optimiza como si el valor de la clave no estuviera presente en el rango del padre, entonces la clave está presente en otra rama. Como estos valores limitan la búsqueda, también se conocen como valor límite o valor de separación. Si llegamos a un Node hoja y no encontramos la clave deseada, mostrará NULL.

Algoritmo para buscar un elemento: –

    BtreeSearch(x, k)
    i = 1

    while i ≤ n[x] and k ≥ keyi[x]        // n[x] means number of keys in x node
           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)

Ejemplo: Buscando 120 en el B-Tree dado. 
 

 
Solución: 
 

En este ejemplo, podemos ver que nuestra búsqueda se redujo simplemente limitando las posibilidades de que la clave que contiene el valor pudiera estar presente. De manera similar, si dentro del ejemplo anterior tenemos que buscar 180, entonces el control se detendrá en el paso 2 porque el programa encontrará que la clave 180 está presente dentro del Node actual. Y de manera similar, si se trata de buscar 90, entonces como 90 < 100, irá automáticamente al subárbol izquierdo y, por lo tanto, el flujo de control será similar al que se muestra en el ejemplo anterior.

// C++ implementation of search() and traverse() methods
#include<iostream>
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->search(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 < n; 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();
}
 
// Function to search key k in subtree rooted with this node
BTreeNode *BTreeNode::search(int k)
{
    // Find the first key greater than or equal to k
    int i = 0;
    while (i < n && k > 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);
}

// 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 < n && k > 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);
 
    }
}

// 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 < n && k > 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

<script>
 
// 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("<br>");
    }
     
    // 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 < n && k > 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
</script>

El código anterior no contiene el programa controlador. Cubriremos el programa completo en nuestra próxima publicación sobre B-Tree Insertion .
Hay dos convenciones para definir un B-Tree, una es definir por grado mínimo (seguido en el libro de Cormen ), la segunda es definir por orden. Hemos seguido la convención de grado mínimo y la seguiremos en las próximas publicaciones en B-Tree. Los nombres de variables utilizados en el programa anterior también se mantienen igual que el libro de Cormen para una mejor legibilidad. 

Aplicaciones de los árboles B:

• Se utiliza en grandes bases de datos para acceder a los datos almacenados en el disco.
• La búsqueda de datos en un conjunto de datos se puede lograr en mucho menos tiempo usando el árbol B
• Con la función de indexación se puede lograr una indexación multinivel.
• La mayoría de los servidores también utilizan el enfoque de árbol B.

Insertion and Deletion  
B-Tree Insertion  
B-Tree Deletion
Referencias:  
Introducción a los algoritmos 3.ª edición por Clifford Stein, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest
Escriba comentarios si encuentra algo incorrecto o si desea compartirlo más información sobre el tema tratado anteriormente.