El presente artículo ofrece una amplia explicación acerca de la utilización de los árboles B y sus diferentes variantes, en el manejo de grandes volúmenes de información, utilizando memoria externa. En el mismo se detalla cómo se realizan cada una de las operaciones en los diferentes tipos de árboles.

Arbol B, Arbol B+, Arbol B*

En el manejo de grandes volúmenes de información, siempre ha estado presente la necesidad de hacer eficiente el proceso de búsqueda.

A menudo se usan árboles binarios de búsqueda para ordenar listas de valores, minimizando el número de lecturas, y evitando tener que ordenar dichas listas.

Pero este tipo de árboles tienen varias desventajas:

1. Es difícil construir un árbol binario de búsqueda perfectamente equilibrado.
2. El número de consultas en el árbol no equilibrado es impredecible.
3. Y además el número de consultas aumenta rápidamente con el número de registros a ordenar.

Para resolver estas desventajas, pudiera pensarse en el uso de árboles balanceados, por ejemplo AVL, pero ¿Qué ocurriría si el volumen de la información es tal que no pueda mantenerse en memoria? En este caso, a la preocupación de ganar eficiencia en la búsqueda, se le suma la necesidad de resolver los inconvenientes de reiterados accesos a disco. Utilizando un árbol AVL, el uso del disco es muy deficiente: cada acceso implica leer un bloque de memoria y de este bloque únicamente se utiliza un registro, cuyos índices de izquierda y derecha apuntan, con mucha probabilidad, a un registro de otro bloque.

Cuando el volumen de la información a procesar tiene un tamaño tal que nos conduce a la utilización de ficheros para el almacenamiento de los datos, se hace necesario pensar en otras estructuras que resuelvan los inconvenientes anteriores

Un árbol de búsqueda es un tipo especial de árbol que sirve para guiarla búsqueda de un registro, dado el valor de uno de sus campos. Un árbol de búsqueda de orden p es un árbol tal que cada nodo contiene, cuando más, p-1 valores de búsqueda y p apuntadores en el orden <P₁, k₁, P₂, k₂, …, P_q-1, K_q-1, P_q> , donde q <= p, cada P_i es un apuntador a un nodo hijo (o apuntador nulo) y cada K_i es un valor de búsqueda proveniente de algún conjunto ordenado de valores. Se supone que todos los valores de búsqueda son únicos. Un árbol de búsqueda debe cumplir, en todo momento, las siguientes restricciones:

1. Dentro de cada nodo K₁ < K₂ < ….< K_q-1
2. Para todos los valores de X, del subárbol al cual apunta P_{i ,} tenemos que K_i-1 < X < K_i , para 1 < i < q; X < K_i , para i = 1 y X > K_i-1 para i = q.

La figura 1 muestra un nodo de un árbol de búsqueda. En ella se pueden apreciar de manera más clara, las condiciones que impone la restricción 2.

Al buscar, insertar o eliminar un valor X siempre se sigue el puntero P_i apropiado, de acuerdo con las condiciones de la segunda restricción.

Podemos usar un árbol de búsqueda como mecanismo para buscar registros almacenados en un archivo de disco. Los valores del árbol pueden ser los valores de uno de los campos del registro, el llamado campo de búsqueda o llave. Cada valor del árbol está asociado a un apuntador de registro que tiene ese valor en el archivo de datos. Como alternativa, puede apuntar al bloque de disco que contiene ese registro.

El árbol de búsqueda en sí puede almacenarse en disco, asignando cada nodo del árbol a un bloque del disco. Cuando se inserta un registro nuevo, es preciso actualizar el árbol de búsqueda incluyendo en él el valor del campo de búsqueda del nuevo registro y un apuntador a este.

Para insertar valores de búsqueda en el árbol y eliminarlos, sin violar las restricciones anteriores, se utilizan algoritmos que no garantizan que el árbol de búsqueda esté equilibrado (que todas las hojas estén al mismo nivel).

Es importante mantener equilibrados los árboles de búsqueda porque esto garantiza que no habrá nodos en niveles muy profundos que requieran muchos accesos a bloques durante una búsqueda. Además, las eliminaciones de registros pueden hacer que queden nodos casi vacíos, con lo que hay un desperdicio de espacio importante que también provoca un aumento en el número de niveles y un menor aprovechamiento de los accesos a disco.

El árbol B es un árbol de búsqueda, con algunas restricciones adicionales, que resuelve hasta cierto punto los dos problemas anteriores. Estas restricciones adicionales garantizan que el árbol siempre estará equilibrado y que el espacio desperdiciado por la eliminación, si lo hay, nunca será excesivo. Los algoritmos para insertar y eliminar se hacen más complejos para poder mantener estas restricciones. No obstante, la mayor parte de las inserciones y eliminaciones son procesos simples, se complican sólo en circunstancias especiales.

De manera más formal, un Árbol B de orden p, utilizado como estructura de acceso según un campo clave para buscar registros en un archivo de datos, cumple que:

1. Cada nodo interno del árbol B tiene la forma (Ver Fig. 2)

<P₁, <k_1, Pr₁>, P₂, <k_2, Pr₂> , …, <kq-1_, Pr_q-1>, P_q>

donde q <= p. Cada P_i es un apuntador de árbol: un apuntador a otro nodo del árbol. Cada P_ri es un apuntador de datos: un apuntador al registro cuyo valor del campo clave de búsqueda es igual a K_i (o un apuntador al bloque que contiene ese registro de datos)

2. Dentro de cada nodo K₁ < K₂ < ….< K_q-1

1. Para todos los valores de X, del subárbol al que apunta P_{i ,} tenemos que K_i-1 < X < K_i , para 1 < i < q; X < K_i , para i = 1 y X > K_i-1 para i = q.
2. Cada nodo tiene, cuando más, p apuntadores de árbol.
3. Cada nodo, excepto la raíz y los nodos hoja, tienen por lo menos p/2 apuntadores de árbol. El nodo raíz tiene, como mínimo, dos punteros a nodos del árbol, a menos que sea el único nodo del árbol.
4. Un nodo con q apuntadores de árbol, q <= p, tiene q-1 valores del campo clave de búsqueda y por tanto, tiene q-1 apuntadores de datos.
5. Todos los nodos hojas están en el mismo nivel. Los nodos hoja tienen la misma estructura que los internos, excepto que todos sus apuntadores de árbol, P_i , son nulos.

Nota: Por una cuestión de simplicidad de los gráficos, en lo adelante solo se representarán los apuntadores de árboles.

A continuación se muestran dos árboles. Uno de ellos es un árbol B, en cambio, el otro no. El árbol de la figura 3.1 es un árbol B "correcto", pues cumple con todas las reglas en cuanto a su estructura y orden. En cambio, el de la figura 3.2 no es un árbol B, ya que a pesar de mantener el orden, hay una página (que no es la raíz) que tiene menos de p/2 elementos (en este caso menos de 5/2 elementos). Esta página es la que contiene al elemento 10.

El número de acceso a disco en un árbol B es proporcional a la altura del árbol, el caso peor para la altura es cuando la raíz tiene una sola llave y el resto de los nodos tiene el mínimo permitido p/2.

La siguiente figura nos muestra la cantidad de nodos por cada nivel del árbol donde t=p/2.

Generalizando, para un árbol de altura h, la cantidad de nodos que tiene el último nivel sería 2t^h-1.

La cantidad de nodos n, que tiene un árbol B cumple con lo siguiente:

Obtenemos que:

entonces el crecimiento del árbol es O(log_t n).

Las operaciones básicas que se pueden realizar en un árbol B son básicamente tres:

1. Buscar una llave
2. Insertar una llave
3. Eliminar una llave

La búsqueda de una llave Y se realiza de manera análoga a la búsqueda en un árbol binario de búsqueda. Se comienza buscando por el nodo raíz y se compara la llave Y con las llaves K_i que se encuentran en ese nodo. Si Y es igual a algún K_i, termina la búsqueda satisfactoriamente, si no, se debe seguir el puntero adecuado hacia un nodo hijo en el que se continuará la búsqueda. El puntero seleccionado será P₁, si Y < K₁, P_q si Y > K_q-1 y P_i, si K_i-1 < X < K_i, para 1 < i < q. En caso que el P_i correspondiente sea nulo, la búsqueda termina insatisfactoriamente.

En la búsqueda en un árbol B el número de acceso a página es (h) = (log_t n) donde h es la altura del árbol, n la cantidad de llaves, n<p y t=p/2. La búsqueda lineal de la llave en una página es O(t) por lo tanto el tiempo total es O(t*h)=O(t*log_tn).

Para realizar la inserción, lo primero que debe hacerse es un proceso de búsqueda, para localizar el nodo en el que se va a insertar. Si este proceso de búsqueda da por resultado que el elemento ya existe, no se realizará ninguna operación, pues el árbol B no permite elementos repetidos.

La búsqueda de un elemento inexistente y que, por tanto, pueda ser insertado en el árbol, terminará en el momento en que, tratando de buscar un puntero P_i que apunte al nodo donde debería estar el elemento, encontremos un puntero nulo, siendo insertado el nuevo elemento en el nodo actual. Cuando se inserta en un nodo que no está lleno, solo debemos preocuparnos por el lugar que debe ocupar la nueva llave en ese nodo y hacer un corrimiento de las restantes.

En problema surge cuando ya se han insertado varias llaves en un mismo nodo hasta que este queda completo. Una vez lleno un nodo con p-1 valores de la clave de búsqueda, si intentamos insertar una entrada más en él, debemos seguir el siguiente procedimiento:

1. Insertar la llave como si realmente tuviese sitio libre.
2. Extraer el nodo que ocupa la posición del medio e insertarlo en la página padre. Si no hubiese página padre se crearía una nueva página con ese nodo.
3. Dividir equitativamente la página original en dos nuevas páginas Estas páginas serán los hijos derechos e izquierdos del nodo que promocionó a la página superior.
4. Si la página a la que promociona el nodo mediano también se encuentra completa, se repetiría la misma operación de división y promoción.

La división puede propagarse hasta llegar al nodo raíz. En caso que el nodo raíz deba dividirse también, el elemento que es promocionado para ser insertado en el padre, será insertado en un nuevo nodo que se debe crear, que pasará a ser la nueva raíz del árbol, creando un nuevo nivel cada vez que se divida la raíz..

Es importante hacer notar la curiosa manera de crecer en altura que tienen los árboles B, que lo hacen hacia la raíz, a diferencia de los comúnmente utilizados, cuyas inserciones se realizan en forma de hojas y por tanto crecen en sentido inverso al árbol B. Esto es muy importante, porque garantiza que en el árbol B, todas las hojas estén en el mismo nivel y por tanto, esté balanceado.

Veamos algunos ejemplos:

Ej. 1 Supongamos que queremos insertar la clave 52 en el árbol siguiente.

No hay espacio para almacenar la clave en nodo, por lo tanto, este nodo debe dividirse, promocionando la llave que queda en el medio, en este caso, el 65:

Ahora tenemos que promocionar la clave intermedia, insertándola en el nodo padre. Como la llave promocionada, pudo insertarse sin dificultad en el nodo padre, el proceso termina.

En primer lugar, dividimos nodo en dos, repartimos las claves y promocionamos el valor intermedio, el 69:

Ahora estamos de nuevo en la misma situación, cuando tratamos de insertar el 69 en el nodo padre, pues este no cabe en dicho nodo, luego, el anterior nodo pasa a ser el nodo padre, y el padre de éste es null. Ahora procedemos igual, dividimos nodo en dos, separamos las claves, y promocionamos el valor intermedio:

Y otra vez repetimos el proceso, al tratar de insertar el 65 en el nodo padre del nodo que se dividió, vemos que este no existe, porque el nodo que se acaba de dividir era la raíz. En este caso, se crea un nuevo nodo en el que se inserta la llave promovida y se actualizan los punteros. Note la variación en la altura del árbol y su crecimiento hacia la raíz.

En la inserción en un árbol B el número de acceso a página es donde h es la altura del árbol, n la cantidad de llaves, n<p y t=p/2. La búsqueda lineal de la llave en una página es O(t) por lo tanto el tiempo total es O(t*h)=O(t*log_tn).

El proceso de eliminación puede llegar a ser algo más complejo que la inserción. La eliminación siempre debe realizarse en una hoja. Si después de realizarla búsqueda, el nodo a borrar no estuviese en una hoja, de la misma manera que se procede en un árbol binario de búsqueda, el nodo a borrar se sustituiría por su antecesor o sucesor, que sí debe estar en una hoja.

Al hacer la sustitución, caemos en el caso de la eliminación de una llave de un nodo hoja, la que ya fue replicada.

El caso más sencillo se produce cuando al eliminar un nodo de una página hoja, bien porque sea el nodo a eliminar, bien porque sea un elemento que sustituyó al nodo a eliminar, el tamaño de la página sigue siendo al menos p/2. De esta forma, la estructura del árbol se sigue cumpliendo y no hay que realizar ninguna reestructuración.

El problema surge cuando al eliminar un nodo de la hoja, la página se queda con menos del mínimo número de nodos permitidos. Si la eliminación de un valor hace que un nodo quede ocupado hasta menos de la mitad, este le "pedirá prestado un elemento" a uno de sus hermanos, o el izquierdo o el derecho. Si el hermano está en condiciones de ceder un elemento, o sea, si al perder dicho elemento no hace que quede ocupado a menos de la mitad, cederá el elemento más a la izquierda o más a la derecha, en dependencia de su ubicación respecto al hermano.

Esta "donación", debe realizarse con participación del nodo padre. El elemento donado, debe intercambiarse con el valor K_i correspondiente en el nodo padre y es este valor K_i quien iría a suplir la falta en el hermano afectado. En este caso, pudiera adoptarse la variante de chequear primero si el hermano derecho tiene la posibilidad de donar una llave y en caso negativo, pasar a chequear si el hermano izquierdo puede, pero esto provocaría un nuevo acceso a disco y por tanto, es preferible chequear solamente a uno de los dos hermanos.

Aún resta un caso más. Este caso es idéntico al anterior, pero ahora la página vecina tiene el número mínimo de nodos y por tanto, no existe la posibilidad de suplir la falta de llave tomando una llave del hermano En esta situación se produce el efecto inverso a la división, las dos páginas se agrupan en una sola, formando una nueva página en la que todavía existe capacidad para otra llave. A esta página se le añade la llave K_i que estaba situada en la página padre, entre ambos nodos. Si al fundirse los dos nodos y tomar la llave K_i de su padre, este se queda con una cantidad de llaves menor que p/2, el proceso se repite, propagándose hasta la raíz.

En caso de ser la raíz el nodo al que se le quitará el K_i y esta solo tenía una llave, queda automáticamente eliminada, reduciéndose en 1 la altura del árbol. Note que, del mismo nodo que el árbol B crece hacia la raíz, este tipo de árbol se acorta también desde la raíz, garantizándose así que todas las hojas, estén al mismo nivel.

Veamos algunos ejemplos de eliminación:

Tan sólo tendremos que eliminar la clave:

Según el algoritmo debemos sustituir la clave por el siguiente valor, es decir, el 25.

Ahora estamos en el mismo caso que antes, sólo hay que borrar la clave 25 del nodo hoja:

Ej. 3 Pasemos a eliminar ahora el elemento 12 del árbol:

La primera parte es fácil, bastará eliminar la clave, pero el resultado es que sólo queda una clave en el nodo, y debe haber al menos dos claves en un nodo de cuatro.

Según el algoritmo, buscaremos en el hermano derecho. Si el número de claves en el nodo derecho es mayor que el mínimo, pasaremos una clave del nodo derecho al padre y de éste al nodo hoja, en este caso, el 25 pasa al nodo padre y el 20 pasa al nodo que tenía el déficit.

La primera parte es igual que el caso anterior, eliminamos la clave 5. Pero ahora el nodo derecho tiene el número mínimo de claves.

Según el algoritmo, debemos fundir en el nodo hoja, las claves del nodo hoja, la clave del padre y las del nodo derecho. Y después eliminar el nodo derecho.

La cosa no termina ahí, ahora debemos comprobar el nodo padre, ya que también ha podido quedar con menos claves que el mínimo exigido. En este caso sucede eso, pero es un caso especial, ya que ese nodo es raíz y puede contener menos claves que número mínimo.

Borraremos la clave 65 de este árbol:

El primer paso es sustituir la clave 65 por la siguiente, la 67:

A continuación eliminamos la clave 67 del nodo hoja, y comprobamos que el nodo tiene menos claves del mínimo. Buscamos el nodo derecho

El nodo derecho tiene justo el número mínimo de claves, por lo tanto tenemos que fusionar hoja con derecho y con una clave de padre. Y eliminamos el nodo derecho.

Ahora el nodo hoja es el padre del anterior nodo hoja. De nuevo comprobamos que tiene menos claves que el mínimo, así que buscamos el nodo derecho, como no existe, buscamos el izquierdo. Y de nuevo comprobamos que el izquierdo tiene justo el número mínimo de claves.

Ahora fusionamos en el nodo izquierdo con el nodo hoja y con una clave del nodo padre, y eliminamos el nodo hoja, como además el nodo padre es la raíz y ha quedado vacía, lo eliminaremos y el nodo raíz será el izquierdo:

En la eliminación en un árbol B el número de acceso a página es donde h es la altura del árbol, n la cantidad de llaves, n<p y t=p/2. La búsqueda lineal de la llave en una página es O(t) por lo tanto el tiempo total es O(t*h)=O(t*log_tn).

Como se puede observar, en los árboles B todos los valores del campo de indexación aparecen alguna vez en algún nivel del árbol, junto con un puntero al fichero de datos.

En un árbol B+ los punteros a datos se almacenan sólo en los nodos hoja del árbol, por lo cual, la estructura de los nodos hoja difiere de la de los nodos internos.

Los nodos hoja tienen una entrada por cada valor del campo de indexación, junto con un puntero al registro del fichero de datos (o al bloque que contiene el registro). Estos nodos están enlazados para ofrecer un acceso ordenado a los registros a través del campo de indexación. Los nodos hoja de un árbol B+ son similares al primer nivel (nivel base) de un índice*. Los nodos internos del árbol B+ corresponden a los demás niveles del índice. Algunos valores del campo de indexación se repiten en los nodos internos del árbol B+ con el fin de guiar la búsqueda.

* Los índices multinivel cumplen que los índices de primer nivel contienen claves con apuntadores al fichero de datos y los índices de otros niveles sirven para indexar a los anteriores.

La estructura de los nodos internos del árbol B+ de orden p se define como sigue(Fig 4):

1. Todo nodo interno es de la forma <P₁, k₁, P₂, k₂, …, P_q-1, K_q-1, P_q> , donde q <= p, cada P_i es un apuntador de árbol.
2. Dentro de cada nodo interno K₁ < K₂ < ….< K_q-1
3. Para todos los valores X, del campo de búsqueda en el subárbol al cual apunta P_{i ,} tenemos que K_i-1 <= X < K_i , para 1 < i < q; X < K_i , para i = 1 y X >= K_i-1 para i = q. En este caso pudiera encontrarse una X igual a K y debe seguirse hacia abajo, hasta llegar a un nodo hoja.
4. Cada nodo interno tiene, cuando más, p apuntadores de árbol.
5. Cada nodo interno, excepto la raíz y los nodos hoja, tienen por lo menos p/2 apuntadores de árbol. El nodo raíz tiene, como mínimo, dos punteros a nodos del árbol, si es un nodo interno
6. Un nodo interno con q apuntadores de árbol, q <= p, tiene q-1 valores del campo de búsqueda

La estructura de los nodos hojas de un árbol B+ de orden p se define como sigue(Fig 5):

1. Todo nodo hoja tiene la forma:

<<k_1, Pr₁>, <k_2, Pr₂> , …, <kq-1_, Pr_q-1>, P_siguiente,> donde q<=p, cada P_ri es un apuntador de datos y P_siguiente apunta al siguiente nodo hoja del árbol B+.

2. Dentro de cada nodo hoja K₁ < K₂ < ….< K_q-1, donde q<=p
3. Cada nodo hoja tiene al menos p/2 valores
4. Todos los nodos hoja están en el mismo nivel

Como las entradas en los nodos internos de los árboles B+ contienen valores del campo de indexación y punteros a nodos del árbol, pero no contienen punteros a los registros del fichero de datos, es posible ``empaquetar" más entradas en un nodo interno de un árbol B+ que en un nodo similar de un árbol B. Por tanto, si el tamaño de bloque (nodo) es el mismo, el orden p será mayor para el árbol B+ que para el árbol B.

Esto puede reducir el número de niveles del árbol B+, mejorándose así el tiempo de acceso. Como las estructuras de los nodos internos y los nodos hoja de los árboles B+ son diferentes, su orden p puede ser diferente.

Se ha demostrado por análisis y simulación que después de un gran número de inserciones y eliminaciones aleatorias en un árbol B, los nodos están ocupados en un 69% cuando se estabiliza el número de valores del árbol. Esto también es verdadero en el caso de los árboles B+. Si llega a suceder esto, la división y combinación de nodos ocurrirá con muy poca frecuencia, de modo que la inserción y la eliminación se volverán muy eficientes.

La operación de búsqueda en árboles-B+ es similar a la operación de búsqueda en árboles-B. El proceso es simple, sin embargo puede suceder que al buscar una determinada clave la misma se encuentre en un nodo raíz o interior, en dicho caso no debe detenerse el proceso, sino que debe continuarse la búsqueda con el nodo apuntado por la rama derecha de dicha clave.

Por ejemplo, al buscar la clave 55 en el árbol-B+ de la figura 6 se advierte que esta se encuentra en el nodo raíz. En este caso, debe continuarse el proceso de búsqueda en el nodo apuntado por la rama derecha de dicha clave, o sea, si se encuentra la clave K_i-1, debemos continuar la búsqueda por el apuntador P_{i .}

El proceso de inserción en árboles-B+ es relativamente simple, similar al proceso de inserción en árboles-B. La dificultad se presenta cuando desea insertarse una clave en un nodo que se encuentra lleno. En este caso, el nodo afectado se divide en 2, distribuyéndose las claves de la siguiente forma: " las p/2 primeras claves en el nodo de la izquierda y las p/2 + 1 restantes claves en el nodo de la derecha". Una copia de la clave del medio sube al nodo padre. En la figura 7 hay dos diagramas que ilustran como funciona este caso.

Puede suceder que el nodo padre se desborde nuevamente, entonces tendrá que repetirse el proceso anterior. Es importante notar que el desbordamiento en un nodo que no es hoja no produce duplicidad de claves. El proceso de propagación puede llegar hasta la raíz, en cuyo caso la altura del árbol puede incrementarse en una unidad.

En la figura 8 se presentan dos diagramas que muestran este caso.

Supóngase que se desea insertar las siguientes claves en un árbol-B+ de orden 5 que se encuentra vacío:

claves: 10-27-29-17-25-21-15-31-13-51-20-24-48-19-60-35-66

Los resultados parciales que ilustran el crecimiento del árbol se presentan en los siguientes diagramas correspondientes a la figura 9

La operación de eliminación en árboles-B+ es mas simple que en árboles-B. Esto ocurre porque las claves a eliminar siempre se encuentran en las paginas hojas. En general deben distinguirse los siguientes casos:

1. Si al eliminar una clave, la cantidad de llaves queda mayor o igual que p/2 entonces termina la operación. Las claves de los nodos raíz o internos no se modifican por más que sean una copia de la clave eliminada en las hojas. (Se presenta un ejemplo de este caso en la figura 10).
2. Si al eliminar una clave, la cantidad de llaves queda menor que p/2 entonces debe realizarse una redistribución de claves, tanto en el índice como en las paginas hojas. (Hay dos ejemplos que ilustran como funciona este caso en las figuras 11 y 12 ).

Nota: Al eliminar la clave 27 de la página A, la cantidad de llaves queda menor que p/2 por lo que debe realizarse una redistribución de las claves. Se toma la clave que se encuentra más a la derecha en la rama izquierda de 25 (21 de la página B). Se coloca dicha clave en la página A y una copia de la misma, como índice, en la página C. (Se le llama página a un nodo)

Nota: Al eliminar la clave 21 de la página A, la cantidad de llaves queda menor que p/2 por lo que debe realizarse una redistribución de claves. Como no se puede tomar una clave de la página B puesto que m quedaría menor a d, entonces se realiza una fusión de las páginas A y B.

Puede suceder que al eliminar una clave y al realizar una redistribución de las mismas, la altura del árbol disminuya en una unidad. (En la figura 13 se presentan dos diagramas que muestran este caso).

Nota: Al eliminar la clave 37 de la página A, la cantidad de llaves queda menor que p/2 por lo que debe realizarse una redistribución de claves. Como no puede tomarse una clave de la página B puesto que m quedaría menor a d, entonces se realiza una fusión de las páginas A y B. Sin embargo, luego de está fusión la cantidad de llaves queda menor que p/2 en la página C, por lo que debe bajarse la clave 29 de la página E y realizarse una nueva fusión, ahora de las páginas C y E. La altura del árbol disminuye en una unidad.

El Árbol B* es un caso particular de Árbol B, al que se le adiciona la restricción de que todos los nodos se mantienen 2/3 llenos, o sea, la cantidad de llaves en cada nodo no puede ser menor que (2/3)p. Esta condición favorece que se aprovechen los accesos a disco, pues cada nodo está obligado a permanecer más lleno que los del árbol B.

Otra particularidad del Árbol B*, que lo distingue del Árbol B, es que el nodo raíz puede tener hasta (4/3)p llaves. Esta salvedad surge producto de que si se restringe a este nodo a tener a lo sumo p-1 llaves, al insertar una nueva llave, deberíamos proceder a dividir el nodo en dos nodos, que no cumplirían con la condición de tener al menos (2/3)p llaves.

Esto se comprenderá mejor en lo adelante, cuando se expliquen las operaciones básicas en este tipo de árboles.

De manera más formal, un Árbol B*, de orden p, cumple que:

1. Cada nodo interno del árbol B tiene la forma (Ver Fig. 2)

<P₁, <k_1, Pr₁>, P₂, <k_2, Pr₂> , …, <kq-1_, Pr_q-1>, P_q>

donde q <= p. Cada P_i es un apuntador de árbol: un apuntador a otro nodo del árbol. Cada P_ri es un apuntador de datos: un apuntador al registro cuyo valor del campo clave de búsqueda es igual a K_i (o un apuntador al bloque que contiene ese registro de datos)

2. Dentro de cada nodo K₁ < K₂ < ….< K_q-1

1. Para todos los valores de X, del subárbol al que apunta P_{i ,} tenemos que K_i-1 < X < K_i , para 1 < i < q; X < K_i , para i = 1 y X > K_i-1 para i = q.
2. Cada nodo, excepto la raíz, tiene, cuando más, p apuntadores de árbol. La raíz puede contener hasta (4/3)p + 1 apuntadores.
3. Cada nodo, excepto la raíz y los nodos hoja, tienen por lo menos (2/3)p +1 apuntadores de árbol. El nodo raíz tiene, como mínimo, dos punteros a nodos del árbol, a menos que sea el único nodo del árbol.
4. Un nodo con q apuntadores de árbol, q <= p, tiene q-1 valores del campo clave de búsqueda y por tanto, tiene q-1 apuntadores de datos.
5. Todos los nodos hojas están en el mismo nivel. Los nodos hoja tienen la misma estructura que los internos, excepto que todos sus apuntadores de árbol, P_i , son nulos.

La búsqueda en el Árbol B* se realiza de misma manera que en el B.

La inserción en un árbol B* se realiza del mismo modo que en el árbol B, siempre y cuando exista capacidad en el nodo para colocar la nueva llave. La diferencia está en el momento en que se va a insertar un elemento en un nodo que ya está lleno.

La manera de proceder en caso de insertar un elemento en un nodo lleno, varía si dicho nodo es la raíz o si es un nodo hoja. Note que cuando se habla de una inserción en la raíz es o porque la raíz es el único nodo del árbol y el nuevo elemento debe ser insertado en ella o porque la inserción en una hoja, provocó la promoción de una llave para ser insertada en el padre y esta promoción se propagó hasta la raíz.

Cuando se va a insertar en la raíz del árbol y está llena, caso en que ocurre un crecimiento en la altura del árbol, se procede de la manera siguiente:

1. Insertar la llave como si realmente tuviese sitio libre.
2. Crear un nuevo nodo, que pasará a ser la raíz del árbol. Extraer el nodo que ocupa la posición del medio en el nodo en que se insertó e insertarlo en la nueva raíz.
3. Dividir equitativamente la página original en dos nuevas páginas Estas páginas serán los hijos derecho e izquierdo del nodo que promocionó a la página superior.

Es importante hacer notar que esto sucede solo en el momento en que la raíz, producto de la inserción, excede las (4/3)p llaves, lo cual garantiza que al dividirse en dos el nodo original, en cada nodo queden las (2/3)p llaves que necesita un nodo del árbol B*.

Cuando va a insertarse en un nodo hoja y está lleno se procede de la siguiente manera:

1. Insertar la llave como si hubiese capacidad.
2. Chequear si en el hermano izquierdo o derecho existe capacidad y en caso positivo se le cede al hermano seleccionado, la llave que está más a la izquierda o más a la derecha, en caso de ser cedido al hermano izquierdo o derecho, respectivamente.
3. Esta llave cedida, debe intercambiarse con la llave K_i que se encuentra en el nodo padre, entre los dos nodos que intercambiarán llaves y será dicha llave K_i la que se insertará en el hermano.
4. Si al tratar de cederle una llave al hermano, este también se encuentra lleno, deben combinarse ambos nodos para formar tres. Esta combinación debe realizarse incluyendo la llave K_i que se encontraba en el padre, entre ambos nodos. Se dividirán equitativamente todas las llaves entre 3, sin contar las dos que deben pasar al nodo padre. Al insertar una nueva llave en el nodo padre (una de las dos ya se encontraba allí) con su respectivo apuntador a árbol, puede ocurrir un desbordamiento en ese nodo, por lo que debe hacerse nuevamente el procedimiento de inserción.

Veamos unos ejemplos de inserción en un árbol de orden 7:

El nodo de un árbol B* de orden 7 tiene a lo sumo 6 llaves, pero en este caso, que se trata de una inserción en la raíz del árbol, la inserción se realiza en el propio nodo, porque la raíz admite hasta 8 llaves. Luego, el árbol que se obtiene es:

Si al árbol anterior le insertamos un 70, estaríamos nuevamente en un caso fácil y obtendríamos el árbol:

Ahora insertemos un 35. Ya el nodo se encuentra lleno, por lo que tenemos que dividirlo en dos e insertar la llave del medio en un nuevo nodo raíz que debe ser creado, obteniendo al árbol:

Hay capacidad en el nodo, por tanto, solo hay que buscar el lugar que le corresponde e insertar. Se obtiene el árbol:

Ahora insertemos un 15 en el árbol anterior

No hay capacidad en el nodo en que se inserta. Existe capacidad en el hermano derecho, por lo que puede cedérsele la llave más a la derecha, el 40 en este caso; esta debe intercambiarse con la llave que está en el padre, el 45 y este debe ser insertado en el hermano. El árbol resultante se muestra en la figura siguiente:

En este caso, debemos combinar el nodo en que se inserta, con el hermano, para obtener tres nodos. En esta combinación también se tiene en cuenta la llave que se encuentra en el padre, entre ambos nodos, o sea, el 40.

La figura anterior muestra la combinación. Están representados todas las llaves a combinar, que son las llaves de ambos nodos, más la llave a insertar y la que estaba en el padre. Estas dos últimas se encuentran encerradas en un círculo. Se muestra además las llaves que quedarán en el padre y la división equitativa en tres nodos. El árbol resultante es:

La eliminación se realiza del mismo modo que en el árbol B, siempre y cuando no provoque que un nodo quede con menos llaves que las que debe tener, porque en este caso, el procedimiento a seguir en el árbol B* difiere de la vista anteriormente para el árbol B.

Cuando va a eliminarse una llave de un nodo con la cantidad mínima de llaves, deben seguirse los pasos siguientes:

1. Chequear si el hermano tiene una llave para ceder, o sea, si no tiene también la cantidad mínima de llaves, en este caso, se procede a hacer una rotación de manera análoga a la inserción: la llave cedida se intercambia con la llave K_i del padre, que se encuentra entre ambos nodos y esta se inserta en el nodo del cual se eliminó.
2. Si los hermanos inmediatos del nodo del cual se elimina, no tuvieran la posibilidad de ceder una llave, debe analizarse el nodo que está un lugar más allá que el hermano analizado, o sea, el hermano del hermano, para valorar la posibilidad de que sea este nodo quien ceda la llave. Para ganar en claridad, llamaremos H₀ al nodo del cual se eliminó, H₁ al hermano que no podía ceder y H₂ al otro hermano En caso de ser posible, deben hacerse dos rotaciones para hacer llegar la llave a H₀: una primera rotación de H₁ a H₀ (ahora H₁ es quien tiene la falta) y otra rotación desde H₂ a H₁. Recuerde que estas rotaciones involucran a las llave Ki del nodo padre, que se encuentran entre los nodos H₀ y H₁, H₁ y H₂, respectivamente.
3. De no poder realizar estas rotaciones y persistir el faltante de una llave en el nodo del que eliminó, podemos estar en dos situaciones: o existen dos nodos hermanos del nodo del que se eliminó que no tenían posibilidad de ceder una llave o el nodo del que eliminó solo tenía un hermano. En el primer caso, podemos resolver la situación realizando una combinación de tres nodos para obtener dos, con participación de las llaves K_i del padre que se encuentran entre los tres nodos. La idea es, dividir las llaves de los tres nodos en dos conjuntos que pasarán a estar en los dos nodos a formar, extrayendo la llave del medio, que quedará en el nodo padre, entre los nodos resultantes. Note que como parte de este proceso, el nodo padre ha perdido una llave. Lo cual puede provocar una falta de llave en este, con lo que debe seguirse analizando el árbol hacia arriba.
4. Si estamos en la situación en la que el nodo del cual se eliminó solo tiene un hermano (árbol con dos niveles, en uno la raíz y el otro las dos hojas) y este hermano no puede ceder la llave, debemos fundir las llaves que quedan en un solo nodo, que quedaría como raíz del árbol.

La eliminación en árboles B* podrá entenderse mejor en los ejemplos que siguen, para un árbol de orden 7.

En este caso, el nodo en que se elimina queda con una cantidad de llaves menor que la permitida. Su hermano derecho puede cederle una llave, por lo que se procede a extraer la llave más a la izquierda de este, el 45 en este caso, intercambiarla con la llave del padre, el 40, e insertar el 40 en el nodo del que se eliminó, resultando el árbol:

En este caso, al eliminar el 40, el nodo del que se elimina queda con una cantidad de llaves por debajo del límite. Sus hermanos inmediatos no pueden cederle una llave, por lo que se analiza un hermano más allá y se comprueba que sí puede ceder una. En este caso, debe hacer dos rotaciones, para suplir la falta de llave.

La figura muestra dicha operación:

El árbol resultante sería:

Si analizamos a su hermano (H₁) y al hermano de su hermano (H₂), vemos que no es posible resolver la falta de llave mediante rotaciones, por lo que debe procederse a combinar los tres nodos (H₀, H₁ y H₂) para formar dos.

En la figura anterior se muestran las llaves de los tres nodos a combinar. Se encuentran entre círculos las llaves del nodo padre, que se encuentran entre los tres nodos, que también deben tenerse en cuenta para combinar.

Se encuentra señalado con una flecha la llave que debe quedar en el nodo padre entre los dos nodos y el árbol resultante es:

En este caso, la cantidad de llaves pasa por debajo del límite, el hermano no tiene para ceder una llave, solo existe un hermano para el nodo del cual se eliminó y por tanto, todos los nodos deben combinarse en uno que quedará como raíz, obteniéndose el árbol:

Wirth, N (1987) Algoritmos y Estructuras de Datos

Knuth, D (1973) The Art of Computer Programming[El arte de la programación de computadoras]

Datos de los autores

Licenciado en Ciencias de la Computación, Universidad Central de Las Villas, Cuba, 2002

Ingeniero Informático, Instituto Superior Politécnico José Antonio Echeverría, CUJAE, 2003

Ambos autores se desempeñan actualmente como profesores del Dpto de Técnicas de Programación de la Universidad de Ciencias Informáticas, Cuba y cursan una Maestría en Ciencias de la Computación.

Fecha de realización: Noviembre de 2005.