3 - Estructura de un nodo B-Tree en C

Con los límites del grado mínimo definidos, necesitamos una representación concreta del nodo para implementar el B-Tree. Un nodo almacena sus claves en un arreglo ordenado, mantiene punteros a hijos intercalados y lleva un contador de claves para saber dónde insertar, dividir o fusionar.

El diseño busca reducir saltos de memoria y alinearse con el tamaño del bloque. Los miembros son planos (arreglos contiguos) para favorecer la localidad y la serialización en disco.

3.1 Arreglo de claves

Las claves se guardan en un arreglo contiguo de enteros (o del tipo que represente la llave). Están siempre ordenadas y se recorren secuencialmente durante la búsqueda.

• Tamaño: 2t - 1 posiciones máximas; permite insertar una clave extra antes de dividir.
• Inserción local: se desplazan claves a la derecha para abrir espacio, evitando nuevas asignaciones.
• Comparaciones por bloque: el recorrido secuencial dentro del arreglo es rápido y se mantiene en caché.

3.2 Arreglo de punteros a hijos

Los punteros a hijos se almacenan en un arreglo paralelo, con una posición extra respecto a las claves para cubrir todos los intervalos.

• Tamaño: 2t punteros como máximo.
• Intercalado: cada puntero separa rangos de claves: hijo0 < clave0 < hijo1 < clave1 ...
• Reuso: los punteros se mueven durante splits y merges, sin reasignar toda la estructura.

3.3 Cantidad actual de claves

Un contador entero indica cuántas claves están en uso dentro del arreglo. Evita recorrer espacios vacíos y es esencial para validar los límites t - 1 y 2t - 1.

• Control de divisiones: si cuenta == 2t - 1 antes de descender, se debe dividir el nodo.
• Control de fusión: si cuenta == t - 1 al eliminar, se debe redistribuir o fusionar.
• Iteraciones: acota los bucles de búsqueda y recorrido en O(2t) operaciones por nodo.

3.4 Indicador de nodo hoja

Un flag binario (esHoja) distingue si el nodo tiene hijos. Cambia el flujo de las operaciones:

• Inserción: si es hoja se escribe directamente; si es interno se desciende al hijo apropiado.
• Eliminación: las hojas borran in situ; los internos pueden reemplazar por predecesor/sucesor.
• Recorrido: optimiza recorridos en disco evitando leer punteros a hijos inexistentes.

3.5 Organización del archivo

Para pruebas rápidas puedes poner todo en un solo main.c: declaración de la estructura, firmas y código de las funciones. Así evitas un .h y compilas un único archivo.

/* main.c: declaracion y definicion juntas para prototipos rapidos */
typedef struct BTreeNode {
  int *claves;              /* arreglo de claves ordenadas */
  struct BTreeNode **hijos; /* punteros a subarboles */
  int cuenta;               /* cantidad actual de claves */
  int esHoja;               /* 1 si es hoja, 0 si es interno */
  int orden;                /* grado minimo t */
} BTreeNode;

BTreeNode *btree_crear(int t);
void btree_insertar(BTreeNode **raiz, int clave);
int btree_buscar(BTreeNode *raiz, int clave);
void btree_eliminar(BTreeNode **raiz, int clave);
void btree_destruir(BTreeNode *raiz);

/* Implementaciones: reservar arreglos de tamanio maximo (2t-1 claves, 2t hijos)
   y aplicar las reglas de split/merge vistas en los temas anteriores. */

Con todo en main.c solo compilas ese archivo para inicializar el árbol con el grado t deseado y probar búsquedas, inserciones y eliminaciones.