Arboles B y B+ en Python - Operaciones en árboles B+

Las operaciones en un árbol B+ conservan la altura baja y explotan las hojas enlazadas para recorridos secuenciales rápidos. Las reglas de llenado y división son similares al B-Tree, pero la diferencia clave es que las claves se almacenan solo en hojas.

Visualizador interactivo de Árbol B+

8.1 Búsqueda

Se recorre desde la raíz comparando con las claves internas hasta llegar a una hoja.
La coincidencia se verifica solo en la hoja; los internos sirven como límites superiores.
Complejidad O(h) con altura típicamente 2 o 3 en índices reales.

8.2 Inserción

Se desciende hasta la hoja adecuada; si está llena, se divide antes de insertar.
La clave promovida al padre es la primera clave del nuevo nodo hoja derecho.
Se mantienen los enlaces entre hojas actualizando punteros de vecino al dividir.

8.3 Split en nodos hoja

Dividir una hoja llena (2t claves) crea dos hojas con t claves cada una:

La clave de promoción al interno padre es la menor clave del nuevo nodo derecho.
Los punteros de siguiente/anterior se ajustan para mantener la lista enlazada.
Los datos permanecen en hojas; los internos no almacenan registros.

8.4 Redistribución

Si un nodo hoja tiene déficit, puede tomar claves de un hermano con espacio (≥ t).
La clave separadora en el padre se actualiza para reflejar la nueva mínima del hijo derecho.
Redistribuir evita fusionar y mantiene la ocupación sin aumentar la altura.

8.5 Eliminación

Se borra en la hoja; si queda con menos de t - 1 claves, se redistribuye o fusiona con un hermano.
Si se fusiona, se elimina la clave separadora en el padre y se encadena la lista de hojas.
Si la raíz queda sin claves y tiene un solo hijo, ese hijo se convierte en la nueva raíz.

8.6 Recorrido eficiente por hojas enlazadas

Para un range scan se baja una vez por el árbol hasta la primera hoja en el rango.
Luego se itera hoja a hoja usando los punteros de enlace, sin volver a los nodos internos.
Esto ofrece complejidad O(h + k) para devolver k resultados consecutivos.

8.7 Código completo para probar en VSCode

Ejemplo autocontenido en main.py con inserción, búsqueda y recorrido por hojas enlazadas en un árbol B+:

ORDEN = 3
MAX_CLAVES = 2 * ORDEN - 1

class BPlusNode:
  def __init__(self, es_hoja):
    self.claves = []
    self.hijos = []
    self.siguiente = None
    self.cuenta = 0
    self.es_hoja = es_hoja

def crear_nodo(es_hoja):
  return BPlusNode(es_hoja)

def buscar_posicion(nodo, clave):
  i = 0
  while i < nodo.cuenta and clave > nodo.claves[i]:
    i += 1
  return i

def split_hoja(padre, idx, hijo):
  nuevo = crear_nodo(True)
  mid = hijo.cuenta // 2
  nuevo.claves = hijo.claves[mid:]
  hijo.claves = hijo.claves[:mid]
  hijo.cuenta = len(hijo.claves)
  nuevo.cuenta = len(nuevo.claves)

  nuevo.siguiente = hijo.siguiente
  hijo.siguiente = nuevo

  padre.hijos.insert(idx + 1, nuevo)
  padre.claves.insert(idx, nuevo.claves[0])
  padre.cuenta = len(padre.claves)

def split_interno(padre, idx, hijo):
  nuevo = crear_nodo(False)
  mid = hijo.cuenta // 2
  promover = hijo.claves[mid]

  nuevo.claves = hijo.claves[mid + 1:]
  nuevo.hijos = hijo.hijos[mid + 1:]
  nuevo.cuenta = len(nuevo.claves)

  hijo.claves = hijo.claves[:mid]
  hijo.hijos = hijo.hijos[:mid + 1]
  hijo.cuenta = len(hijo.claves)

  padre.hijos.insert(idx + 1, nuevo)
  padre.claves.insert(idx, promover)
  padre.cuenta = len(padre.claves)

def insertar_no_lleno(nodo, clave):
  pos = buscar_posicion(nodo, clave)
  if nodo.es_hoja:
    nodo.claves.insert(pos, clave)
    nodo.cuenta += 1
  else:
    hijo = nodo.hijos[pos]
    if hijo.cuenta == MAX_CLAVES:
      if hijo.es_hoja:
        split_hoja(nodo, pos, hijo)
      else:
        split_interno(nodo, pos, hijo)
      if clave >= nodo.claves[pos]:
        pos += 1
      hijo = nodo.hijos[pos]
    insertar_no_lleno(hijo, clave)

def bplus_insertar(raiz, clave):
  if raiz is None:
    raiz = crear_nodo(True)
    raiz.claves = [clave]
    raiz.cuenta = 1
    return raiz
  if raiz.cuenta == MAX_CLAVES:
    nueva = crear_nodo(False)
    nueva.hijos.append(raiz)
    if raiz.es_hoja:
      split_hoja(nueva, 0, raiz)
    else:
      split_interno(nueva, 0, raiz)
    raiz = nueva
  insertar_no_lleno(raiz, clave)
  return raiz

def bplus_buscar(nodo, clave):
  if nodo is None:
    return False
  pos = buscar_posicion(nodo, clave)
  if nodo.es_hoja:
    return pos < nodo.cuenta and nodo.claves[pos] == clave
  return bplus_buscar(nodo.hijos[pos], clave)

def imprimir_hojas(raiz):
  if raiz is None:
    return
  while not raiz.es_hoja:
    raiz = raiz.hijos[0]
  print("Hojas enlazadas:")
  actual = raiz
  while actual:
    print("[" + ", ".join(str(x) for x in actual.claves) + "] -> ", end="")
    actual = actual.siguiente
  print("NULL")

if __name__ == "__main__":
  datos = [10, 20, 5, 6, 12, 30, 7, 17, 3, 4, 15, 25, 27]
  raiz = None
  for valor in datos:
    raiz = bplus_insertar(raiz, valor)

  imprimir_hojas(raiz)

  consultas = [6, 22, 27]
  for clave in consultas:
    print(f"Buscar {clave} -> {'encontrado' if bplus_buscar(raiz, clave) else 'no'}")

Editor online

Retornar