- Resumen
- Resolviendo los problemas de los
accesos a disco. Generalización del concepto
Árbol de búsqueda - En busca del equilibrio en el
árbol y un mayor aprovechamiento del espacio en disco.
Árbol B - Algunas modificaciones al
Árbol B. Árbol B + - Disminuyendo la altura del
árbol y los accesos a memoria. Árbol
B* - Bibliografía
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.
Palabras claves
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:
- Es difícil construir un árbol binario
de búsqueda perfectamente equilibrado. - El número de consultas en el árbol no
equilibrado es impredecible. - 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
Resolviendo los
problemas de
los accesos a disco. Generalización del concepto
Árbol de búsqueda.
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 <P1, k1,
P2, k2, …, Pq-1,
Kq-1, Pq> , donde q <= p, cada
Pi es un apuntador a un nodo hijo (o apuntador nulo) y
cada Ki 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:
- Dentro de cada nodo K1 < K2
< ….< Kq-1 - Para todos los valores de X, del subárbol al
cual apunta Pi , tenemos que Ki-1 < X
< Ki , para 1 < i < q; X < Ki
, para i = 1 y X > Ki-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 Pi 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.
En busca del equilibrio en
el árbol y un mayor aprovechamiento del espacio en disco.
Árbol B
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:
<P1, <k1,
Pr1>, P2, <k2,
Pr2> , …, <kq-1,
Prq-1>, Pq>donde q <= p. Cada Pi es un
apuntador de árbol: un apuntador a otro nodo
del árbol. Cada Pri es un apuntador de
datos: un apuntador al registro cuyo valor del campo
clave de búsqueda es igual a Ki (o un
apuntador al bloque que contiene ese registro de
datos)- Cada nodo interno del árbol B tiene la forma
(Ver Fig. 2) - Dentro de cada nodo K1 < K2
< ….< Kq-1
- Para todos los valores de X, del subárbol al
que apunta Pi , tenemos que Ki-1 < X
< Ki , para 1 < i < q; X < Ki
, para i = 1 y X > Ki-1 para i = q. - Cada nodo tiene, cuando más, p apuntadores de
árbol. - 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. - 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. - 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,
Pi , 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
2th-1.
La cantidad de nodos n, que tiene un árbol B
cumple con lo siguiente:
Obtenemos que:
entonces el crecimiento del árbol es
O(logt n).
Operaciones
básicas en árboles B
Las operaciones básicas que se pueden realizar en
un árbol B son básicamente tres:
- Buscar una llave
- Insertar una llave
- Eliminar una llave
Búsqueda
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 Ki que se
encuentran en ese nodo. Si Y es igual a algún
Ki, 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á P1, si Y < K1,
Pq si Y > Kq-1 y Pi, si
Ki-1 < X < Ki, para 1 < i < q.
En caso que el Pi 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) = (logt 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*logtn).
Inserción
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 Pi
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:
- Insertar la llave como si realmente tuviese sitio
libre. - 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. - 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. - 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.
Ej. 2 Veamos otro ejemplo que implicará que
aumente la altura del árbol. Supongamos que tenemos un
árbol con esta estructura, y queremos insertar la clave
68:
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*logtn).
Eliminación
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 Ki correspondiente en el
nodo padre y es este valor Ki 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 Ki que
estaba situada en la página padre, entre ambos nodos. Si
al fundirse los dos nodos y tomar la llave Ki 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 Ki 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:
Ej. 1 Eliminemos la clave 65. Es uno de los casos
más sencillos, la clave está en un nodo hoja, y el
número de claves del nodo después de eliminarla es
mayor del mínimo.
Tan sólo tendremos que eliminar la
clave:
Ej. 2 Eliminaremos ahora la clave 20.
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.
Ej. 4 Vamos a ver el caso en que el nodo derecho no
tiene claves suficientes para transferir una al nodo hoja.
Eliminaremos la clave 5:
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.
Ej. 5 Veamos cómo sería el proceso en
un caso general, que implica la reducción de altura del
árbol.
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*logtn).
Algunas
modificaciones al Árbol B. Árbol B +
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):
- Todo nodo interno es de la forma <P1,
k1, P2, k2, …,
Pq-1, Kq-1, Pq> , donde q
<= p, cada Pi es un apuntador de
árbol. - Dentro de cada nodo interno K1 <
K2 < ….< Kq-1 - Para todos los valores X, del campo de
búsqueda en el subárbol al cual apunta Pi
, tenemos que Ki-1 <= X < Ki
, para 1 < i < q; X < Ki , para i = 1 y X
>= Ki-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. - Cada nodo interno tiene, cuando más, p
apuntadores de árbol. - 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 - 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):
<<k1, Pr1>,
<k2, Pr2> , …,
<kq-1, Prq-1>,
Psiguiente,> donde q<=p, cada Pri
es un apuntador de datos y Psiguiente apunta al
siguiente nodo hoja del árbol B+.- Todo nodo hoja tiene la forma:
- Dentro de cada nodo hoja K1 <
K2 < ….< Kq-1, donde
q<=p - Cada nodo hoja tiene al menos p/2 valores
- 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.
Operaciones básicas en árboles
B+
Búsqueda
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 Ki-1, debemos
continuar la búsqueda por el apuntador Pi
.
Inserción
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
Fig. 9 Crecimiento del árbol B
a medida que se insertan los valores
señalados
Eliminación
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:
- 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). - 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.
Disminuyendo la
altura del árbol y los accesos a memoria. Árbol
B*
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:
<P1, <k1,
Pr1>, P2, <k2,
Pr2> , …, <kq-1,
Prq-1>, Pq>donde q <= p. Cada Pi es un
apuntador de árbol: un apuntador a otro nodo
del árbol. Cada Pri es un apuntador de
datos: un apuntador al registro cuyo valor del campo
clave de búsqueda es igual a Ki (o un
apuntador al bloque que contiene ese registro de
datos)- Cada nodo interno del árbol B tiene la forma
(Ver Fig. 2) - Dentro de cada nodo K1 < K2
< ….< Kq-1
- Para todos los valores de X, del subárbol al
que apunta Pi , tenemos que Ki-1 < X
< Ki , para 1 < i < q; X < Ki
, para i = 1 y X > Ki-1 para i = q. - 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. - 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. - 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. - 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,
Pi , son nulos.
Operaciones básicas en árboles
B*
Búsqueda
La búsqueda en el Árbol B* se realiza de
misma manera que en el B.
Inserción
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:
- Insertar la llave como si realmente tuviese sitio
libre. - 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. - 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:
- Insertar la llave como si hubiese
capacidad. - 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. - Esta llave cedida, debe intercambiarse con la llave
Ki que se encuentra en el nodo padre, entre los dos
nodos que intercambiarán llaves y será dicha
llave Ki la que se insertará en el
hermano. - 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 Ki 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:
Ejemplo 1 Insertemos un 45 en el siguiente
árbol:
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:
Ejemplo 2 Insertemos el 25 en el siguiente
á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:
Ejemplo 3 Veamos qué ocurre al insertar una
llave en un nodo sin capacidad, que tiene un hermano en el que no
hay capacidad. Insertemos el 32 en el
árbol:
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:
Eliminación
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:
- 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 Ki del padre, que se
encuentra entre ambos nodos y esta se inserta en el nodo del
cual se eliminó. - 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 H0
al nodo del cual se eliminó, H1 al hermano
que no podía ceder y H2 al otro hermano En
caso de ser posible, deben hacerse dos rotaciones para hacer
llegar la llave a H0: una primera rotación de
H1 a H0 (ahora H1 es quien
tiene la falta) y otra rotación desde H2 a
H1. Recuerde que estas rotaciones involucran a las
llave Ki del nodo padre, que se encuentran entre los nodos
H0 y H1, H1 y H2,
respectivamente. - 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 Ki 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. - 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.
Ejemplo 1 En el árbol siguiente, eliminar la
llave 35
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:
Ejemplo 2 Eliminemos el 40 del árbol
siguiente:
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:
Ejemplo 3 Eliminemos el 20 del
árbol:
Si analizamos a su hermano (H1) y al hermano
de su hermano (H2), vemos que no es posible resolver
la falta de llave mediante rotaciones, por lo que debe procederse
a combinar los tres nodos (H0, H1 y
H2) 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:
Ejemplo 4 Procedamos a eliminar el 20 en el
árbol siguiente:
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]
Pozo, S (2001) Arboles-B. Extraído
de http://articulos.conclase.net/arboles-b
Marqués, M (2001) Arboles B y árboles
B+. Extraído de http://www3.uji.es/~mmarques/f47/apun/node27.html.
Luna, F (2001) Tutorial de los árboles B.
Extraído de http://usuarios.lycos.es/arbolesbpro/
Datos de los autores
Lic. Joel Arencibia Ramírez
Licenciado en Ciencias de la
Computación, Universidad
Central de Las Villas, Cuba,
2002
Ing. Leansy Alfonso Pérez
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.