Ensayo Equipo 1 - Fernando Cesar Sandoval Padilla

Vista previa del material en texto

Equipo 1 Página 1 Docente: Lara López Graciela EDD2 
UNIVERSIDAD DE GUADALAJARA 
Centro Universitario de Ciencias Exactas e Ingenierías 
 
Estructura de Datos lI 
 
“Arboles b & otras organizaciones de archivos 
estructuradas en forma de árbol” 
 
 
 
 
 
 
Equipo 1 
Integrantes: 
 Wario Merlo Luz Daniela 
 Blas Palomino Socorro Lizette 
 Ponce Anaya Erika Ivette 
 Reyes Gonzales Julio Francisco 
 Sandoval Padilla Fernando Cesar 
 Morales Gutiérrez Alan 
 
 
Equipo 1 Página 2 Docente: Lara López Graciela EDD2 
Invención de árboles B 
Uno de los grandes retos por los que atravesaban los ingenieros de inicios de 
1970 fue la capacidad de procesamiento de archivos, se tenía el hardware de 
procesamiento hasta cierto punto necesario. Ya se disponía del primer 
procesador de 4 bits, el Intel 4004. Se disponía también de lenguajes de 
programación. Ahora uno de los retos era la creación de algoritmos para el 
procesamiento de archivos de gran escala, y sin que esto afectara la capacidad 
de procesamiento o tiempo de procesamiento y los costes en memoria, ya que 
como sabemos, la memoria principal en aquellos tiempos era aún más escasa. 
En 1974 se dio a conocer o se desarrolló una idea bastante revolucionaria que 
parte de un concepto matemático bastante versátil e interesante, el árbol B. 
Básicamente es una estructura de datos para las ciencias de la computación que 
nos sirve para catalogar información, en este caso particular los ingenieros 
específicamente R. Bayer y McCreight lo plantearon como un sistema de 
organización y mantenimiento del índice de un archivo de acceso aleatorio que 
cambia dinámicamente. 
Problemática principal 
Cabe destacar que el objetivo principal de esta exposición es dar a conocer la 
problemática planteada ante el manejo de la información en un índice de 
almacenamiento secundario, puesto que los principales problemas se centran 
en la poca o limitada capacidad para el manejo de información en archivos que 
pueden llegar a contener grandes cantidades de información, es decir; la limitada 
capacidad hace referencia a la dificultad de mantener ordenado el índice dando 
de esta forma lugar a la mayor dificultad esencial para el manejo de la 
información, pues es de vital importancia el poder acceder a la información 
rápidamente, por lo que la búsqueda binaria llega a requerir demasiados 
desplazamientos, entonces, es así que en el desarrollo de los temas se proponen 
diversos métodos de arborización para facilitar la búsqueda y afrontar la 
problemática planteada limitante. Evidentemente estos dos problemas 
planteados no son los únicos existentes en cuanto al procesamiento de archivos 
ya que la simple existencia de dos limitantes conlleva mas limitantes en cuanto 
a capacidad y velocidad de procesamiento, relacionándose así con el Hardware, 
Equipo 1 Página 3 Docente: Lara López Graciela EDD2 
por lo que tomando en cuenta esto, es fácil comprender que todo va de la mano 
y una cosa puede limitar a otra, teniendo así a varias posibles soluciones siendo 
estas soluciones los diversos métodos de arborización. 
Los árboles binarios de búsqueda como solución 
El árbol binario es el caso más simple de árbol de orden N, cuando N vale 2. Su 
especificación se puede hacer considerando un valor constante, el árbol nulo, y 
un constructor de árboles a partir de un elemento y dos árboles. 
Consisten en facilitar la construcción de otras especificaciones de árboles, en los 
que se recurre al esquema de árbol binario y sus operaciones para la expresión 
de operaciones de inserción, extracción, rotación, etc. más complejas, y permitir 
la formalización de conceptos y nociones ligadas a la de árbol binario. 
Árboles AVL 
Un árbol AVL es un árbol balanceado en altura, estos árboles son altamente 
equilibrados lo que significa que el tamaño de permitido entre las alturas de dos 
subárboles que comparten la misma raíz es limitado. 
 
Las dos importantes de un árbol AVL son: 
1) Al establecer la diferencia de altura máxima permitida entre dos subárboles, 
el árbol AVL puede garantizar un cierto rendimiento mínimo de búsqueda. 
 
2) Mantener el árbol en forma AVL cuando se insertan nuevos nodos implica el 
usar uno de las cuatro rotaciones posibles. Cada uno de ellos está limitado a un 
área local única del árbol. Las rotaciones más complejas requieren solo cinco 
apuntadores para ser reasignados. 
 
Para un árbol completamente equilibrado, considerando N claves posibles, el 
peor caso para buscar claves es buscar en el nivel del árbol log2(n+1). El peor 
caso para buscar puede ser 1.44 log2(n+2). 
 
Los árboles AVL en sí no son directamente aplicables a la mayoría de los 
problemas de estructura de archivos, porque como todos los árboles binarios, 
Equipo 1 Página 4 Docente: Lara López Graciela EDD2 
tienen demasiados niveles es decir son muy profundos, los árboles AVL son 
interesantes por la posibilidad de definir procesos que mantengan un alto grado 
de equilibrio. El hecho de que el árbol AVL este altamente equilibrado garantiza 
que el rendimiento de la búsqueda sea similar a la de un árbol completamente 
equilibrado. 
Arboles binarios paginados 
El problema que plantea resolver el empleo de arboles paginados es el de leer o 
escribir un conjunto de bytes puesto que el desplazamiento para encontrar la 
ubicacion especifica del contenido del almacenamiento es lento y tiende tomar 
demasiado tiempo. Tomando en cuenta que la transferencia si es rapida. 
Entonces la paginacion esta enfocada en la busqueda, su funcion principal es 
dividir un arbol binario en varias paginas que a su vez seran agrupadas por 
bloques reduciendo el numero de desplazamientos al momento de realizar una 
busqueda, siendo basicamente la optimizacion para la extraccion comparada 
con cualquier otra forma de acceso por llave, esto se justifica con el hecho de 
que el costo de desplazamientos se reduce sin importar que el acceso a una 
pagina requiera gran cantidad de transmision de datos, siendo asi datos que a 
final de cuentas no suelen utilizarse. 
El problema con la construcción descendente de los árboles 
paginados 
Una estrategia muy adecuada a las características de los dispositivos de 
almacenamiento secundario es dividir un árbol en páginas. 
Pero cuando se intenta realizar un árbol paginado hay ciertos problemas es 
saber cómo construirlo, aunque una manera sencilla seria clasificar la lista de 
llaves e ir construyendo el árbol. El problema es más complejo cuando se reciben 
las llaves de manera aleatoria y se insertan conforme se reciben. 
Cuando se planea construir un árbol a partir de la raíz, como se sabe la llave a 
la mitad de la lista es la llave raíz, así se sabe dónde comenzar y que es punto 
inicial mantenga un balance. 
Se debe tener cuidado y poner las llaves correctas como raíz, ya que causaría 
muchos problemas si las pusiéramos incorrectas, en los árboles paginados no 
se puede rotar paginas completas del árbol a como se rotarían las llaves 
Equipo 1 Página 5 Docente: Lara López Graciela EDD2 
individuales en un árbol que no está paginado. Si hacemos eso muchas llaves 
quedarían fuera de lugar. 
En fin, el problema de los árboles paginados en sí, es hacia los acomodos y 
ajustes que existen en gran parte del árbol. Si hubiera mayores tamaños de 
páginas sería más difícil. 
Pero sigue siendo una gran idea agrupar llaves en páginas es muy buena, si se 
considera la reducción de desplazamiento en disco. 
Conclusión 
Es claro que el desarrollo de esta actividad nos ayudo a conocer distintos 
métodos de arborización, los cuales podemos llegar a emplear en diversas 
situaciones, esto siempre dependiendo de los factores que consideremos más 
importantes al momento en que programemos algo que facilite el procesamiento 
de archivos, es decir; dependiendo de las necesidades o prioridades elegidaspara el trabajo en cuestión. 
Entonces, tomando en cuenta todo lo dicho anteriormente, podemos decir con 
seguridad que el procesamiento de archivos es una prioridad en el ámbito de la 
computación y la informática puesto que todos estos temas se ven involucrados 
de una u otra manera con el software y el hardware, los cuales trabajando en 
conjunto nos permiten procesar los archivos de diversas maneras, nombrando 
así de nuevo los métodos de arborización ya planteados, finalmente es 
importante destacar que con esto podemos analizar y observar en que 
situaciones es mas correcto el empleo de ciertos métodos para el manejo de la 
información, teniendo de esta manera como necesidad o factor a futuro el 
aprender a emplear estos métodos y ponerlos en practica para que no quede 
solo en cuestión teórica.