Ensayo Equipo 2 - Fernando Cesar Sandoval Padilla

Vista previa del material en texto

Equipo 2 Estructuras de datos 2 Arboles B
 
 
Arboles B 
 
 
 
 
 
 
 
 
Integrantes: 
● Soto Martinez Christian 
● Moran Garcia Fernando Rene 
● Ortega Garcia Carlos Antonio 
● Alvarez Rodriguez Miguel Angel 
● Ponce Aragón Brandon Alejandro 
● Nava Ramos Vianey Guadalupe 
●García Ramírez Alberto 
Página 1 
Equipo 2 Estructuras de datos 2 Arboles B
 
Ensayo árboles 
El uso de árboles como métodos de ordenamiento e indexación 
presentan una solución que si resulta complicada de entender, reduce 
de manera considerable los espacios a utilizar y nos permiten trabajar 
con grandes cantidades de información de manera eficiente y rápida. 
Incluso dentro de los árboles existen varios tipos, cada uno aplicable a 
problemas distintos, que los resuelven de maneras distintas, más o 
menos pesadas. 
Los árboles B de construcción ascendente son una alternativa poderosa 
de las varias dentro del tema de los árboles donde en lugar de 
construirlos de arriba abajo empezamos de abajo a arriba. Esto no son 
precisamente binarios pues son multi-caminos y llevan una construcción 
especial que permite mantenerlos balanceados a bajo costo. El estar 
dividido en multiniveles facilita los procesos de búsqueda ahorrando 
mucho costo computacional. Además estos árboles evitan la dificultad 
de tener llaves erróneas y tener que reacomodarlas siendo que se 
permite que la raíz del árbol emerja, en lugar de colocarla y tener que 
buscar maneras de cambiarla. 
A diferencia de un árbol paginado en los árboles B no existen los 
árboles explícitos para un nodo. 
Como explicaba en el párrafo anterior la ventaja de estos árboles b son 
que construimos el árbol en base a los datos y no desde una base, lo 
cual nos obliga a introducir conceptos como la promoción y división, que 
son los métodos de organización dentro del árbol. El paginamiento 
funciona de manera bastante similar. Donde establecemos un máximo 
de llaves e hijos para comenzar el paginamiento. Esto resulta ser 
bastante practico por que se pueden. Originalmente este tipo de 
organizaciones puede causar confusiones en cuanto a cuando terminan 
debido a la misma nomenclatura. Pero todo se simplifica cuando 
relacionamos los datos como descendientes con las llaves. 
Estableciendo que el número de llaves en una página siempre es uno 
menos que el número de descendientes. 
Página 2 
Equipo 2 Estructuras de datos 2 Arboles B
 
Como ejemplo el libro establece un arbol de orden 8 tiene un máximo de 
llaves de 7 por página. Por ende un árbol B con N cantidad de llaves 
puede tener N+1 descendientes a partir de su nivel hoja. 
En términos de eficiencia de algoritmos describimos a un árbol B como 
t(n)= n en el mejor de los casos y logM(n) en el peor siendo M la 
cantidad máxima de hijos que un árbol puede tener. Comparando esto 
con un árbol binario de tipo descendente comparten el mismo t(n) pero 
la manera de organización es mucho más compleja. De hecho calcular 
las relaciones resulta muy simple incluso numéricamente hablando. 
Considerando el peor de los casos como nuestra fórmula a calcular. 
Ahora, hay una enorme diferencia en el nivel de distribución y 
organización entre un árbol tipo B y un índice primario. 
Siendo por ejemplo que el hecho de trabajar con llaves hechas 
específicamente para cantidades calculadas de grupos de datos. Esto 
supone costos computacionales distintos. Un índice simple, 
regularmente accede a los datos de manera secuencial mientras que un 
árbol lo hace de manera binaria, haciendo sumamente eficiente tanto la 
búsqueda como la adición de registros a un índice. El problema 
regularmente sería el hecho de el mantenimiento, mientras que el índice 
simple solo involucra la creación de una nueva llave y registro. La 
adición de datos en un árbol involucra una situación más profunda 
donde tendremos que evaluar situaciones más complejas como lo es la 
división y la promoción. Así que solo estaríamos cambiando la simpleza 
y facilidad de manejo de un índice simple contra la eficiencia y buen 
manejo de la información de un árbol tipo B. 
Siempre es muy importante al trabajar con información tener un correcto 
manejo de ella. Sobre todo si no disponemos de recursos 
computacionales como para desperdiciarlos con búsquedas 
secuenciales u ordenamientos ineficientes. Así que en la mayoría de las 
situaciones, si es posible, y sobre todo si se manejan grandes 
cantidades de información, es mejor utilizar árboles. Sobre todo y a 
nuestro parecer este tipo de árboles debido a su complejidad 
computacional y manera de organizar la información . En cualquier 
trabajo que no requiera el uso de tanta información se puede recurrir al 
uso de estrategias más simples como lo es la indexación simple. 
Página 3 
Equipo 2 Estructuras de datos 2 Arboles B
 
Podemos concluir entonces, que a mayor complejidad del problema y 
mayor cantidad de datos, debemos utilizar estructuras acorde. 
Página 4