El AVL de la lección anterior es imbatible... mientras el árbol quepa en RAM. Pero imagina TaskFlow desplegado en una empresa con diez millones de tareas: el índice ya no cabe en memoria y vive en disco, y el disco cambia las reglas del juego — no se lee byte a byte sino por bloques de miles de bytes, y cada lectura cuesta decenas de miles de veces más que un acceso a RAM. De pronto, la métrica que importa no es "cuántas comparaciones hago" sino "cuántos bloques leo", y el árbol binario, con un mísero nodo por salto, lee un bloque casi entero para aprovechar unos pocos bytes. El árbol B invierte el diseño: nodos enormes, del tamaño exacto de un bloque, con cientos de claves e hijos cada uno — árboles bajísimos y anchísimos donde tres o cuatro lecturas bastan para encontrar una clave entre millones. En esta lección entenderás por qué existe, cómo funciona su inserción con división de nodos (con esquemas, no con una implementación completa), qué añade su variante B+ y dónde te lo encuentras cada día: en el índice de cualquier base de datos.

1. El disco cambia las reglas: bloques y coste de acceso
2. Qué es un árbol B: orden, propiedades e invariantes
3. Buscar en un árbol B
4. Insertar: crecer partiendo nodos (splits)
5. El árbol B+: datos en las hojas, hojas encadenadas
6. Dónde viven: bases de datos y sistemas de ficheros — TaskFlow sobre SQLite
7. ABB vs AVL vs B: la tabla comparativa

En el módulo 1 vimos la jerarquía de memoria de pasada; ahora nos toca la factura. Órdenes de magnitud (redondeados, pero fieles):

Y el matiz clave: el disco no vende bytes sueltos. Se lee por bloques (o páginas, típicamente 4-16 KB): pedir 8 bytes cuesta lo mismo que pedir los 4 096 del bloque entero. Dos consecuencias inmediatas:

• El coste de un algoritmo sobre disco se mide en número de bloques leídos, no en comparaciones. Las comparaciones dentro de un bloque ya cargado en RAM son gratis en comparación.
• Un buen algoritmo de disco debe aprovechar el bloque entero cada vez que paga por él.

Ahora mira el AVL con estas gafas. Diez millones de claves → altura ≈ 23. Cada salto de nodo a nodo es, en el peor caso, un bloque distinto (los nodos, creados en momentos distintos, viven dispersos): 23 lecturas de bloque para traer... 23 nodos minúsculos de unas decenas de bytes cada uno. En cada bloque de 4 KB pagado, aprovechamos quizá el 1 %. En un disco mecánico, 23 lecturas son un cuarto de segundo — para una búsqueda. El árbol binario es un diseño magnífico para RAM y un despilfarro para disco.

La idea que lo arregla es de una lógica aplastante: si el bloque viene entero de todos modos, llenémoslo de claves. Un nodo de 4 KB puede albergar cientos de claves y punteros a hijos; con cientos de hijos por nodo, la altura se desploma.

Un árbol B de orden m es un árbol de búsqueda donde cada nodo puede tener hasta m hijos. Sus propiedades:

• Cada nodo guarda hasta m − 1 claves ordenadas; un nodo interno con k claves tiene exactamente k + 1 hijos.
• Las claves de un nodo actúan de separadores: el hijo i contiene solo claves entre la clave i−1 y la clave i del padre — la generalización directa de "izquierda menor, derecha mayor" a muchos hijos.
• Todo nodo (salvo la raíz) está al menos medio lleno: como mínimo ⌈m/2⌉ − 1 claves. Nada de nodos raquíticos que desperdicien bloques.
• Todas las hojas están al mismo nivel: el árbol B está perfectamente equilibrado, siempre. Ni factores de equilibrio ni rotaciones: su mecanismo de crecimiento (lo veremos enseguida) hace imposible el desequilibrio.

Un árbol B de orden 4 (una "raíz" pedagógica de tamaño juguete): la raíz tiene 2 claves y 3 hijos; el hijo del medio contiene solo claves entre 20 y 40. En la práctica real, con bloques de 4-16 KB, el orden m ronda los cientos: y ahí está el milagro de la altura —

La altura crece como log_m(n), y con m = 200, log₂₀₀(10⁷) ≈ 3. Tres lecturas de bloque para encontrar una tarea entre diez millones (y en la práctica menos: la raíz y el segundo nivel se quedan cacheados en RAM). Frente a las 23 del AVL, es la diferencia entre un índice usable y uno que arrastra.

La búsqueda generaliza el descenso del ABB: en cada nodo, en lugar de una comparación y dos caminos, se busca la posición de la clave entre los separadores (dentro del nodo puede usarse búsqueda binaria — ¡el módulo 1 trabajando dentro de cada bloque!) y se desciende por el hijo del hueco correspondiente. Buscar 31 en el árbol del diagrama:

1. Raíz [20 | 40]: 31 está entre 20 y 40 → hijo del medio. (1 bloque leído)
2. Nodo [25 | 31 | 38]: 31 está aquí. Encontrada. (2 bloques leídos)

En pseudocódigo (esta lección trabaja con pseudocódigo y esquemas; la implementación completa de un árbol B — con su gestión de bloques, mínimos de ocupación y fusiones al borrar — es un proyecto de semanas que excede el nivel del curso, y en la práctica la escriben los motores de bases de datos, no las aplicaciones):

Coste: O(log_m n) lecturas de bloque, con O(log₂ m) comparaciones gratis dentro de cada una.

Aquí está la elegancia del árbol B. Las inserciones van siempre a una hoja (bajando como en la búsqueda), y la clave se acomoda en orden dentro de ella. ¿Y si la hoja ya está llena (tiene m − 1 claves)? Entonces se divide (split):

1. La hoja desbordada se parte en dos nodos, cada uno con la mitad de las claves.
2. La clave mediana no se queda en ninguno: sube al padre como nuevo separador entre los dos medios nodos.
3. Si con eso el padre desborda, el padre se divide igual... y la división puede propagarse hacia arriba. Si desborda la raíz, se divide y se crea una raíz nueva con una sola clave: es el único momento en que el árbol gana altura.

Veámoslo paso a paso, insertando 10, 20, 30, 40, 50 en un árbol B de orden 4 vacío (máximo 3 claves por nodo):

Pasos 1-3 — 10, 20, 30 caben en la raíz-hoja:

Paso 4 — llega el 40: la hoja tendría 4 claves. Split: se parte en [10] y [30|40], y la mediana 20 sube... pero no hay padre: se crea una raíz nueva.

Paso 5 — el 50 baja a la derecha y cabe: [30|40|50].

Paso 6 — insertemos 60: la hoja derecha desborda, se parte en [30] y [50|60], y la mediana 40 sube a la raíz, que tiene sitio:

Detente en el detalle que lo explica todo: el árbol B no crece hacia abajo, crece hacia arriba — las hojas se quedan donde están y es la raíz la que, muy de tanto en tanto, se eleva un piso. Por eso todas las hojas están siempre al mismo nivel: nacieron al mismo nivel y solo se reparten en horizontal. El equilibrio perfecto no se mantiene con rotaciones correctoras como en el AVL: es estructuralmente imposible desequilibrarlo. (El borrado es el proceso inverso — nodos que caen por debajo del mínimo se fusionan con hermanos o les piden claves prestadas — con la misma garantía.)

En pseudocódigo:

Un split cuesta O(m) (repartir claves entre dos bloques), y hay como mucho uno por nivel: inserción en O(log_m n) escrituras de bloque. Y la ocupación mínima del 50 % queda garantizada de fábrica: cada mitad de un split nace justo medio llena.

La variante que domina el mundo real es el árbol B+, con dos retoques sobre el árbol B:

• Los nodos internos solo guardan separadores (claves de guía, sin datos asociados); los datos completos viven exclusivamente en las hojas. Ventaja: sin datos que transportar, en cada bloque interno caben más separadores → mayor orden efectivo → árbol aún más bajo. (Consecuencia curiosa: las claves separadoras pueden aparecer duplicadas — una vez como guía arriba y otra con sus datos en la hoja.)
• Las hojas están encadenadas entre sí en una lista enlazada ordenada (¡el módulo 2 reapareciendo en la sala de máquinas de las bases de datos!).

Ese encadenamiento es oro para la consulta estrella de este módulo: el rango. En el ABB/AVL, rango(a, b) navegaba el árbol con podas; en el B+, se baja una sola vez hasta la hoja de a y después se avanza en línea recta por la cadena de hojas hasta pasarse de b — lecturas secuenciales de bloques contiguos, el patrón de acceso más barato que existe en disco. "Tareas con id entre 1 000 y 5 000": un descenso más un paseo. Por lo mismo, el recorrido completo en orden ni siquiera toca los nodos internos.

Los árboles B/B+ son, casi con seguridad, la estructura de datos que más veces usaste hoy sin saberlo:

• Bases de datos: los índices de SQLite, PostgreSQL, MySQL (InnoDB), Oracle y SQL Server son árboles B+ (o variantes muy próximas). Cada CREATE INDEX planta uno.
• Sistemas de ficheros: NTFS (Windows), APFS (Apple), Btrfs y ext4 (Linux) usan árboles B para directorios y metadatos — la jerarquía de carpetas de 06-01, indexada.

Cerremos el círculo con TaskFlow. El día que sus tareas se muden de nuestras estructuras en RAM a una base de datos:

Lee la segunda línea con los ojos de este módulo: (prioridad, id) es exactamente la clave compuesta que inventamos en 06-04 para el índice de urgencias — la base de datos y tú habéis llegado a la misma solución, porque es la misma pregunta. Y el SELECT final se ejecuta como acabamos de describir: descenso al primer (1, ...), paseo por las hojas encadenadas hasta pasar (3, ∞), resultados ya ordenados sin ordenar nada. Todo el módulo 6, servido en tres líneas de SQL — la diferencia es que ahora sabes qué hay debajo y por qué es rápido, que es lo que separa a quien usa una base de datos de quien la entiende.

La progresión del módulo, leída de corrido: el ABB aportó la idea (comparar y descartar), el AVL añadió la garantía (equilibrio mantenido), y el árbol B adapta ambas al hardware (la unidad de coste es el bloque). Misma lógica, tres hábitats.

• Medir un árbol de disco en comparaciones. La métrica correcta son las lecturas de bloque; dentro de un bloque en RAM, comparar es gratis a efectos prácticos. Confundir las métricas lleva a "optimizaciones" irrelevantes.
• Creer que la mediana se queda en una de las mitades del split. No: sube al padre como separador. Si en tus esquemas las cuentas de claves no cuadran, revisa esto — es el despiste número uno al trazar splits a mano.
• Pensar que el árbol B necesita rebalanceo tipo AVL. No hay rotaciones: crecer por arriba (split de raíz) mantiene todas las hojas al mismo nivel por construcción. Son dos filosofías de equilibrio distintas.
• Confundir B con B+. En el B clásico, los nodos internos también llevan datos; en el B+, solo separadores, y las hojas van encadenadas. Cuando leas "las bases de datos usan árboles B", casi siempre significa B+.
• Consejo práctico: la próxima vez que una consulta SQL con WHERE ... BETWEEN u ORDER BY vaya lenta, pregúntate si existe un índice B+ cuyas primeras columnas casen con la consulta (el orden de las columnas en el índice importa: es el orden de la tupla de 06-04). EXPLAIN te dirá si el motor lo está usando.

En un árbol B de orden 4 (máximo 3 claves por nodo) inicialmente vacío, inserta en este orden: 8, 5, 1, 7, 3, 12, 9, 6. Dibuja el árbol tras cada split, indicando qué clave sube. ¿Cuántos splits se producen y cuál es la altura final?

Un nodo de árbol B+ interno debe caber en un bloque de 4 096 bytes. Cada clave (id de tarea) ocupa 8 bytes y cada puntero a hijo otros 8. (a) ¿Qué orden máximo m admite el bloque? (b) Con ese m, ¿cuántas tareas indexa como máximo un árbol de altura 2 (raíz + 1 nivel interno + hojas, suponiendo hojas de hasta 255 entradas)? (c) ¿Qué altura necesitaría un árbol binario para esa cantidad?

Para cada escenario de TaskFlow, elige entre dict/TablaHash, ArbolAVL y árbol B+ (vía base de datos), y justifica en una frase con la métrica correcta: (a) caché en memoria de sesiones activas, consultada por token exacto; (b) índice en RAM de las 10 000 tareas del sprint por (prioridad, id), con listados por rango constantes; (c) historial completo de 20 millones de tareas archivadas, consultado por rangos de fechas.

Solución 1

• 8, 5, 1 llenan la raíz: [1|5|8].
• 7 desborda → split 1: mitades [1|5] y [8]... con mediana 7 subiendo a una raíz nueva. Ojo: las cuatro claves en juego ordenadas son 1, 5, 7, 8; se parten como [1|5], sube 7, queda [8]. Árbol: raíz [7], hijos [1|5] y [8].
• 3 baja a la izquierda: [1|3|5]. 12 baja a la derecha: [8|12]. 9: [8|9|12].
• 6 baja a la izquierda, que desborda (1, 3, 5, 6) → split 2: [1|3], sube 5, queda [6]. Raíz: [5|7] con hijos [1|3], [6], [8|9|12].

Total: 2 splits, altura final 1 (raíz + hojas). Comentario: fíjate en que las ocho claves quedaron repartidas con todas las hojas al mismo nivel y ninguna por debajo del mínimo (⌈4/2⌉ − 1 = 1 clave) — el invariante se mantuvo solo, sin que ninguna regla externa interviniera.

Solución 2

(a) Un nodo con k claves tiene k + 1 punteros: 8k + 8(k+1) ≤ 4096 → k ≤ 255. Orden m = 256. (b) Raíz con 256 hijos → 256 nodos internos → 256 × 256 = 65 536 hojas de hasta 255 entradas ≈ 16,7 millones de tareas con altura 2 (tres lecturas de bloque, y las dos primeras probablemente cacheadas). (c) Un árbol binario necesitaría altura ⌊log₂(16,7·10⁶)⌋ = 23. Comentario: la moraleja en una frase — mismo logaritmo, distinta base, y la base la dicta el tamaño del bloque: log₂₅₆ frente a log₂ es la diferencia entre 3 lecturas y 23.

Solución 3

(a) dict/TablaHash: clave exacta, sin necesidad de orden, todo en RAM — O(1) imbatible; un árbol pagaría un logaritmo a cambio de nada. (b) ArbolAVL: rangos y orden constantes en RAM con ids que llegan crecientes — el hash no sabe de rangos y el ABB degeneraría; el B+ sería sobreingeniería sin disco de por medio. (c) Árbol B+ (base de datos): 20 millones no caben cómodamente en RAM y la consulta es por rango — tres lecturas de bloque y paseo por hojas encadenadas; un AVL en disco haría ~24 saltos de bloque por descenso. Comentario: ninguna respuesta es "la mejor estructura en abstracto"; las tres son "la mejor para ese patrón de acceso en ese hábitat" — el criterio que desarrollaremos a fondo en el módulo 8.

El árbol B completa la escalera del módulo: cuando los datos se mudan a disco, la unidad de coste pasa de la comparación al bloque, y la respuesta es un árbol a la medida del bloque — nodos con cientos de claves, altura 3 o 4 para millones de elementos, equilibrio perfecto mantenido por splits que hacen crecer el árbol por la raíz, y en su variante B+, hojas encadenadas que convierten los rangos en lecturas secuenciales. Ahora sabes qué planta un CREATE INDEX y por qué el BETWEEN de TaskFlow sobre SQLite volará: es el mismo índice (prioridad, id) que tú construiste a mano, en versión industrial. Nos queda una promesa por cumplir, y es antigua: en el módulo 4 usamos heapq como caja negra para la BandejaUrgencias, jurando que algún día la abriríamos. Ese día es la próxima lección: el montículo, un árbol binario que renuncia al orden total del ABB a cambio de una sola cosa — tener siempre el mínimo a mano — y que, gracias a la representación en array de 06-02, ni siquiera necesita nodos. Vamos a abrir la caja.