Equipo1 - Fernando Cesar Sandoval Padilla

Vista previa del material en texto

Arboles B & otras organizaciones de archivos estructuradas en forma de árbol
Integrantes
Blas Palomino Socorro Lizette
Morales Gutiérrez Alan
Ponce Anaya Erika Ivette
Reyes Gonzales Julio Francisco
Sandoval Padilla Fernando Cesar
Wario Merlo Luz Daniela
UNIVERSIDAD DE GUDALAJARA
CENTRO UNIVERSITARIO DE CIENCIAS EXACTAS E INGENIERIAS 
ESTRUCTURAS DE DATOS II
EQUIPO 1
9.1 Invención de los arboles B
El nacimiento del concepto de árbol B surgió alrededor de 1972 por R. Bayer y E. McCreight, empleados de la empresa Boeing.
1.- Surgieron como una necesidad por un sistema de almacenamiento y extracción de grandes archivos que proporcionara acceso rápido a los datos con coste mínimo.
2.- El origen del nombre “árbol B” proviene mas probablemente del nombre de su creador R. Bayer.
9.2 Planteamiento del problema
El acceso al almacenamiento secundario es lento.
1.- La búsqueda binaria requiere demasiados desplazamientos. 
2.- Puede ser muy costoso mantener el índice ordenado para que sea posible efectuar una búsqueda binaria.
 9.3. Los Arboles Binarios De Busqueda como solucion
Usando las tecnicas de estructuras de datos elementales crean nodos que contengan campos de liga,el arbol binario de busqueda se puede construir como una escritura ligada.
Si cada nodo se trata como un registro de longitud fija en el que los campos de liga tiene numeros relativos de registro (NRR).
La busqueda en el arbol es bueno porque esta en un estado balanceado se entiende que la altura de la trayectoria mas larga en mas de un nivel.
9.4 Arboles AVL
Un árbol AVL es un árbol balanceado en altura. 
¿Que es un Árbol AVL?
Un árbol AVL es un árbol balanceado en altura, significa que existe un limite en la magnitud de la diferencia que se permite entre las alturas de cualesquiera dos sub-árboles que comparten una raíz común.
Figura 9.8
Tienen la propiedad AVL, o BA(I). Nótese que no hay 
sub-árboles de cualquier raíz que difieran en más de un nivel. 
Figura 9.9
No son árboles AVL. En cada uno de ellos la raíz del sub-árbol que no está balanceada se marca con una X. 
Características de los árboles AVL
Establecen una diferencia máxima en la altura de cualesquiera dos sub-árboles, los árboles AVL garantizan un cierto nivel mínimo de desempeño en la búsqueda.
Mantener un árbol AVL conforme se insertan nodos nuevos implica el uso de una de cuatro posibles rotaciones. Cada una de ellas se restringe a una única área local del árbol. Rotaciones más complejas requieren solo cinco reasignaciones de apuntadores. 
log2(n+1)
Para un árbol completamente balanceado, el peor caso de la búsqueda para encontrar una llave, considerando N llaves posibles, busca en niveles del árbol.
1.44 log2(n+2)
El peor caso de la búsqueda podría ser buscar en 
 9.5. Arboles binarios paginados.
Los dispositivos de almacenamiento secundario al desplazarse a una localidad especifica tiende a tomar mucho tiempo, pero cuando al cabeza lectora esta en posición ya esta en posición, leer o escribir un conjunto de bytes se efectúa rápidamente.
Pero esta combinación de desplazamiento lento y transferencia rápida lleva a la idea de la paginación.
La paginación es una solución al problema de la búsqueda ya que divide un árbol binario en paginas para después almacenar cada pagina en un bloque haciendo que sea posible reducir el numero de desplazamientos asociados con cualquier búsqueda.
Aunque todo acceso a una pagina requiere de una gran cantidad de transmisión de datos que en su mayoría ni se usan.
Aunque se justifica su costo ya que ahorra muchos desplazamientos los cuales generan más tiempo que las transmisiones adicionales.
En resumen, se divide el árbol en paginas y permite búsquedas más rápidas en el almacenamiento secundario y permite una extracción mas rápida que cualquier otra forma de acceso por llave.
9.6 El problema con la construcción descendentes de los arboles paginados
Dividir un árbol en paginas es una estrategia adecuada a las características de los dispositivos de almacenamiento secundario, como los discos. El problema de hacer un árbol paginado, es como construirlo.
Una manera relativamente sencilla seria clasificar la lista de llaves y construir el árbol a partir de esa lista. 
Cuando se inicia la construcción a partir de la raíz, la llave situada a la mitad de la lista se le llama LLAVE DE RAIZ dentro de la PAGINA RAIZ del árbol.
El problema es muy complejo cuando se reciben las llaves en orden aleatorio y se insertan tan pronto como se reciben.
Árbol paginado construido a partir de llaves en secuencia aleatoria.																
Un ejemplo seria que se debe construir un árbol en paginas conforme se reciben las llaves de una sola letra:
 CSDTAMPIBWNGURKEHOLJYQZFXV
Se construye el árbol paginado con un máximo de tres llaves por pagina.
El problema en este caso es que conforme se insertan las llaves, se van rotando dentro de una pagina y es necesario mantener cada pagina balanceada.
Aunque el árbol no parece demasiado deforme, se ve claramente los problemas inherentes a la construcción de un árbol binario paginado en forma descendente.
Si se llegara a poner como raíz la llave C y D causaría muchos problemas,, debido a que no se puede simplemente rotar paginas completas del arbolen la misma forma que se rotarían llaves individuales en un árbol que no este paginado. Si esto pasara ciertas llaves quedarían fuera de lugar, por lo tanto deben dividirse las paginas. Pero también dividir paginas causa problemas, ya que implica reacomodarlas para crear nuevas paginas y así queden balanceadas y acomodadas.
En resumen el problema de estos arboles paginados, es hacia los acomodos y ajustes que existen en gran parte del árbol. Esto se vuelve mas difícil con mayores tamaños de pagina.
Aunque esto no quita que la idea de agrupar llaves en paginas es muy buena, si se considera la reducción de desplazamientos en disco.
19