Arboles-B

Por: Salvador Pozo Coronado

[Principal] [Índice de artículos] [Siguiente]

Generalidades:

Los árboles-B son árboles de búsqueda.

La "B" probablemente se debe a que el algoritmo fue desarrollado por "Rudolf Bayer" y "Eduard M. McCreight", que trabajan para la empresa "Boeing" aunque parece que "Karl Unterauer" desarrolló un algoritmo semejante en la misma época.

Lo que si es cierto es que la letra B no significa "binario", ya que:

  1. Los árboles-B nunca son binarios.
  2. Y tampoco es porque sean árboles de búsqueda, ya que en inglés se denominan B-trees.
  3. Tampoco es porque sean balanceados, ya que no suelen serlo.

En cualquier caso, tampoco es demasiado importante el significado de la "B", si es que lo tiene, lo interesante realmente es el algoritmo.

A menudo se usan árboles binarios de búsqueda para ordenar listas de valores, minimizando el número de lecturas, y evitando tener que ordenar dichas listas.

Pero este tipo de árboles tienen varias desventajas:

  1. Es difícil construir un árbol binario de búsqueda perfectamente equilibrado.
  2. El número de consultas en el árbol no equilibrado es impredecible.
  3. Y además el número de consultas aumenta rápidamente con el número de registros a ordenar.

Para evitar estos inconvenientes se usan árboles-B, sobre todo cuando se ordenan ficheros, donde se ha convertido en el sistema de indexación más utilizado. En el curso sobre manejo de ficheros veremos una implementación de árboles-B aplicaco a ficheros.

Los árboles-B son árboles de búsqueda de m ramas, y cada nodo puede almacenar un máximo de m-1 claves.

Las características que debe cumplir un árbol-B son:

Ejemplo de un árbol-B de ORDEN 5 y de profundidad 2.

Existen varios criterios para dimensionar el ORDEN de un árbol-B.

Normalmente se intenta limitar la profundidad del árbol, de modo que el número máximo de consultas sea pequeño. Cuanto mayor sea el ORDEN, menor será la profundidad.

Cuando se crean árboles-B para indexar ficheros de datos en disco, intervienen otras condiciones. En ese caso interesa que el número de accesos a disco sea lo más pequeño posible. Para calcular el ORDEN se usa como dato el tamaño del cluster. Un cluster es el bloque de disco más pequeño que se lee o se escribe en una operación de acceso a disco, su tamaño suele ser distinto según el tamaño de disco y el tipo de formato que tenga, puede variar entre 512 bytes y múltiplos de esa cantidad. El ORDEN se ajusta de modo que el tamaño del nodo sea lo más próximo posible, menor o igual, al tamaño del cluster.

Las operaciones que se pueden realizar en un árbol-B son básicamente tres:

Estructura de un nodo:

Para ilustrar este artículo haremos un programa que indexará una tabla de enteros usando un árbol-B.

Implementaremos dos clases, una para el tratamiento de los nodos y otra para el árbol.

Cada clave estará compuesta por una pareja de valores, uno de esos valores es la propia clave, en nuestro ejemplo será un entero, pero en general será del mismo tipo que el campo por el que ordenaremos la tabla o fichero, el otro campo será una referencia al registro al que corresponda dicha clave. Por ejemplo, si tenemos un fichero con la siguiente estructura de registro:

struct registro {
   char nombre[32];
   int edad;
   long telefono;
};

Y queremos construir un árbol-B para indicar una tabla de 1000 registros por el campo nombre.

Nuestra clave será una estructura como ésta: 

struct stclave {
   char nombre[32];
   long registro; // número índice correspondiente a la clave "nombre"
};

Si lo que tenemos que ordenar es un fichero, el valor de registro sería la posición del registro de datos asociado a la clave dentro del fichero.

En rigor, un nodo sólo necesita almacenar un máximo de m-1 claves y m punteros, pero para facilitar el manejo de los árboles-B, añadiremos algunos datos extra.

Para el nodo, definiremos la clase bnodo como sigue: 

class bnodo {
  public:
   bnodo(int nClaves); // Constructor
   ~bnodo();           // Destructor
 
  private:
   int clavesUsadas;   // Claves usadas en el nodo
   stclave *clave;     // Array de claves del nodo
   bnodo **puntero;    // Array de punteros a bnodo
   bnodo *padre;       // Puntero a nodo padre
 
  friend class btree;
};

Además de un array de claves y de punteros, que es lo que se necesita para definir un nodo según el gráfico que hemos visto antes, hemos añadido un par de datos más que nos facilitarán en manejo del árbol.

Uno es el número de claves usadas en el nodo, ya sabemos que no tienen por qué estar todas usadas. El otro es un puntero al nodo padre, este puntero nos será muy útil para insertar y eliminar claves.

Clase para manejar la estructura del árbol:

class btree {
  public:
   btree(int nClv);              // Constructor
   ~btree();                     // Destructor
   long Buscar(int clave);       // Buscar un valor de clave, devuelve la posición en el array
   bool Insertar(stclave clave); // Insertar una clave
   void Borrar(int clave);       // Borrar la clave correspondiente a un valor
   void Mostrar();               // (Depuración) Mostrar el árbol por pantalla

  private:
   stclave *lista;               // Auxiliar para insertar claves
   pbnodo *listapunt;            // Auxiliar para insertar claves
   // Funciones auxiliares internas de la clase:
   void Inserta(stclave clave, pbnodo nodo, pbnodo hijo1, pbnodo hijo2);
   void BorrarClave(pbnodo nodo, int valor);
   void BorrarNodo(pbnodo nodo);
   void PasarClaveDerecha(pbnodo derecha, pbnodo padre, pbnodo nodo, int posClavePadre);
   void PasarClaveIzquierda(pbnodo izquierda, pbnodo padre, pbnodo nodo, int posClavePadre);
   void FundirNodo(pbnodo izquierda, pbnodo &padre, pbnodo derecha, int posClavePadre);
   void Ver(pbnodo nodo);
 
   int nClaves;                  // Número de claves por nodo
   int nodosMinimos;             // Número de punteros mínimos para cada nodo que no sea hoja
   pbnodo Entrada;               // Puntero a nodo de entrada en el árbol
};

Se han declarado varias funciones auxiliares privadas para facilitar la inserción y borrado de nodos. Estas funciones sólo se usarán internamente por la clase.

Algoritmo de inserción de claves:

Se trata de un algoritmo iterativo, aunque también puede implementarse recursivamente.

Veremos ahora algunos ejemplos.

Ejemplo con inserción de nodo:

Veamos un ejemplo. Supongamos que queremos insertar la clave 52 en el árbol del ejemplo.

No hay espacio para almacenar la clave en nodo, por lo tanto creamos un nuevo nodo:

Ahora tenemos que promocionar la clave intermedia, insertándola en el nodo padre. El proceso es recursivo, aunque el algoritmo que hemos diseñado es iterativo.

Ejemplo con aumento de altura del árbol:

Veamos otro ejemplo que implicará que aumente la altura del árbol. Supongamos que tenemos un árbol con esta estructura, y queremos insertar la clave 68:

En primer lugar, dividimos nodo en dos, repartimos las claves y promocionamos el valor intermedio, el 69:

Ahora estamos de nuevo en la misma situación, el anterior nodo pasa a ser el nodo padre, y el padre de éste es null. Ahora procedemos igual, dividimos nodo en dos, separamos las claves, y promocionamos el valor intermedio:

Y otra vez repetimos el proceso, el algoritmo funciona de forma recursiva, pero en este caso nodo es null, por lo tanto estamos en un caso diferente, según el algoritmo debemos crear un nuevo nodo, hacer que ese nodo sea el de entrada, insertar la clave y actualizar los punteros:

Siguiente>>

© Agosto de 2.001, Con Clase, [email protected]