← Volver a Programación II · ← Apunte de Árboles
Esta guía complementa la práctica de Árboles, en su parte de árboles B y B+. Son estructuras de búsqueda balanceadas pensadas para grandes volúmenes de datos almacenados en disco, donde lo caro no es comparar claves sino acceder a memoria (leer un bloque del disco).
En la teoría, al B+ se lo llama «B Mejorado»: es un árbol B con dos mejoras (una en la inserción y otra en la eliminación). No hay que confundirlo con otras variantes que se ven en bibliografía; acá seguimos el modelo de la cátedra.
Conviene leer primero el apunte de Árboles (ABB y AVL).
A lo largo de la guía usamos página como sinónimo de nodo (cada nodo es un bloque de disco) y rama para referirnos a cada hijo.
Un AVL es excelente en memoria, pero tiene un problema en disco: su altura es $O(\log_2 n)$ y cada nodo guarda una sola clave. Bajar un nivel del árbol implica leer un nodo nuevo, es decir, un acceso a disco. Con millones de claves, $\log_2 n$ accesos son demasiados.
La idea de los árboles B (Bayer y McCreight, 1970) es achatar el árbol: árboles de búsqueda multicamino, donde cada página guarda muchas claves y tiene muchas ramas. Así la altura crece como $\log_m n$ (con $m$ grande), y se necesitan muy pocos accesos a disco para llegar a cualquier clave. Cada página se dimensiona para coincidir con el tamaño de un bloque de disco.
Un árbol B de orden $m$ es un árbol de búsqueda 100% balanceado que cumple:
Árbol B de orden 5 (hasta 4 claves por página):
[ 10 | 20 ]
/ | \
[5|8] [12|18] [25|65|92|99]
Orden 5 ⇒ hasta 4 claves y 5 ramas por página; mínimo $\lceil 5/2 \rceil = 3$ ramas (2 claves) en las páginas que no son la raíz.
Se busca de forma similar a un ABB: se compara la clave buscada con las de la página actual para decidir por qué rama bajar; dentro de cada página la búsqueda es secuencial ordenada. Se repite hasta encontrar la clave o llegar a una hoja sin éxito. (Una optimización habitual: si la clave es mayor que la última de la página, se baja directamente por la rama más a la derecha.)
Siempre se inserta en una hoja (todas están al mismo nivel).
El árbol crece “desde las hojas hacia la raíz”, lo que mantiene todas las hojas al mismo nivel automáticamente.
$n$ = cantidad de claves; $m$ = orden del árbol.
| Operación | Complejidad | Notas |
|---|---|---|
| Buscar | $O(\log_m n)$ | Altura del árbol; cada nivel = 1 acceso a disco. |
| Insertar | $O(\log_m n)$ | Descenso + posibles splits hacia la raíz. |
| Eliminar | $O(\log_m n)$ | Descenso + posibles préstamos/fusiones hacia la raíz. |
Lo importante en disco es la cantidad de accesos = altura del árbol. Como $m$ es grande, $\log_m n$ es muy chico (pocos niveles aun para millones de claves).
El B+ introduce dos mejoras sobre el árbol B —una en la inserción y otra en la eliminación— con un mismo objetivo: mantener las páginas más llenas, para evitar divisiones y fusiones innecesarias y que el árbol crezca o decrezca de nivel lo menos posible. Ambas mejoras operan solo a nivel de las hojas.
Cuando una hoja se desborda, en lugar de dividirla de inmediato, primero se fija si una hoja hermana (la de la rama izquierda) tiene lugar para una clave más:
De esta forma se llenan todas las hojas antes de producir una división, lo que evita divisiones innecesarias y hace que el árbol no crezca un nivel hasta que todas las hojas estén llenas.
Orden 5 — insertar 56 (la hoja [25|65|92|99] está llena):
[ 10 | 20 ] [ 10 | 25 ]
/ | \ → / | \
[5|8] [12|18] [25|65|92|99] [5|8] [12|18|20] [56|65|92|99]
El hermano izquierdo [12|18] tiene lugar: baja el 20 del padre a esa hoja
y sube el 25 al padre. Queda lugar para el 56, sin dividir ninguna página.
Cuando al eliminar una clave la hoja queda por debajo del mínimo, antes de unir páginas se intenta balancear pidiendo prestada una clave, pero ahora probando tanto por la rama izquierda como por la derecha (el árbol B básico solo prueba con un hermano). Solo si ninguno de los dos hermanos puede prestar se fusionan páginas.
Esto es posible solamente a nivel de las hojas y siempre que la hoja sea una hoja intermedia (tenga hermanos a ambos lados).
Orden 5 — eliminar 10 de la hoja [10|18]:
[ 9 | 20 ] [ 9 | 65 ]
/ | \ → / | \
[5|8] [10|18] [65|92|99] [5|8] [18|20] [92|99]
Al sacar el 10, la hoja queda con menos del mínimo. El hermano izquierdo
[5|8] está en el mínimo y NO puede prestar; el derecho [65|92|99] SÍ:
baja el 20 del padre a la hoja y sube el 65 al padre. No hace falta unir.
Las complejidades asintóticas no cambian respecto del árbol B: búsqueda, inserción y eliminación siguen siendo $O(\log_m n)$. La mejora está en las constantes (menos accesos a disco por reorganización y mejor ocupación de las páginas).