Árboles B

¿Qué son los árboles B y por qué existen?

Los árboles B son una estructura de datos diseñada para gestionar grandes volúmenes de información de manera eficiente, especialmente en sistemas donde los datos no caben completamente en la memoria principal (RAM). Esta estructura es ideal para aplicaciones críticas como bases de datos, donde la velocidad de acceso a los datos es esencial.

Problemas con los árboles binarios

Los árboles binarios, aunque eficientes en muchos casos, tienen limitaciones en escenarios del mundo real:

• Limitaciones de memoria: En aplicaciones con grandes cantidades de datos, los nodos de un árbol pueden ocupar mucho espacio y no caber completamente en memoria RAM.
• Accesos lentos: Cuando los árboles se almacenan en memoria secundaria (discos duros, SSD, etc.), los accesos son mucho más lentos que en memoria RAM.

En este contexto, los árboles B destacan porque minimizan los accesos a disco al permitir que cada nodo almacene más claves y tenga más hijos, reduciendo la profundidad del árbol y, por ende, la cantidad de operaciones necesarias para acceder a un dato.

Estructura de los árboles B

En un árbol binario teniamos una clave y como mucho 2 hijos. Pero en un árbol B:

• Cada nodo puede contener más de una clave (k).
• Cada nodo puede tener más de dos hijos(c).

Los hijos(c) y las claves(K) están relacionados.

Esta es una imagen de un nodo de un árbol B, donde K1, K2 y K3 son las claves del nodo, mientras que los hijos son los rectángulos azules.

Como ves siempre una clave tiene un puntero a un hijo a la izquierda y un puntero a un hijo a la derecha. Es importante que las claves sean comparables, es decir que se puedan comparar, porque en un nodo de un árbol B es importante que las claves estén ordenadas.(k1 < k2 < k3)

Aquí tendríamos punteros que van saliendo de los hijos

Al igual que pasaba en los árboles binarios, el hijo que esta entre k1 y k2 apunta a un subárbol donde contendrá elementos que tendrán valores entre k1 y k2.

Ventajas de los árboles B

• Mayor factor de ramificación: Al permitir más claves por nodo, se reduce la profundidad del árbol.
• Menos accesos a disco: Esto mejora significativamente el rendimiento en sistemas donde los datos residen en memoria secundaria.

Propiedades de los árboles B

Número máximo de hijos

Relación entre claves y hijos: Si decimos que un árbol es de grado 4, como el del ejemplo anterior, significa que cada nodo puede tener 4 hijos (k). Por lo que el número de claves sera k - 1 es decir 3.

ℹ️  Otra forma en la que se define el grado, es como el número mínimo de claves que tiene cada nodo, por lo que para un nodo de grado 4, tendrá 2 * 4 (hijos) y 2 * 4 - 1 claves como máximo. Si el nodo tiene como minimo 4 claves, tendrá 5 hijos como mínimo. Hay que tener en cuenta que algunas de estas propiedades no son requeridas para los nodos raíz.

Número mínimo de hijos

Un árbol de grado M con M hijos y M - 1 claves, los nodos deben de tener al menos M / 2 hijos (M / 2 - 1 claves). El redondeo siempre es hacia arriba.

Para mantener esto será necesario ir reestructurando el árbol.

Como excepción está la raíz que puede tener menos hijos de lo obligado.

Operaciones en árboles B

Operaciones básicas

1. Búsqueda: Similar a los árboles binarios, pero adaptada para recorrer más claves e hijos por nodo.
2. Inserción:
   • Si un nodo tiene espacio, se inserta directamente.
   • Si un nodo está lleno, se divide (operación de división) y se redistribuyen las claves.
3. Eliminación:
   • Si la eliminación deja un nodo con menos claves de las permitidas, se reorganiza el árbol para mantener sus propiedades.

Operaciones adicionales

• Dividir nodos: Ocurre cuando un nodo está lleno y se inserta una nueva clave. Este proceso redistribuye las claves y ajusta la estructura del árbol.
• Reestructurar nodos: Puede ser necesario durante una eliminación para garantizar que los nodos cumplan con el número mínimo de claves.