1 - Introducción a los árboles multicamino

Iniciamos el tutorial dedicado a los árboles multicamino, también conocidos como B-Tree y sus variantes como B+ Tree. Son estructuras pensadas para discos y SSD, donde se prioriza reducir accesos a bloques completos en lugar de optimizar rotaciones individuales como en los árboles binarios.

Trabajaremos en C y usaremos ejemplos sencillos que ponen el foco en la organización por páginas, el reparto de claves y la altura logarítmica que se mantiene sin rotaciones. Este primer tema explica por qué existen, cómo se diferencian de los BST y AVL, y dónde se aplican en la práctica.

1.1 Qué son los árboles B

Un árbol B es un árbol de búsqueda de más de dos hijos (multicamino) que asegura que todas las hojas están a la misma profundidad. Cada nodo almacena varias claves ordenadas y tiene punteros a sus hijos, también ordenados entre esas claves.

• Orden o grado mínimo (t): determina cuántas claves e hijos puede contener cada nodo.
• Nodo raíz: puede tener menos claves que el resto, pero siempre es el punto de entrada.
• Altura baja: el factor de ramificación amplio mantiene el número de niveles muy pequeño, incluso con millones de claves.

typedef struct BTreeNode {
  int *claves;              // Arreglo ordenado de claves
  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 (define tamanos de nodo)
} BTreeNode;

El esqueleto anterior muestra la idea central: un nodo almacena arreglos de claves y de hijos en lugar de un par de punteros como en un árbol binario. La variable orden se usa para validar cuándo dividir o fusionar nodos.

1.2 Por qué existen los árboles multicamino

Los discos y SSD leen por bloques; acceder a disco es mucho más costoso que procesar varias comparaciones en memoria. Los árboles multicamino explotan esto almacenando muchas claves por nodo, alineando cada nodo con el tamaño de bloque.

• Menos I/O: cada lectura de bloque aporta decenas o centenas de claves y punteros, lo que reduce la cantidad de accesos físicos.
• Altura mínima: el alto factor de ramificación consigue alturas muy bajas (a menudo 2 o 3 niveles para millones de registros).
• Mutaciones locales: dividir (split) o fusionar nodos afecta uno o dos bloques, manteniendo el equilibrio sin rotaciones costosas.

La idea general es pagar algunas comparaciones extra dentro de un nodo a cambio de menos viajes al medio de almacenamiento.

1.3 Diferencias con BST y AVL

Un BST y un AVL son binarios: cada nodo tiene dos hijos y a lo sumo una clave. Los árboles B trabajan distinto:

• Multiples claves por nodo: las claves se almacenan en un arreglo ordenado y los hijos se intercalan entre ellas.
• Balance implícito: no hay factores de equilibrio ni alturas guardadas; el invariante de cantidad mínima/máxima de claves mantiene la altura acotada.
• Operaciones de reorganización: en lugar de rotaciones se usan divisiones (split) y fusiones (merge) para redistribuir claves.
• Complejidad: las operaciones siguen siendo O(log n) en número de nodos, pero el logaritmo se toma respecto al orden del árbol (menos niveles que un binario).
• Localidad: los nodos se adaptan a bloques de disco o a cachés de CPU, mejorando la eficiencia práctica en datos grandes.

1.4 Aplicaciones en bases de datos y sistemas de archivos

Los árboles multicamino surgieron para mejorar los índices en almacenamiento secundario y siguen siendo la opción de facto:

• Índices de bases de datos: motores relacionales y NoSQL usan árboles B o B+ para soportar búsquedas y recorridos por rango con pocas lecturas de disco.
• Sistemas de archivos: NTFS, APFS y ext4 emplean variantes B+ para localizar inodos, bloques y directorios de manera eficiente.
• Almacenamiento de claves/valores: caches persistentes y key-value stores basados en discos magnéticos o SSD aprovechan la baja altura para servir lecturas rápidas.
• Indices por prefijo: los B+ se combinan con claves compuestas o truncadas para acelerar filtros por rangos o coincidencias parciales.

Con esta base ya podemos profundizar en el orden del árbol, la definición exacta de los límites de claves y cómo se implementa cada operación.