2 - Conceptos fundamentales de los árboles B

Antes de implementar un B-Tree conviene fijar sus parámetros base. El grado mínimo (t) marca el tamaño de los nodos, cuántas claves puede almacenar cada uno y cuántos hijos se admiten. Estos límites, junto con la distinción entre nodos internos y hojas, garantizan una altura muy pequeña sin rotaciones.

Todo lo que sigue aplica a implementaciones clásicas usadas en motores de bases de datos y sistemas de archivos. A partir de las restricciones formales podremos derivar las operaciones de inserción y eliminación que mantienen el árbol balanceado.

2.1 Orden del árbol (grado mínimo t)

El orden, también llamado grado mínimo y denotado como t, define la capacidad básica de cada nodo:

• Tamaño de bloque: suele elegirse para que un nodo completo quepa en un bloque de disco o caché (por ejemplo, 4 KB).
• Factor de ramificación: cada nodo interno tiene al menos t hijos y hasta 2t, lo que fija la base del logaritmo en la complejidad.
• Uniformidad: todos los nodos usan el mismo t; no hay nodos con orden variable.

Elegir t demasiado pequeño produce más niveles; elegirlo demasiado grande desaprovecha espacio. En práctica se calcula con el tamaño de la clave y el puntero al hijo para llenar el bloque sin fragmentación.

2.2 Número permitido de claves

Los límites de claves por nodo dependen de si el nodo es la raíz:

• Nodo interno no raíz: entre t - 1 y 2t - 1 claves.
• Raíz: puede tener de 1 a 2t - 1 claves si no es hoja; si es hoja (cuando el árbol tiene pocos elementos) puede incluso quedar con 0.

Estos límites son los que activan los splits al insertar y las fusiones o redistribuciones al eliminar. Mantenerlos evita nodos demasiado vacíos que harían crecer la altura.

/* Calculo de limites de claves por nodo */
int max_claves(int t) { return 2 * t - 1; }
int min_claves(int t, int es_raiz) {
  return es_raiz ? 1 : t - 1; /* la raiz puede quedar con 1 clave */
}

Con t = 3 cada nodo admite 2 a 5 claves (la raíz de 1 a 5). Al superar 5 se divide el nodo; al bajar de 2 en un nodo interno se debe pedir o fusionar claves con sus hermanos.

2.3 Número permitido de hijos

Los hijos siempre son uno más que la cantidad de claves almacenadas, respetando estos topes:

• Nodo interno no raíz: entre t y 2t hijos.
• Raíz: si no es hoja, puede tener de 2 a 2t hijos; si es hoja, no tiene hijos.
• Hojas: siempre tienen 0 hijos aunque mantengan los límites de claves.

Estas cotas aseguran que un nodo interno nunca quede con un solo hijo, lo que evitaría la compactación logarítmica que hace eficientes a los B-Tree.

2.4 Nodo interno vs nodo hoja

La diferencia no es solo estructural; también afecta cómo se aplican las operaciones:

• Nodo hoja: almacena claves y, según la variante (B o B+), los valores o punteros al registro. No tiene hijos, así que las inserciones y eliminaciones se resuelven localmente.
• Nodo interno: solo direcciona la búsqueda. Mantiene claves de separación y punteros a subárboles. Durante splits puede promover una clave al padre.
• Recorrido: todas las hojas están al mismo nivel, por lo que alcanzar una hoja implica el mismo número de saltos desde la raíz.

Entender el rol de cada tipo de nodo ayuda a decidir dónde conviene colocar datos (B vs B+) y cómo optimizar la lectura de discos o SSD.

2.5 Propiedad de balanceo automático

El balanceo en un árbol B no depende de factores de equilibrio ni alturas guardadas en cada nodo. Se logra cumpliendo siempre los límites de claves e hijos:

• Splits controlados: al insertar en un nodo lleno se divide en dos nodos con t - 1 claves cada uno y se promociona la clave central.
• Redistribución y fusiones: al eliminar se pide prestada una clave a un hermano adyacente o se fusionan nodos para que ninguno quede por debajo del mínimo.
• Altura estable: la raíz solo crece hacia arriba cuando se divide; el resto de niveles permanece con hojas alineadas.
• Complejidad: las operaciones siguen siendo O(log n) con base t, reduciendo el número de niveles gracias al alto factor de ramificación.

Este balanceo implícito es lo que hace que, incluso con millones de registros, la mayoría de los B-Tree prácticos tengan solo 2 o 3 niveles, minimizando los accesos a disco.