3 - Estructura de un nodo B-Tree en Python

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 (es_hoja) 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.py: declaración de la clase, funciones y código de prueba. Así evitas módulos separados y ejecutas un único archivo.

# main.py: declaracion y definicion juntas para prototipos rapidos
class BTreeNode:
  def __init__(self, orden, es_hoja):
    self.claves = []        # lista de claves ordenadas
    self.hijos = []         # referencias a subarboles
    self.cuenta = 0         # cantidad actual de claves
    self.es_hoja = es_hoja  # True si es hoja, False si es interno
    self.orden = orden      # grado minimo t

def btree_crear(t):
  return BTreeNode(t, True)

def btree_insertar(raiz, clave):
  pass

def btree_buscar(raiz, clave):
  pass

def btree_eliminar(raiz, clave):
  pass

def btree_destruir(raiz):
  pass

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

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