Equipo4 - Fernando Cesar Sandoval Padilla

Vista previa del material en texto

La familia de los arboles B+ y el acceso a los archivos secuenciales indizados
(10.1 – 10.6).
Delgadillo Gutiérrez Jonatan Esaú
Esqueda Ortiz Andrea Guadalupe
Garibay Guerra Luis Ángel
Gómez Gutiérrez Hugo
Hernández Barajas Daniela Estefanía
Navarro Sánchez Jorge
Panduro Partida María Elizabeth
EQUIPO 4
10.1 ACCESO SECUENCIAL INDIZADO.
Las estructuras de archivos secuenciales indizados permiten elegir entre dos formas alternativas de visualizar un archivo:
Indizado: el archivo puede verse como un conjunto de registros indizado por llave.
Secuencial: se puede acceder secuencialmente el archivo (con registros físicamente contiguos, sin hacer desplazamientos), devolviendo los registros en el orden de la llave.
La idea de tener un solo método organizacional que proporcione los puntos de vista pasados es nueva; hasta ahora se había tenido que elegir alguno de ellos.
Como un ejemplo ilustrativo, de la divergencia potencial de estas dos opciones, supóngase que se ha desarrollado una estructura de archivo que consiste en un conjunto de registros de entradas secuenciales, indizados por un árbol B separado.
Esta estructura puede dar un excelente acceso indizado a cualquier registro individual por llave, aun cuando se agreguen o eliminen registros. 
Ahora supongamos que también se desea usar este archivo como parte de una intercalación secuencial coordinada. En el procesamiento secuencial coordinado se desea extraer todos los registros en el orden de la llave. 
Puesto que los registros reales en este archivo están en secuencia de entrada, y no físicamente clasificados por llave, la única forma de extraerlos en el orden de la llave es por medio del índice.
10.2 MANTENIMIENTO DE UN CONJUNTO DE SECUENCIAS.
Se enfocará el problema de mantener un conjunto de registros en orden físico por llave mientras se agregan o eliminan registros. A este conjunto ordenado se le denomina conjunto de secuencias. 
Subtemas:
10.2.1 Uso de Bloques
10.2.2 Elección del tamaño del bloque
USO DE BLOQUES
En consecuencia, el tamaño de los buffers que se usan en un programa permite almacenar un bloque entero. Después de leer un bloque, todos los registros del bloque están en memoria RAM, donde se pueden manejar o reacomodar mucho más rápidamente. 
Como sucede con los árboles B, la inserción de nuevos registros en un bloque puede hacer que el bloque se sature. Por ejemplo, la figura 10.1 muestra cómo se ve el conjunto de secuencias en bloques antes de realizar cualquier inserción o eliminación. 
Nótese que este proceso de división de bloques es diferente del de los árboles B. La eliminación de registros puede ocasionar que un bloque esté lleno a menos de la mitad y, por lo tanto, presente insuficiencia.
Si un nodo vecino también está medio lleno, se pueden concatenar los dos nodos, con lo que se libera uno para que pueda usarse de nuevo.
Si los nodos adyacentes están llenos hasta más de la mitad, los registros pueden redistribuirse entre los nodos para hacer que la distribución sea más equilibrada.
USO DE BLOQUES
Como ocurre con la inserción, el proceso para el conjunto de secuencias es más simple que el proceso para los árboles B porque el conjunto de secuencias no es un árbol y, por lo tanto, no existen llaves ni registros en un nodo padre.
Tomando en cuenta la separación de registros en bloques, junto con estas operaciones fundamentales de división, concatenación y redistribución de bloques, puede mantenerse un conjunto de secuencias en orden de llaves sin tener que clasificar todo el conjunto de registros.
Sin embargo, pueden aplicarse los mismos tipos de estrategias empleadas para incrementar la utilización de espacio en un árbol B. Una vez más, la implantación de cualquiera de estas estrategias debe tomar en cuenta el hecho de que el conjunto de secuencias no es un árbol y que, por lo tanto, no hay promoción de registros.
10.2.2 ELECCION DEL TAMAÑO DEL BLOQUE
Al trabajar con el conjunto de secuencias, el bloque es la unidad básica para las operaciones de E/S. Cuando se leen datos del disco, nunca se lee menos de un bloque; cuando se escriben datos, siempre se escribe al menos un bloque.
Un bloque también es, como se ha dicho, la máxima extensión garantizada de una secuencia física, de ahí que deba pensarse en términos de bloques grandes, cada uno con muchos registros.
Consideración 1: El tamaño de bloque deber ser tal que puedan almacenarse varios bloques en memoria RAM a la vez. Sí se hace la división de dos a tres para conservar el espacio en disco, es necesario almacenar al menos tres bloques en memoria RAM a la vez.
Se tiene que leer un bloque entero para llegar a cualquier registro dentro de ese bloque.
Consideración 2: Leer o escribir un bloque no debe tomar demasiado tiempo. Incluso si se tuviera una cantidad ilimitada de memoria RAM, conviene colocar un límite superior al tamaño de bloque de modo que no se termine leyendo el archivo entero para llegar a un solo registro.
Esta no es una limitación obligatoria, pero es razonable: nos interesa un bloque porque contiene registros que están físicamente adyacentes, así que no se van a extender los bloques más allá del punto en el que pueda garantizarse dicha adyacencia.
Un cúmulo es el mínimo número de sectores asignados a la vez. Si un cúmulo consiste en ocho sectores, como en un disco fijo normal en un computador IBM PC/XT, entonces incluso un archivo que contenga sólo un byte usa los ocho sectores en el disco.
La razón de hacer cúmulos es que se garantiza una cantidad mínima de «secuencialidad» física. Cuando nos movemos de cúmulo en cúmulo en la lectura de un archivo, puede hacerse un desplazamiento en disco, pero dentro de un cúmulo se puede acceder a los datos sin él.
Así, una sugerencia razonable al elegir el tamaño del bloque es hacer cada bloque igual al tamaño de un cúmulo. 
Con frecuencia el tamaño del cúmulo en un sistema de discos ya ha sido determinado por el administrador del sistema. 
Entonces será necesario considerar los aspectos relacionados con el tamaño del cúmulo que aparecen en el capítulo 3, junto con las restricciones impuestas por la cantidad disponible de memoria RAM y el número de bloques que se desee almacenar en la memoria a la vez.
10.3 Adición de un indice simple al conjunto de secuencias
Se ha creado un mecanismo para mantener un conjunto de registros de modo que se pueda acceder a ellos en forma secuencial en el orden de la llave. Esto está basado en la idea de agrupar registros en bloques y mantener los bloques, conforme se insertan y eliminan registros, por medio de la división, concatenación y redistribución. 
Puede considerarse que cada uno de los bloques contiene un intervalo de registros 
Este es un punto de vista externo respecto a los bloques (en realidad no se ha leído ningún bloque, por lo que no se sabe exactamente lo que contienen), pero es lo bastante informativo para ayudar a elegir el bloque que quizá tenga el registro que se busca. 
La combinación de este tipo de índices con el conjunto de secuencias de bloques proporciona acceso secuencial indizado completo. Si es necesario extraer un registro específico, se consulta el índice y después se extrae el bloque correcto.
si se necesita acceso secuencial, se comienza en el primer bloque y se lee en la lista ligada de bloques hasta que se han leído todos. 
A este método tan simple se le puede sacar mucho provecho siempre y cuando el índice pueda almacenarse en la memoria electrónica RAM. 
El requisito de que el índice esté almacenado en memoria RAM es importante por 2 razones:
Razón 1. 
Los registros específicos se encuentran por medio de una búsqueda binaría en el índice. La búsqueda binaria funciona bien si se realiza en memoria RAM, pero, requiere demasiados desplazamientos si el archivo está en un dispositivo de almacenamiento secundario. 
Razón 2.
Conforme cambian los bloques en elconjunto de secuencias por medio de la división, concatenación y redistribución, el índice tiene que actualizarse 
¿Qué se hace si el archivo contiene tantos bloques que el índice de bloques no entra en forma concerniente dentro de la memoria RAM?
En el capítulo anterior se encontró que la estructura del índice podía dividirse en páginas, en forma muy similar a los bloques que se analizan aquí, manejando a la vez varias páginas, o bloques, del índice en memoria RAM. 
El uso de un índice en árbol B para el conjunto de secuencias de bloques es, de hecho, un concepto poderoso. La estructura híbrida resultante se conoce como árbol B*t lo cual es apropiado porque es un índice en árbol B más un conjunto de secuencias que almacena los registros reales. 
10.4 CONTENIDO DEL INDICE: SEPARADORES EN LUGAR DE LLAVES
El propósito del índice es asistir al usuario cuando busca un registro con una llave específica, podría decirse que es un mapa.
Por ende, se puede reconocer que no es necesario tener llaves reales en el conjunto índice. La necesidad real es de separadores.
Existen muchos separadores potenciales capaces de distinguir entre dos bloques.
SÍ se decide tratar a los separadores como entidades de longitud variable en la estructura del índice, puede ahorrarse espacio colocando el separador más corto en la estructura del índice. 
Por ejemplo, se usa E como separador para guiar la elección entre los bloques 3 (DUTTON) y 4 (EVANS). No siempre existe un único separador más corto. Por ejemplo, BK, BN y BO.
Figura 10.5 Una lista de separadores potenciales.
10.5 ARBOLES B* DE PREFIJOS SIMPLES
Al índice en forma de árbol B se le llama conjunto índice, y éste y el conjunto de secuencias forman una estructura de archivos llamada árbol B* de prefijos simples. 
Los separadores son las letras iniciales de las llaves.
También se pueden crear separadores a partir de prefijos de llaves, eliminan caracteres innecesarios del inicio de los separadores, así como del final.
El registro con la llave EMBRY, se comienza en la raíz del conjunto índice, comparando EMBRY con el separador E. Puesto que EMBRY viene después de E, se va hacia la derecha y se extrae el nodo que contiene los separadores F y FOLKS. Puesto que EMBRY está aún antes que el primero de estos separadores, se sigue la rama que está a la izquierda del separador F, la cual lleva al bloque 4, el correcto en el conjunto de secuencias.
10.6 MANTENIMIENTO DE ARBOLES B+ DE PREFIJOS SIMPLES 
10.6.1 Cambios localizados en bloques individuales del conjunto de secuencias 
10.6.2 Cambios que involucran varios bloques en el conjunto de secuencias 
10.6.1 CAMBIOS LOCALIZADOS EN BLOQUES INDIVIDUALES DEL CONJUNTO DE SECUENCIAS 
Supongamos que se quiere eliminar los registros de EMBRY y FOLK y que esto da como resultado una concatenación o redistribución dentro del conjunto índice. Como no hay concatenación o redistribución^ el efecto de estas eliminaciones en el conjunto de secuencias está limitado a cambios dentro de los bloques 4 y 6
El registro que antes era el segundo en el bloque 4 (digamos que su llave es ERVIN) es ahora el primer registro. De igual modo, el que era el segundo registro del bloque 6 (se supone que tiene una llave FROST) inicia ahora ese bloque. 
El efecto que tiene insertar dentro del conjunto de secuencia registros nuevos que no provocan división del bloque es, en gran medida, el mismo que tienen estas eliminaciones que no dan como resultado la concatenación: El conjunto índice permanece sin cambio. 
La cuestión más interesante es cuál será el efecto, si lo hay. de estas eliminaciones en el conjunto índice. La respuesta es que, debido a que el número de bloques del conjunto de secuencias no cambia, y a que ningún registro se mueve entre los bloques, el conjunto índice puede también permanecer sin cambios.
Esto es fácil de ver en el caso de la eliminación de EMBRY: E sigue siendo un separador adecuado para los bloques 3 y 4 del conjunto de secuencias, así que no hay razón de cambiarlo en el conjunto índice
10.6.2 CAMBIOS QUE INVOLUCRAN VARIOS BLOQUES EN EL CONJUNTO DE SECUENCIAS 
¿Qué sucede cuando la inserción o eliminación de registros del conjunto de secuencias hacen cambiar el número de bloques? Resulta claro que si se tienen más bloques, se necesitan separadores adicionales en el conjunto índice, y si se tienen menos bloques, se necesitan menos separadores. 
Cambiar el número de separadores ciertamente tiene efecto en el conjunto índice, donde se almacenan los separadores. Puesto que el conjunto índice para un árbol B* de prefijos simples es en realidad sólo un árbol B normal, los cambios en el conjunto índice se manejan de acuerdo con las reglas familiares para la inserción y eliminación en árboles B.
El siguiente ejemplo se supone que el conjunto índice es un árbol B de orden tres, lo cual significa que el máximo número de separadores que pueden almacenarse en un nodo es dos. Se usa este pequeño tamaño de nodo del conjunto índice para ilustrar la división y concatenación de nodos usando sólo unos cuantos separadores. Como se verá posteriormente, en la implantación real de árboles B* de prefijos simples se colocan muchos más separadores en un nodo del conjunto índice.
Se comienza con una inserción dentro del conjunto de secuencias que se muestra en la figura 10.9. En forma específica, se va a suponer que hay una inserción en el primer bloque, y que esta inserción hace que el bloque se divida. Se trae un bloque nuevo (el bloque 7) para almacenar la segunda mitad de lo que era originalmente en el primer bloque. Este nuevo bloque se liga dentro de la posición correcta en el conjunto de secuencias, siguiendo al bloque 1 y precediendo al bloque 2 (éstos son los números físicos de los bloques). Estos cambios al conjunto de secuencias se ilustran en la figura 10.10. 
Nótese que el separador que antes distinguía entre los bloques 1 y 2, la cadena BO, es ahora el separador de los bloques 7 y 2. Se necesita un nuevo separador, con un valor AY, para distinguir entre los bloques 1 y 7. Al colocar este separador dentro del conjunto índice se encuentra que el nodo dentro del cual se desea insertarlo, que contiene BO y CAM, ya está lleno. En consecuencia, la inserción de un nuevo separador provoca una división y promoción, de acuerdo con las reglas usuales para árboles B+ El separador promovido, BO, se coloca en la raíz del conjunto índice. 
Figura 10.10
GRACIAS
7 de Mayo del 2020