Árboles B

Los árboles B son una adaptación de los árboles 2-3 a memoria externa, donde cada nodo se almacena en un bloque y entonces se ensancha el nodo a tamaño $B$ para aprovechar que el bloque se lee completo. Los nodos internos del árbol $B$ pueden almacenar hasta $(B-1)/2$ elementos (entendiendo que éstos requieren almacenar $(B-1)/2$ claves y $(B-1)/2+1$ punteros a los nodos hijos). Estas claves están replicadas en las hojas (esta variante, que suele ser la más conveniente, corresponde al llamado árbol B$+$). Las hojas pueden almacenar hasta $B$ elementos (pues no almacenan punteros), pero suelen almacenar también $B/2$ elementos para poder incorporar un puntero a los datos asociados a cada clave. Incluso pueden almacenar $B/c$ elementos, para alguna constante $c$, si se elige almacenar los datos asociados directamente en la hoja junto con la clave, para evitar otro acceso aleatorio en disco. Note que los "punteros" son aquí posiciones del archivo en disco donde se almacena el árbol B. Por simplicidad de exposición, diremos que los bloques tienen capacidad de almacenar hasta $B$ claves, tanto en las hojas como en los nodos internos.

Con una capacidad máxima de $B$ claves, el árbol B garantiza que los nodos, salvo la raíz, tienen al menos $B/2$ claves. Cada nodo interno con $k$ claves $y_1,\ldots,y_k$ tiene $k+1$ hijos $T_0,\ldots,T_k$. Todas las claves $y$ del subárbol $T_i$ cumplen $y_i < y \le y_{i+1}$ (entendiendo $y_0 = -\infty$ e $y_{k+1} = +\infty$). Todas las hojas del árbol B están al mismo nivel, por lo que su altura es $\Theta(\log_B N)$ (está entre $\log_B N$ y $1+\log_{B/2} N$).

El mecanismo de búsqueda de un elemento $x$ en el árbol B es una extensión clara del mecanismo del árbol 2-3. Se lee el nodo raíz, con sus claves $y_1,\ldots,y_k$, y se busca $x$ entre ellas (en forma binaria o secuencial, no hay diferencia en el modelo de memoria externa). Una vez determinado que $y_i < x \le y_{i+1}$, la búsqueda continúa en el subárbol $T_i$. La búsqueda requiere entonces leer $O(\log_B N)$ páginas de disco.

La inserción de un elemento comienza con una búsqueda, donde se identifica la hoja $H$ donde debería estar su clave. El elemento se agrega en la hoja, y si ésta se pasa del tamaño máximo $B$, se corta en dos hojas $H_1$ y $H_2$ de tamaño $B/2+1$ y $B/2$, respectivamente, y la mediana de las claves (que será la máxima clave almacenada en $H_1$) se inserta en el nodo padre $U$, que así reemplaza su antiguo hijo $H$ por dos hijos, $H_1$ y $H_2$, separados por la nueva clave. Si el padre $U$ se pasa del tamaño $B$, es decir pasa a tener $B+1$ claves y $B+2$ hijos, se repite la operación en forma casi idéntica: se corta en dos mitades $U_1$ y $U_2$ de $B/2$ claves y $B/2+1$ hijos, y la clave mediana se mueve hacia el padre $V$ de $U$, reemplazando el nodo $U$ por los nodos $U_1$ y $U_2$ que flanquean la nueva clave de $V$. Si $V$ a su vez se pasa del tamaño máximo, se repite el procedimiento de rebalse de nodos internos. Si finalmente esto ocurre en la raíz, se crea una nueva raíz del árbol con sólo 2 hijos, y la altura del árbol crece en 1.

Para el borrado, se elimina al elemento de la hoja. La clave borrada no necesita eliminarse de los nodos internos, aunque ya no exista más. Si la hoja pasa a tener menos de $B/2$ elementos, entonces se une con su anterior o siguiente hermana, y la clave que las separa en el padre se elimina. Si esto hace que el padre tenga menos de $B/2$ elementos, se repite el proceso de forma similar. La diferencia al unir dos nodos internos es que la clave que los separa en el nodo del padre se baja al nuevo nodo, para separar el último hijo del nodo izquierdo del primero del nodo derecho que se unen. Eventualmente se puede llegar a la raíz, que no requiere tener $B/2$ elementos. Sin embargo, si la raíz queda con cero elementos (y un hijo), se elimina y el hijo pasa a ser la raíz, con lo que el árbol B pierde altura.

En el borrado puede ocurrir que, cuando unimos un nodo con su hermano, el nodo resultante tenga más de $B$ elementos. En ese caso debemos volver a cortar el nodo que hemos creado, por su nueva mediana, y volver a insertar una nueva clave en el padre. En la práctica, esto implica que las claves se redistribuyen entre los nodos hermanos y la clave del padre que los separa se modifica. Cuando esto ocurre, el borrado no necesita seguirse propagando hacia arriba.

Como puede verse, tanto la inserción como el borrado cuestan $O(\log_B N)$ operaciones de I/O. El árbol B garantiza un porcentaje mínimo de ocupación de las páginas de disco de 50%. Si los datos se insertan en forma uniformemente aleatoria, el porcentaje promedio de ocupación es de 69%.

Con algunas técnicas más refinadas para evitar cortar hojas cuando rebalsan, la ocupación puede sobrepasar el 80% promedio.

Por otro lado, note que podríamos mantener los primeros $\Theta(\log_B M)$ niveles del árbol B en memoria principal, de modo que la cantidad de I/Os para búsquedas y modificaciones se reduciría a $O(\log_B \frac{N}{M})$.

📄️ Cota inferior

El costo de búsqueda de $O(\log_B \frac{M})$ es óptimo si se busca mediante