Arboles B

ÁRBOLES-B

• Los árboles-B son una variante de los árboles balanceados y cubren la misma necesidad.

• En estas estructuras, a cada nodo se le conoce con el nombre de página y las

• páginas se guardan en algún dispositivo de almacenamiento secundario.

• Las operaciones que pueden realizarse sobre la información almacenada en

• árboles-B son: búsqueda, inserción y eliminación.

CARACTERÍSTICAS DE LOS ÁRBOLES-B

• • La página raíz almacena como mínimo 1 dato y como máximo 2n datos.

• • La página raíz tiene como mínimo 2 descendientes.

• • Las páginas intermedias y hojas almacenan entre n y 2n datos.

• • Las páginas intermedias tienen entre (n+1) y (2n+1) páginas descendientes.

• • Todas las páginas hojas tienen la misma altura.

• • La información guardada en las páginas se encuentra ordenada.

EJEMPLO DE ÁRBOL-B

La figura 7.16 presenta un ejemplo de un árbol-B, de grado 2.

En la raíz se almacenan dos datos, lo que origina que tenga tres descendientes. La página hoja que está más a la izquierda guarda todos los datos que son menores al primer dato (105) de la página raíz, la segunda hoja contiene los datos mayores a 105 y menores a 320, mientras que la tercera hoja almacena los datos mayores al segundo dato de la página raíz (320). Cada una de las páginas hojas tiene entre 2 y 4 elementos.        

Si no fueran hojas, tendrían: la primera 3, la segunda 5 y la tercera 4 páginas descendientes respectivamente.

BÚSQUEDA EN ÁRBOLES-B

• En este tipo de árboles se recuperan del medio secundario de almacenamiento páginas completas de información y se procede a buscar en ellas el dato deseado.

• Si se encuentra, termina la búsqueda; en caso contrario se procede con la página

• que corresponda según el dato con el cual se compara, ya sea menor o mayor.

• Si se requiere recuperar una nueva página pero no existe, entonces se tiene un

• caso de fracaso.

• Los pasos para llevar a cabo esta operación son los siguientes:

• Considere el árbol-B de la figura 7.17. Se quiere encontrar el valor 319.

• La figura 7.17 las líneas punteadas indican las páginas que se van visitando hasta llegar al dato buscado. Por su parte, las páginas sombreadas son las que se recuperan para hacer la comparación del elemento buscado con los elementos almacenados en el árbol.

INSERCIÓN EN ÁRBOLES-B

• La operación de inserción se caracteriza porque los nuevos elementos siempre se

• guardan a nivel de las hojas, y puede originar la reestructuración del árbol incluso

• hasta la raíz provocando esto último que la altura aumente en uno.

• Los pasos para llevar a cabo esta operación son los siguientes:

• Considere el árbol-B, de grado 2, de la figura 7.18 en el cual se quiere insertar el valor 60.

• La línea punteada señala la página que se recupera y donde se agrega el 60.

ELIMINACIÓN EN ÁRBOLES-B

• La operación de eliminación consiste en quitar un elemento del árbol-B cuidando

• que mantenga las propiedades vistas. Es decir, el número de datos en cada

• página debe ser mayor o igual a n y menor o igual a 2n.

• Los pasos para llevar a cabo esta operación son los siguientes:

• Se tiene un árbol-B, de grado 2 en el cual se quiere eliminar el valor 222.

• El dato buscado estaba en una página hoja que a su vez tenía más de n elementos.

ÁRBOLES-B+

• Los árboles-B+ son una variante de los árboles-B, diferenciándose de estos últimos

• por el hecho de que toda la información se encuentra almacenada en las

• hojas.

• En la raíz y en los nodos intermedios se guardan solamente las claves o

• índices que permiten llegar a un cierto dato.

• Las operaciones que pueden realizarse sobre la información almacenada en

• árboles-B+ son: búsqueda, inserción y eliminación.

CARACTERÍSTICAS DE LOS ÁRBOLES-B+

• • La página raíz almacena como mínimo 1 dato y como máximo 2n datos.

• • La página raíz tiene como mínimo 2 descendientes.

• • Las páginas intermedias y hojas almacenan entre n y 2n datos.

• • Las páginas intermedias tienen entre (n+1) y (2n+1) páginas descendientes.

• • Todas las páginas hojas tienen la misma altura.

• • La información guardada en las páginas se encuentra ordenada.

EJEMPLO DE ÁRBOL-B+

• La figura 7.24 presenta un ejemplo de un árbol-B+, de grado 2.

• En la raíz se almacenan valores que funcionan como índices para llegar a los datos que están en las hojas.

BÚSQUEDA EN ÁRBOLES-B+

• La operación de búsqueda es similar a la estudiada en los árboles-B. La diferencia

• es que en estos árboles la búsqueda termina siempre en las páginas hojas

• (donde está la información completa).

• Los pasos para llevar a cabo esta operación son los siguientes:

• Buscar el valor 320 en el árbol-B+  de la figura 7.24.

INSERCIÓN EN ÁRBOLES-B+

• La operación de inserción es similar a la estudiada en los árboles-B. La diferencia

• consiste en que cuando se produce la división de una página en dos

• (por dejar de cumplir la condición de que el número de elementos debe ser

•  n y  2n) se debe subir una copia de la clave (o índice) del elemento del

• medio.

• Sólo se duplica información cuando la clave que sube es de una página

• hoja.

• Los pasos para llevar a cabo esta operación son los siguientes:

• En el árbol-B+, de grado 2, de la figura 7.25 se quiere insertar el valor 287.

ELIMINACIÓN EN ÁRBOLES-B

• La operación de eliminación consiste en quitar un elemento del árbol-B+ cuidando

• que mantenga las propiedades vistas. Es decir, el número de datos en cada página

• debe ser mayor o igual a n y menor o igual a 2n.

• Como los datos siempre están en las páginas hojas, cuando se encuentran se quitan (sólo de la hoja, sin importar si además están en un nodo intermedio o raíz) y sólo se reestructura el árbol si la página quedó con menos de n elementos.

• Los pasos para llevar a cabo esta operación son los siguientes:

• La tabla 7.13 presenta la secuencia de operaciones requeridas para llevar a cabo

• la eliminación del valor 261 del árbol-B+, de grado 2, de la figura 7.26.

...