Equipo 2_EXPO - Fernando Cesar Sandoval Padilla

Vista previa del material en texto

Equipo 2
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
Árboles B
9.7 Árboles B: construcción Ascendente 
Muchas se han aplicado en las ciencias de la computación surgieron al cambiar el enfoque para examinar el problema, los Árboles B son un ejemplo de este fenómeno de cambio de punto de vista
Ejemplo de árbol B 
9.7 Árboles B: construcción Ascendente 
La idea clave de esta solución de los árboles B es que puede elegirse construir los árboles hacia arriba a partir de la base, en lugar de hacerlo hacia abajo desde la cima, Generalmente se ha dado por hecho la necesidad de iniciar la construcción a partir de la raíz.
 Luego al descubrir que se tienen llaves equivocadas en la raíz se ha intentado encontrar formas para corregir el error con algoritmos de reacomodo 
Bayer y mcCreight se dieron cuenta que el problemas estaba en trabajar hacia abajo a partir de la raíz
así en lugar de pensar como resolver la situación, decidieron evitar los problemas y con los árboles B se permite que la raíz emerja en vez de colocarse
9.8: División y Promoción
En un árbol B, los nodos consisten en una secuencia de llaves y un conjunto de apuntadores. Los campos marcados con asteriscos son los campos apuntadores. Por definición un nodo hoja no tiene hijos en un árbol.
Una aplicación práctica existe información guardada en llaves como referencia de un registro que contiene registros de datos asociados que se almacenan en otro lugar.
9.8: División y Promoción
Se usa un árbol de orden 4 (cuatro campos apuntadores y tres campos llave por página) porque corresponde al tamaño de página binario paginado. Usar ese tamaño de página tiene como ventaja adicional que las páginas se dividan con mayor frecuencia, proporcionando más ejemplos de división y promoción.
9.9 Algoritmos para la búsqueda e inserción en Árboles B
Estructura de la página:en un nodo de árbol B tiene un número máximo de llaves y de hijos (MAXLLAVES Y MAXHIJOS).
En este caso el árbol tiene los datos
D,H,K.
y sus hijos son la páginas 0(A,B,C),3(E,G),8(I,J),5(L,M)
Como se muestra en la imagen tiene un contador de llaves (3), y seguido tiene el contenido(D,H,K) y las páginas hijos(0,3,8,5)
Contenido de la página 2 y 3
Búsqueda: el procedimiento de búsqueda es recursivo, donde se busca en un árbol, elemento por elemento dentro del árbol, en dado caso de que se encuentre el elemento termina la recursividad, en caso contrario si el elemento en el árbol es mayor al elemento que buscamos, entonces busca en el subárbol entre el elemento que es menor y el elemento que es mayor y así sucesivamente, se puede llegar a una página sin hijos(subárboles) y el elemento no se llegaría a encontrar.
En el caso de buscar I en éste árbol
I es mayor a H pero menor que K, por lo que buscaríamos en el subárbol entre H y K, en este subárbol ya se encuentra el elemento que buscamos
Inserción, División y Promoción
Antes de insertar $
Después de insertar $
Un paso de búsqueda en páginas que, como en la función busca(), ocurre antes de la llamada recursiva.
Inicia la recursividad,que mueve la operación hacia abajo en el árbol conforme busca ya sea la llave o el lugar para
insertarla.
La lógica que se ejecuta después de la llamada recursiva, la acción tiene lugar en la trayectoria de vuelta luego del descenso recursivo.
Ejemplo: se inserta el carácter $
 Conforme regresa cada llamada recursiva se ejecuta la lógica de inserción y división en ese nivel. Si la función de nivel inferior devuelve el valor promoción entonces se tiene una llave para insertar en ese nivel.
El Nivel Superior:
Se necesita una rutina para unir los procedimientos inserta() y divide() y para realizar algunas operaciones que las rutinas de nivel inferior no llevan a cabo.
El manejador debe llevar a cabo:
-Abrir o crear el archivo del árbol B, e identificar o crear la página raíz.
-Leer las llaves que van a almacenarse en el árbol B, y llamar a insertar() para colocarlas.
-Crear un nuevo nodo raíz cuando inserta() divide la página que en ese momento es la página raíz
Primero se copia el contenido de la página a una página auxiliar “Pagina de trabajo”
Se inserta la entrada en la “Pagina de trabajo”
El contenido de la “página de trabajo” se divide en “Página” y “Página Nueva”, excepto por la llave de enmedio (H).
“H” se mueve junto con el nrr(12) de “Página Nueva”
9.10 Nomenclatura de Árboles B
Terminología sobre los árboles B:
Desgraciadamente, en el ámbito de de los árboles B, la información existente sobre ellos es muy variada, por ello siempre se debe estar actualizado, para saber los nuevos desarrollos.
-Orden:
Varios autores, entre ellos Bayer y McCreight[1972] se refieren al orden como el mínimo número de llaves que pueden estar dentro de una página de un árbol. El problema de esta definición es que se vuelve bastante complicado aplicar cuando se quiere almacenar un número máximo de llaves que es Impar.
								
Metele nitro papi
9.10 Nomenclatura de Árboles B
Compaginado con esto, Knuth[1973b], entre otros, resolvió esta confusión de par/impar definiendo al Orden como el número máximo de descendientes que puede tener una página. Al igual que dice que el número de llaves es uno menos que el número de de descendientes en la misma página.
-Hoja:
Este es otro de los términos que los autores emplean de distintas formas, por ejemplo:
Los autores Bayer y McCreight[1972] mencionan que se refiere al nivel más bajo de llaves dentro de un árbol B como el nivel hoja.
Por otro lado, el autor Knuth considera que son los registros de datos reales a los que cuales se puede apuntar por el nivel más bajo de llaves de un árbol.
9.11 Definición formal de las propiedades de los árboles B
Con estas definiciones de orden y hoja pueden firmarse una definición precisa de las propiedades de una árbol B de orden m
Cada página tiene un máximo de m descendiente.
Cada página excepto la raíz y las hojas, tiene por lo menos [m/2] descendientes.
La raíz tiene por lo menos dos descendientes (a menos que sea una hoja).
Todas las hojas aparecen en el mismo nivel.
Una página que no es hoja con k descendientes contiene k-1 llaves.
Una página hoja contiene por lo menos [m/2]-1 llaves y no más de m-1 llaves.
9.12 Profundidad de la búsqueda en el peor caso
Se debe comprender en términos cuantitativos la relación que tiene la página de un árbol B, número de llaves en el árbol y el número de niveles que tiene.
En el peor caso ¿cuál será el número máximo de accesos al disco para encontrar una llave? y eso es igual a buscar la profundidad que tendrá el árbol.
Ejemplo: si se tienen 1000000 de llaves se crea un árbol binario de orden 512 llaves por página que en si serian 511 registros por página 
El número de descendientes de cualquier nivel de un árbol B es uno más que el número de llaves contenidas en el nivel.
Un árbol B con N llaves puede tener (N+1) descendientes a partir del nivel hoja
Profundidad de la búsqueda en el peor caso
Número mínimo de descendientes
Para cualquier nivel D de un árbol binario el mínimo número de descendientes se extiende a partir del nivel 
Número mínimo de descendientes
A la profundidad del árbol en el nivel hoja se le llamará d.Un árbol con N llaves N+1 descendientes y Se puede expresar la relación entre los N+1 descendientes y el número mínimo de descendientes de un árbol de altura d como: 
Puesto que se sabe que el número de descendientes de cualquier árbol no puede ser menor que el número para el peor caso de un árbol de esa profundidad. Despejando d, se llega a lo siguiente:
Número mínimo de descendientes
Ejemplo:
En un árbol de orden 512 el cual tiene 1000000 llaves al sustituir la información en la expresión se tiene que 
 dando como valor así se puede saber que dadas 1000000 de llaves en un árbol binario de orden512 cuenta con una profundidad no más de tres niveles.