Son arboles multicamino con una construcción especial en forma ascendente que permite mantener un árbol balanceado
*Los arboles B son arboles cuyos nodos pueden tener un numero minimo multiple de hijos
*Tiene por objetivo agrupar en cada nodo mas de un elemento de manera que el acceso a un elemento cualquiera tenga lugar visitando un numero de nodos inferior a l caso de ABB
*La ventaja de los arboles B reside en los métodos para insertar y borrar registros, que dejan siempre el árbol balanceado
Los árboles B deben cumplir las siguientes características en cuanto a estructura:
- Toda página tiene como máximo 2n nodos.
- Toda página distinta de la raíz tiene como mínimo n nodos. La raíz tiene como mínimo 1 nodo.
- Toda página que no sea una hoja tiene m+1 páginas hijas, siendo m el número de nodos de la página.
- Todas las páginas hoja están en el último nivel.
Insertar
La operación de inserción en un árbol B es relativamente sencilla, sólo hay un caso en el que este procedimiento se complica ligeramente.
La primera acción a realizar en la operación de inserción es localizar el lugar adecuado en el árbol donde se insertará el nuevo elemento. De esta forma aseguraremos que la propiedad de orden se mantiene.
Una vez localizado el lugar adecuado, hay que tener en cuenta el número de nodos que tiene la página destino del nuevo elemento. Si tiene menos de 2n, entonces se inserta el nuevo nodo y se da por finalizada la operación de inserción.
La complejidad se produce cuando la página destino está al cmopleto de su capacidad, es decir, tiene 2n nodos. En estos casos el procedimiento a seguir es el siguiente:
- Insertar el nodo 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 la página original en dos nuevas páginas, cada una de ellas con n elementos. Estas páginas serán los hijos derechos e izquierdo 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.
Como consecuencia de que todas las hojas deben estar en el último nivel, los árboles B crecen hacia arriba, característica que también los diferencia del resto de árboles estudiados hasta ahora. Este crecimiento se produce cuando la inserción de un nodo en una página completa provoca su división.
Vamos a ver un ejemplo de inserción en árboles B.
Sobre este árbol se inserta el elemento 18. La página que le corresponde es la que contiene los elementos 10,15,17,19. Al estar completa se produce el ascenso del nodo mediano (el 17) y la división en dos páginas de la página original.
Borrar .
El proceso de borrado puede llegar a ser algo más complejo que la inserción.
La eliminación de elementos siempre se hace en una hoja, si el nodo a borrar no estuviese en un nodo hoja, se sustituiría el nodo a borrar por el inmediatamente inferior o superior, que sí que debe estar en undo hoja.
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 n. De esta forma, la estructura del árbol se sigue cumpliendo y no hay que realizar ninguna reestructuración.
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. 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 de 2n-1 nodos. A esta página se le añade el nodo central que estaba situado en la página padre.
Vamos a ver gráficamente los efectos de una eliminación.
Si sobre el árbol representado arriba se elimina el elemento 18, el árbol resultante sería el siguiente:
Para llegar a esta situación se fusionaron la primera y la segunda hoja con su nodo mediano situado en la página padre.
- Los nodos dentro de una página mantienen un orden ascendente de izquierda a derecha.
- Cada nodo es mayor que los nodos situados a su izquierda.
- Cada nodo es mayor que los nodos situados a su derecha.
¿Que es un arbol B+?
un árbol B+ es un tipo de estructura de datos de árbol, representa una colección de datos ordenados de manera que se permite una inserción y borrado eficientes de elementos. Es un índice, multinivel, dinámico, con un límite máximo y mínimo en el número de claves por nodo. Un árbol B+ es una variación de un árbol B.
- Es la técnica mas utilizada para la organización de archivos
- Todas las claves se encuentran en las hojas
- Cualquier camino desde la raiz hasta la clave tiene la misma longitud
- Ocupan mas espacio que los arboles B por que hay que duplicar las claves
- Todas las hojas se encuentran en el mismo nivel.
¿Como construir un arbol B+?
Para crear un arbol B+ vamos ingresando los nodos en el orden de izquierda a derecha, si el nodo a insertar es mayo lo insertamos a la derecha y si es menor a la izquierda y así sucesivamente hasta insertar todos los nodos,pero a diferencia de los arboles b en este tipo de nodos, debemos crear una copia del nodo antecesor y lo ponemos en la hoja de primeras de izquierda a derecha
En un árbol B+, toda la información se guarda en las hojas. Los nodos internos sólo contienen claves y punteros. Todas las hojas se encuentran en el mismo nivel, que corresponde al más bajo. Los nodos hoja se encuentran unidos entre sí como una lista enlazada para permitir búsqueda secuencial.
¿Como insertar una clave en un arbol B+?
La inserción es similar a la del arbol B, cuando se inserta y la pagina esta llena se divide endos ala izquierda , y ala derecha una copia de la clave del tejido sube a a la pagina antecesora
Ejemplo 2
Para eliminar una clave debemos de considerar los siguientes aspectos:
*Si al eliminar la clave (siempre en una hoja) el número de claves es mayor o igual a m/2 el proceso ha terminado. Las claves de las páginas raíz o internas no se modifican aunque sean una copia de la eliminada,pues siguen constituyendo un separador válido entre las claves de las páginas descendientes.
*Si al eliminar la clave el número de ellas en la página es menor que m/2 será necesaria una fusión y redistribución de las mismas tanto en las páginas hojas como en el índice.
Ejemplo:
Si al eliminar una clave, m queda menor a d 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 la figura 8.10 ).
http://www.virtual.unal.edu.co/cursos/ingenieria/2001412/capitulos/cap8/85.html
No hay comentarios.:
Publicar un comentario