Los árboles B son estructuras fundamentales para bases de datos y sistemas de almacenamiento que buscan optimizar el acceso a la información. En esta ocasión, nos adentramos en dos operaciones clave para mantener la integridad y eficiencia de estos árboles: la inserción y la división de nodos.
La inserción en un árbol B se realiza siempre en nodos hoja. Si el nodo donde queremos insertar no es hoja, debemos buscar recursivamente el hijo más prometedor, es decir, aquel que contendrá el rango adecuado para el nuevo valor. Para encontrar este hijo, recorremos las claves del nodo actual hasta hallar la primera clave mayor o igual que el valor a insertar, y seguimos por el puntero izquierdo de esa clave. Si el valor es mayor que todas las claves, avanzamos por el último puntero derecho. Este proceso garantiza que la inserción respete el orden del árbol.
Un aspecto importante es cómo manejar los duplicados. Si permitimos claves repetidas, podemos insertar múltiples ocurrencias sin problema, siempre siendo consistentes en elegir, por ejemplo, el hijo izquierdo o derecho para insertar duplicados. Sin embargo, esto puede hacer que el árbol crezca en profundidad y ocupe más espacio, afectando el rendimiento. Una alternativa para optimizar es almacenar un contador de repeticiones junto a cada clave, evitando insertar múltiples nodos con la misma clave y reduciendo el tamaño del árbol.
Cada nodo en un árbol B tiene un límite mínimo y máximo de claves, determinado por el grado M del árbol. El máximo número de claves es M-1, y el mínimo es el techo de M/2 menos 1. Por ejemplo, en un árbol de grado 7, un nodo debe tener entre 3 y 6 claves. Cuando insertamos un nuevo elemento en un nodo hoja, si el número de claves excede el máximo permitido, debemos dividir el nodo para mantener la validez del árbol.
La división consiste en elegir un pivote, que es la clave en la posición mínima permitida (L), y separar el nodo en dos subnodos: uno con las claves menores al pivote y otro con las mayores. El pivote se eleva al nodo padre, insertándose en orden junto con un nuevo puntero al subnodo derecho creado. Si el nodo padre también se llena por esta inserción, se repite el proceso recursivamente, pudiendo llegar a dividir la raíz. En ese caso, se crea un nuevo nodo raíz que contiene solo el pivote, y los dos subnodos resultantes se convierten en sus hijos.
Para implementar estas operaciones, es útil ampliar el array de claves en cada nodo para que pueda contener una clave adicional temporalmente durante la inserción, evitando errores por desbordamiento. La función de inserción ordenada se encarga de insertar un valor en un nodo desplazando las claves y punteros necesarios para mantener el orden. Esta función también recibe un puntero al hijo derecho, que es útil cuando insertamos un pivote tras una división.
La función principal de inserción es recursiva. Si el nodo es hoja, simplemente insertamos el valor ordenadamente. Si no, buscamos el hijo más prometedor y llamamos recursivamente a la inserción en ese hijo. Tras la inserción, comprobamos si el nodo excede el número máximo de claves. Si es así, llamamos a la función división.
La función división crea un nuevo nodo y transfiere las claves y punteros mayores o iguales al pivote a este nuevo nodo, eliminándolos del nodo original. El pivote es el primer elemento del nuevo nodo. Esta función devuelve el nuevo nodo para que el padre pueda insertar el pivote y enlazar el nuevo subnodo. Así, evitamos referencias explícitas hacia el padre en la estructura de nodos, manteniendo la recursividad hacia abajo.
Cuando la función inserción detecta que un hijo ha sido dividido, recibe el nuevo nodo y debe insertar el pivote correspondiente en el nodo actual, desplazando claves y punteros para mantener el orden. Si esta inserción provoca un desbordamiento, se repetirá la división hacia arriba.
Este enfoque recursivo y ordenado garantiza que el árbol B se mantenga balanceado, con todos los nodos respetando sus límites de claves y punteros, optimizando las búsquedas y el almacenamiento. La operación de eliminación, que también es compleja, se deja para un análisis posterior.
A continuación, mostramos un ejemplo simplificado del pseudocódigo para la inserción ordenada en un nodo, que desplaza claves y punteros para insertar un nuevo valor en la posición correcta:
void insercionOrdenada(Nodo nodo, int valor, Nodo hijoDerecho) {
int i = nodo.numClaves - 1;
// Desplazar claves y punteros hacia la derecha para hacer espacio
while (i >= 0 && nodo.claves[i] > valor) {
nodo.claves[i + 1] = nodo.claves[i];
nodo.punteros[i + 2] = nodo.punteros[i + 1];
i--;
}
// Insertar el nuevo valor y puntero
nodo.claves[i + 1] = valor;
nodo.punteros[i + 2] = hijoDerecho;
nodo.numClaves++;
}
Y un esquema MermaidJS que ilustra la división de un nodo:
graph TD
NodoOriginal["Nodo Original: [10, 20, 30, 40, 50, 60]"]
Pivote["Pivote: 30"]
SubnodoIzq["Subnodo Izquierdo: [10, 20]"]
SubnodoDer["Subnodo Derecho: [40, 50, 60]"]
NodoPadre["Nodo Padre"]
NodoOriginal -->|División| SubnodoIzq
NodoOriginal -->|División| SubnodoDer
Pivote --> NodoPadre
NodoPadre --> SubnodoIzq
NodoPadre --> SubnodoDer
Este proceso es esencial para mantener el equilibrio y la eficiencia de los árboles B, especialmente en aplicaciones donde el acceso a disco es costoso y se busca minimizar el número de accesos para consultas rápidas y almacenamiento eficiente.