• Author / Uploaded
• Yair Ortiz Perez

Citation preview

ARBOLES B+

JHON HANER BAUTISTA LAZARO 1150039 JAVIER VIDAL NUMA MENDOZA 1150057

UNIVERSIDAD FRANCISCO DE PAULA SANTANDER FACULTAD DE INGENIERIAS INGENIERIA DE SISTEMAS CUCUTA 2011

ARBOLES B+

JHON HANER BAUTISTA LAZARO 1150039 JAVIER VIDAL NUMA MENDOZA 1150057

ING OSCAR GALLARDO

UNIVERSIDAD FRANCISCO DE PAULA SANTANDER FACULTAD DE INGENIERIAS INGENIERIA DE SISTEMAS CUCUTA 2011

ARBOLES B+

Los arboles B+ se han convertido en la técnica más utilizada para la organización de archivos indizados (Ordenador por una llave). La principal característica de estos árboles es que toda la información se encuentra en las hojas, mientras que en los nodos raíz e interiores almacenan las claves que se utilizan como índices. Es de notar que los arboles B+ ocupa más de espacio que los arboles B, esto ocurre al existir duplicidad en algunas claves. Este árbol está compuesto por:

Índice: nodos interiores Secuencia: paginas hojas enlazadas secuencialmente en las que se repiten las claves anteriores

PROPIEDADES

• Cada página, excepto la raiz, contiene m elementos, donde m es un valor entre d y 2d , mínimo 2 máximo 4 • La raiz contiene de 1 a 2d elementos. • Cada página, excepto la raíz tiene entre d+1 y 2d+1 descendientes. • La pagina raiz tiene 2 descendientes o ninguno. • Las paginas hojas están todas al mismo nivel. • Toda la información con la clave que las identifican, se encuentra en la pagina hoja. • Las claves almacenadas en las paginas raiz e interiores se utilizan como índices (para búsqueda) • Los nodos no terminales no tienen datos sino punteros a los datos.

BUSQUEDA

La operación de búsqueda en arboles B+ es similar a la operación de búsqueda de arboles B, el proceso es simple sin embargo puede suceder que al buscar una determinada clave la misma se encuentre en una página raiz o interior. En dicho caso no se puede detener el proceso.

EJEMPLO Al buscar la clave 55 en el siguiente árbol, se encuentra en la página raiz, en este caso se debe continuar el proceso de búsqueda en la pagina apuntando por la rama derecha de dicha clave.

INSERCION

El proceso de inserción es similar al de arboles B, la dificultad se presenta cuando se desea insertar una clave cuando la pagina este llena, en este caso la pagina se divide en 2, y una copia de la del medio sube a la pagina antecesora convirtiéndose en raiz.

Insertar la Calve 13:

Ejemplo Supongamos que se desea insertar las siguientes claves en un árbol B+ de orden 2 el cual se encuentra vacio.

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

ELIMINACION

Las operaciones de eliminación en un árbol B+ es más sencilla que la eliminación de un árbol B, por que las claves que iremos a eliminar siempre se encuentra en las páginas hojas, en general se debe distinguir los siguientes casos.

1. Si al eliminar una clave m queda mayor o igual a d, entonces termina la operación de borrado, las claves de las páginas raiz o internas no se modifican por más que sean una copia de las claves eliminada en las hojas.

2. Si al terminar una clave m queda menor que d, entonces se debe realizar una redistribución de claves, tanto para el índice como en las paginas hojas, se quitan aquellas claves que quedaron en los nodos interiores luego de haber eliminado su correspondiente información en los nodos hoja.

BIBLIOGRAFIA

1. Estructura de datos – Tercera edición Osvaldo Cairo Silvia Guardati Pág. 241 – 263 2. http://www.virtual.unal.edu.co/cursos/ingenieria/2001412/capitulos/cap 8/85.html 3. http://www.virtual.unal.edu.co/cursos/ingenieria/2001412/capitulos/cap 8/85.html 4. http://www.dav.sceu.frba.utn.edu.ar/homovidens/cmem_generico/perez cavenago/Final/AB_MAS.html 5. http://usuarios.multimania.es/arbolesbpro/variantes.htm 6. http://usuarios.multimania.es/arbolesbpro/costos.htm