AbrahamLetechipia Unidad 3 Arboles B

EDÓ







INVESTIGACION ARBOLES B+










Versión 1
2015/07/07



Grupo:
1CM1







ALUMNO:
2015670091 Abraham Letechipia Padilla




Índice del Documento
1 Definición 4
2 8.5.2 Inserción en árboles B+ 4
3 8.5.3 Borrado En Arboles-B+ 9


Índice de Figuras
No se encuentran elementos de tabla de ilustraciones.


































Índice de Tablas
Ninguna.1 Definición
Los árboles-B+ se han convertido en la técnica más utilizada para la organización de archivos indizados. La principal característica de estos árboles es que todas las claves se encuentran en las hojas y por lo tanto cualquier camino desde la raíz hasta alguna de las claves tiene la misma longitud. En la figura 8.4 representamos un diagrama de un árbol-B+ de orden2.

Figura 8.4 Árbol-B+ de orden 2
Es de notar que los arboles-B+ ocupan un poco más de espacio que los arboles-B, y esto ocurre al existir duplicidad en algunas claves. Sin embargo, esto es aceptable si el archivo se modifica frecuentemente, puesto que se evita la operación de reorganización del árbol que es tan costosa en los arboles-B.
Formalmente se define un árbol-B+ de la siguiente manera:1. Cada página, excepto la raíz, contiene entre d y 2d elementos.
2. Cada página, excepto la raíz, tiene entre d + 1 y 2d + 1 descendientes. Se utiliza m para expresar el número de elementos por página.
3. La página raíz tiene al menos dos descendientes.
4. Las paginas hojas están todas al mismo nivel.
5. Todas las claves se encuentran en las páginas hojas.
6. Las claves de las páginas raíz einteriores se utilizan como índices.
7. Búsqueda De Arboles-B+
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 encuentra en una página raíz o interior, en dicho caso no debe detenerse el proceso, sino que debe continuarse la búsqueda con la página apuntada por larama derecha de dicha clave. Por ejemplo, al buscar la clave 55 en el árbol-B+ de la figura 8.4 se advierte que esta se encuentra en la página raíz. En este caso, debe continuarse el proceso de búsqueda en la página apuntada por la rama derecha de dicha clave.
2 Inserción en árboles B+
El proceso de inserción en árboles-B+ es relativamente simple, similar al proceso de inserción en árboles-B. Ladificultad se presenta cuando desea insertarse una clave en una página que se encuentra llena (m = 2d). En este caso, la página afectada se divide en 2, distribuyéndose las m + 1 claves de la siguiente forma: " las d primeras claves en la página de la izquierda y las d + 1 restantes claves en la página derecha”. Una copia de la clave del medio sube a la página antecesora. En la figura 8.5 hay dosdiagramas que ilustran como funciona este caso.

Figura 8.5 Inserción de la clave 13 en un árbol B+.
a) Antes de insertar la clave) Después de insertarla.
Puede suceder que la página antecesora se desborde nuevamente, entonces tendrá que repetirse el proceso anterior. Es importante notar que el desbordamiento en una página que no es hoja no produce duplicidad de claves. El proceso de propagaciónpuede llegar hasta la raíz, en cuyo caso la altura del árbol puede incrementarse en una unidad. En la figura 8.6 se presentan dos diagramas que clarifican y resuelven este caso.

Figura 8.6 Inserción de la clave 66 en un árbol-B+
a) Antes de insertar la clave b) Después de insertarla.
Ejemplo 1
Supóngase que se desea insertar las siguientes claves en un árbol-B+ de orden 2 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 8.7
 

Figura 8.7 Inserciones en un árbol-B+ de orden2
(primera parte)


Figura 8.7 Inserción de un árbol-B+ de orden 2
(Segunda parte)
Ejemplo 2
Dado el árbol-B+ de orden 2 de la figura 8.8a), verifique si el...