Arboles B y B+ en Python

Insertar en un B-Tree exige mantener los límites de claves por nodo. El patrón general es descender solo por nodos que no estén llenos; si un nodo está completo se divide antes de seguir. Esto evita llegar a una hoja saturada.

Visualizador interactivo de Árbol B

5.1 Inserción en nodo hoja no lleno

Si la hoja donde debe ir la clave tiene menos de 2t - 1 claves:

Se desplazan a la derecha las claves mayores para abrir espacio.
Se inserta la nueva clave manteniendo el orden.
No se realizan operaciones sobre el resto del árbol.

5.2 Inserción recursiva en nodo interno

Si el nodo actual es interno:

Se localiza el hijo que contiene el rango de la clave.
Antes de descender, si ese hijo está lleno se hace split para liberar espacio.
Luego se desciende al hijo adecuado (izquierdo o derecho según la clave promovida).

Dividir antes de descender garantiza que siempre lleguemos a una hoja con espacio.

5.3 Operación de split en nodo lleno

Al dividir un nodo con 2t - 1 claves:

Se crea un nuevo nodo hermano con las últimas t - 1 claves.
La clave central (posición t - 1) se promueve al padre.
Si el nodo era interno, se reparten también sus punteros a hijos (t y t).

5.4 Promoción de la clave al nodo padre

La clave media sube al padre y separa a los dos nodos resultantes. En el padre se inserta como cualquier clave, moviendo punteros para colocar los nuevos hijos izquierdo y derecho.

Esta promoción puede encadenarse si el padre estaba lleno, provocando splits hacia arriba hasta, eventualmente, la raíz.

5.5 Casos especiales con la raíz

La raíz tiene dos consideraciones:

Si está llena y se va a insertar, se crea una nueva raíz vacía y se divide la raíz antigua en dos hijos.
Si el árbol está vacío, la raíz es una hoja que recibe la primera clave sin dividir.

Gracias a esto la altura solo crece hacia arriba en splits de la raíz, manteniendo todas las hojas al mismo nivel.

# Insercion top-down: divide antes de descender
def btree_insertar(raiz, clave, orden):
  if raiz is None:
    raiz = BTreeNode(orden, True)
  if raiz.cuenta == 2 * raiz.orden - 1:
    nueva = BTreeNode(raiz.orden, False)
    nueva.hijos.append(raiz)
    dividir_hijo(nueva, 0, raiz)
    raiz = nueva
  insertar_no_lleno(raiz, clave)
  return raiz

La función insertar_no_lleno toma decisiones locales (descender o insertar en hoja) asumiendo que el nodo recibido tiene espacio. Esta estrategia top-down evita retroceder después de detectar un nodo lleno.

5.6 Código completo para VSCode

Ejemplo autocontenido en un solo archivo main.py listo para ejecutar en VSCode con python main.py:

class BTreeNode:
  def __init__(self, orden, es_hoja):
    self.claves = []
    self.hijos = []
    self.cuenta = 0
    self.es_hoja = es_hoja
    self.orden = orden

def dividir_hijo(padre, idx, hijo):
  t = hijo.orden
  nuevo = BTreeNode(t, hijo.es_hoja)
  clave_media = hijo.claves[t - 1]
  nuevo.claves = hijo.claves[t:]
  if not hijo.es_hoja:
    nuevo.hijos = hijo.hijos[t:]
  hijo.claves = hijo.claves[:t - 1]
  if not hijo.es_hoja:
    hijo.hijos = hijo.hijos[:t]
  hijo.cuenta = len(hijo.claves)
  nuevo.cuenta = len(nuevo.claves)
  padre.hijos.insert(idx + 1, nuevo)
  padre.claves.insert(idx, clave_media)
  padre.cuenta = len(padre.claves)

def insertar_no_lleno(nodo, clave):
  i = nodo.cuenta - 1
  if nodo.es_hoja:
    nodo.claves.append(0)
    while i >= 0 and clave < nodo.claves[i]:
      nodo.claves[i + 1] = nodo.claves[i]
      i -= 1
    nodo.claves[i + 1] = clave
    nodo.cuenta += 1
  else:
    while i >= 0 and clave < nodo.claves[i]:
      i -= 1
    i += 1
    if nodo.hijos[i].cuenta == 2 * nodo.orden - 1:
      dividir_hijo(nodo, i, nodo.hijos[i])
      if clave > nodo.claves[i]:
        i += 1
    insertar_no_lleno(nodo.hijos[i], clave)

def btree_insertar(raiz, clave, orden):
  if raiz is None:
    raiz = BTreeNode(orden, True)
  if raiz.cuenta == 2 * raiz.orden - 1:
    nueva = BTreeNode(raiz.orden, False)
    nueva.hijos.append(raiz)
    dividir_hijo(nueva, 0, raiz)
    raiz = nueva
  insertar_no_lleno(raiz, clave)
  return raiz

def imprimir_btree(nodo, nivel=0):
  if nodo is None:
    return
  for i, clave in enumerate(nodo.claves):
    if not nodo.es_hoja:
      imprimir_btree(nodo.hijos[i], nivel + 1)
    print("  " * nivel + str(clave))
  if not nodo.es_hoja:
    imprimir_btree(nodo.hijos[len(nodo.claves)], nivel + 1)

if __name__ == "__main__":
  t = 3
  raiz = None
  datos = [10, 20, 5, 6, 12, 30, 7, 17]
  for valor in datos:
    raiz = btree_insertar(raiz, valor, t)
  print(f"Inserciones completadas con t={t}")
  print("Recorrido in-order por niveles:")
  imprimir_btree(raiz)

Editor online