Ensayo_Equipo 3 - Fernando Cesar Sandoval Padilla

Esta es una vista previa del archivo. Inicie sesión para ver el archivo original

Lo que se busca con esto es hacer la mayor cantidad de índices en la menor cantidad de 
niveles de árboles posibles para lograr una mejor eficiencia. O sea que se busca que los 
arboles sean más pequeños y gruesos en vez de largos y delgados siguiendo las siguientes 
reglas: 
 Cada página, excepto la raíz y las hojas, tiene por lo menos [m/2] descendientes. 
 Una página que no es una hoja K descendiente contiene k-1 llaves. 
 Una página hoja contiene por lo menos [m/2]-1 y no más de m-1 llaves. 
Es necesario desarrollar algún tipo de garantía igualmente confiable para que se 
mantengan estas propiedades cuando se eliminan llaves de árbol. 
Trabajar a en situaciones simples te ayudara a demostrar que con la eliminación de llaves 
puedes caer en varias situaciones diferentes. 
Como se mostró en el caso 1, eliminar la llave J no provoco que el contenido de la página 5 
caiga por debajo del mínimo número de llaves. Por ende, la solución no fue mucho más 
complicada que reacomodarlas llaves de esa página. 
En el caso 2 es más complicado, porque, si solo se elimina la M de la raíz, es más 
complicado reacomodar el árbol para que mantenga su estructura. 
En el caso 3 se elimina R de la página 7 y no se hace nada más, porque la página solo tiene 
una llave y el número mínimo de llaves para una página hoja en un árbol de orden 6 es: 
[6/2]-1=2 
Por lo tanto, se tienen que tomar medidas para arreglar este estado de insuficiencia. La 
acción correctiva consiste en redistribuir las llaves entre las páginas, esta debe de 
ocasionar un cambio en la llave que está en la página padre, para que continúe actuando 
como separador. 
En el caso 4 al eliminar la letra A y no poder hacer redistribución con la pagina hermana lo 
que se hace es una concatenación tomando la página padre y las dos páginas hijas para 
crear una nueva página, pero se crea una nueva insuficiencia de datos en la página 
hermana de la página padre de la A. 
En el caso 5 resolvemos el problema que quedo en el caso 4, de igual manera hacemos 
una evaluación para ver si la página hermana tiene una llave de sobra para hacer 
ARBOLES DE TIPO B 
 
9.13 Eliminación, 
Redistribución y 
Concatenación 
 
redistribución, pero al solo tener las necesarias se opta por una concatenación, se toma la 
página padre que es la raíz de nuestro árbol y se concatena con sus dos hijas. 
El caso 6 muestra lo que pasa cuando la concatenación llega hasta la raíz de nuestro árbol 
lo que hace que este mismo disminuya su altura. 
 9.13.1 
Aquí se habla de las diferencias que hay en la redistribución a diferencia de la concitación y la 
división. 
A diferencia de la división y la concatenación la redistribución no se propaga, todos sus efectos son 
locales, esto se refiere a que todos sus efectos suceden entre páginas “hermanas” de la misma 
página padre. 
En la redistribución no existe una regla fija para la reacomodación de las llaves, una eliminación en 
un árbol B bien estructurado no puede causar una insuficiencia de más de una llave. 
La redistribución por lo tanto puede restituir las propiedades del árbol B trasladando solo una llave 
de un hermano a la página que ha tenido la insuficiencia, aun cuando la distribución de las llaves 
entre la página sea dispareja. 
9.14 Redistribución durante la 
inserción 
Prácticamente en los arboles B su inserción no necesita una operación análoga de redistribución 
sin embargo nunca está de más optimizar cuestiones de saturación. Dicho de otra forma, la 
redistribución durante la inserción es una forma muy efectiva de para mejorar la utilización del 
almacenamiento haciendo al árbol B un poco más eficiente. 
La lectura nos deja una reflexión sobre, aunque la importancia de la eficiencia de almacenamiento 
es recomendable el uso de la redistribución como alternativa de la división sea usado solo cuando 
sea posible, y de dividir una página solo cuando ambos hermanos estén completos. 
9.15 Árboles B* 
Este árbol es una pequeña al árbol B convencional que nos permite aprovechar mucho mejor el 
espació de las páginas ya que antes utilizábamos mínimo la mitad del almacenamiento de una 
página pero esta mejora hace que mínimo utilicemos dos terceras parte de cada página que no sea 
la raíz, pero desde mi punto de vista creo que se vuelve más complejo y difícil el manejo del árbol 
ya que tendremos que cambiar nuestros métodos de eliminación y de redistribución para que se 
adapten a las nuevas características. Además de que no solo eso debe de cambiar sino el uso de 
nuestra página raíz ya que para permitirle dividirse y que sus hijos cumplan con las características 
de este árbol, será necesario que permitamos un tamaño mayor de almacenamiento a la raíz y 
usar métodos específicos para sí mismo. 
9.16 Manejo de páginas virtuales en 
buffers 
Estas mejoras aplicadas al Árbol B Virtual aunque aumentan la cantidad de memoria RAM utilizada 
por el sistema, reducen considerablemente el acceso a disco por búsqueda, lo que, a fin de 
cuentas, siguen manteniendo el uso de la RAM al mínimo, por lo cual, si se tiene la posibilidad de 
utilizar más RAM, es una excelente medida para implementar en cuanto a búsquedas constantes 
de información, ya que al mantener, la página raíz únicamente, o también mantener las páginas 
principales, aumentan considerablemente las posibilidades de que la información requerida se 
encuentre ya en memoria principal, evitando de esta forma desperdiciar tiempo y memoria al 
tratar de ingresar a almacenamiento secundario. 
9.17 Colocación de la información 
asociada con la llave. 
En cualquier aplicación real la información asociada es el verdadero objeto de interés. Por lo 
regular es la información asociada con la llave la que en realidad se desea encontrar. 
Es importante preguntar dónde y cómo almacenar la información indizada por las lleves en el 
árbol. 
Fundamentalmente se tiene dos opciones: 
 Almacenar la información en el árbol B junto con la llave 
 Colocar la información en un archivo separado; dentro del índice se acopla la llave con un 
número relativo de registro, o un byte apuntador de dirección que hace referencia a la 
localización de la información en ese archivo separado. 
Las ventajas que tiene el prime enfoque sobre el segundo es que una vez que se encuentra la llave, 
no se requiere más accesos a disco. La información está ahí con la llave. Sin embargo, si la cantidad 
de información asociado con cada llave es relativamente grande, entonces almacenarla con la 
llave reduce el número de llaves que pueden colocarse en una página del árbol B. A medida que se 
reduce el número de llaves por página, se reduce el orden del árbol y tiende a ser de mas altura, 
ya que hay menos descendientes de cada página. 
La ventaja del segundo método es que, suponiendo que la información asociada es de gran 
longitud en relación con la longitud de la llave, colocar la información asociada en otro lugar 
permite construir un árbol de orden más alto. 
En general, entonces la decisión acerca de donde conviene almacenar la información debe guiarse 
por algunos cálculos que comparen las profundidades de los árboles que resultan. El factor crítico 
que influye en estos cálculos es la relación que guarda la longitud del registro completo con la 
longitud de solo una llave y el apuntador. Si pueden ponerse muchas parejas llave/apuntador en el 
área requerida para una sola pareja completa llave/registro, es recomendable la eliminación de la 
información asociada del árbol B y su colocación en un archivo separado. 
9.18 Registros y Llaves de Longitud 
Variable. 
Si bien es cierto, muchas de las aplicaciones actuales al manejar información relacionada 
con una llave esta puede variar en longitud, por lo tanto, aquí se nos presenta un 
incidente muy peculiar en el que contradecimos las características y algunas de las reglas 
de un Árbol B. Recordemos que un Árbol B es de algún orden”. Cada página tiene un 
número fijo
máximo y mínimo de llaves que puede almacenar, por lo tanto, la idea de 
implementar un registro de longitud variable hasta este punto es un cambio de 
perspectiva realmente notable. 
Un árbol B con un número variable de llaves por página no tiene claramente un orden fijo 
único. 
Sin embargo, esta situación nos deja grandes posibilidades que podemos utilizar para 
mejorar la eficiencia de un Árbol B, como: Utilizar una estructura con campos de longitud 
variable el cual como bien se sabe combate la fragmentación interna, ahora a eso le 
agregamos que en lugar de usar un número máximo y mínimo de llaves por página se 
utilice un máximo y mínimo de bytes no romperemos reglas de un Árbol B al tener una 
cantidad preestablecida de espacio y esto nos permitirá manipular el espacio de mejor 
manera aprovechando el mismo para poder asignar una mayor cantidad incluso de llaves 
por página incrementando así la cantidad de sus respectivos descendientes y a su vez 
probablemente un Árbol con menos niveles. 
Esto nos deja una mejor idea de su implementación en aplicaciones actuales incluso 
sabiendo que pueden desarrollarse e implementarse mejoras como mejorar la promoción 
de llaves, las llaves más pequeñas a niveles superiores y las más grandes en inferiores, y 
como bien sabemos esto nos dará un Árbol B con un mínimo de niveles y mayor cantidad 
de descendientes aprovechando la variabilidad. 
Comparación de índices con árboles. 
Un índice es una forma de encontrar de forma sencilla un registro sin tener que 
buscar registro por registro, esto se hace por medio de llaves y estructuras de 
datos simples. 
Podríamos decir que un índice es como el directorio de una biblioteca donde se 
encuentran muchos tipos de libros, autores y clasificaciones, entonces podemos 
dividir todos estos libros por su contenido ya sea de investigación, novelas, cocina 
o podría ser por el título del libro o el autor del mismo, todas estas formas de 
clasificarlos se podrían denominar como sus llaves, entonces dando una 
búsqueda por el libro o el autor que estamos buscando estamos acortando el 
tiempo de búsqueda para encontrar el libro de nuestra referencia, así es como se 
podrían explicar los índices en las estructuras de datos. 
A su vez los árboles son los índices llevados a un campo de registros más 
grandes, estos pueden guardar miles de datos y acceder a estos con muy pocos 
movimientos ahorrando memoria RAM y sin tanta perdida de datos. 
Su invención se hizo ya que muchas veces era imposible guardar registros de 
tanta capacidad de almacenamiento por lo que se tenía que ahorra la mayor 
capacidad de almacenamiento tanto de memoria RAM como de memoria 
secundaria. 
A comparación de otros medios de índices estos pueden acceder a los datos 
almacenados de hasta un millón de registros en menos de 4 desplazamientos a 
comparación de una búsqueda binaria que le llevaría aproximadamente más de 20 
desplazamientos. 
Integrantes 
Carrillo Magallanes Fernando 
Corral Barajas Carlos Alejandro 
Gutiérrez Ramírez Felipe de Jesús 
Musich Flores Branco 
Ríos Vergara Isaac Mijael 
Rodríguez Gómez Jimena Fernanda 
 Romero Proa Juan Manuel