domingo, 10 de junio de 2007

Archivos secuenciales indexados











de Archivos Secuenciales Indexados.
Una manera efectiva de organizar una colección de registros, cuando existe la necesidad de accesar los registros secuencialmente, por algún valor de llave, como de accesarlos individualmente, con esa misma llave, es la organización de archivos secuenciales indexados. Un archivo secuencial indexado proporciona la combinación de tipos de acceso que manejan un archivo secuencial y un archivo relativo.
Esta organización está diseñada para utilizar la combinación de la organización relativa y la secuencial, obteniendo la ventaja de poder acceder a los registros en forma secuencial y relativamente de manera directa.
Como se pude apreciar la organización de archivos secuenciales indexados es efectiva para satisfacer la necesidad tanto de acceder a los archivos en forma secuencial como de forma directa mediante algún valor de llave.
Para poder estructurar esta organización podemos utilizar uno de los métodos más comunes que es el de construir el índice como un árbol de valores llave como se vio anteriormente. Otro método común es de construir el índice basándose en la disposición física de los datos almacenados.
Esto nos da como consecuencia que nuestras aplicaciones crezcan, pudiendo ofrecer esta organización aplicaciones tanto en procesamiento por lotes como interactivo.
Para poder instrumentar esta organización existen algunas técnicas como lo son:
Estructuras de árbol B +. (en esquemas arriba).
Es una de las técnicas más populares para instrumentar esta organización. El árbol B+ consta de dos partes: la parte índice que consta de los nodos interiores y el conjunto secuencia que consta de las hojas del árbol.
La parte índice se usa para direccionar la posición de algún registro en particular , mientras que el acceder secuencialmente a las hojas (conjunto secuencia) podemos tener acceso a todo el archivo en general.
Ahora bien los valores de la llave dentro del índice solo existen con el propósito de dirigir el acceso al conjunto secuencia.
Ahora mostramos el esquema de un árbol B+

La composición de una hoja es como sigue:

Un nodo puede utilizar desde 2 hasta n ligas, mas no podemos manejar una sola, esto quiere decir que si un nodo maneja tres ligas podemos inhabilitar solo una.
Manipulación de un árbol - B+
La inserción de nuevos valores de llave en un árbol B+ se realiza más o menos de la misma manera como son insertados en un árbol - B clásico. Cuando un nodo hoja es particionado en dos nodos, una copia del valor de llave de menor orden, del nodo que se encuentra a la derecha, es promovida para ser el valor de llave separador en el nodo padre. El nuevo nodo también debe ser insertado en la lista ligada del conjunto de secuencias.
Búsqueda de árboles B+
Una búsqueda directa en un árbol B+ debe terminar en un nodo del conjunto de secuencias. Si existe una llave en el índice que corresponda a la llave buscada, el apuntador precedente es seguido hasta que, eventualmente, la hoja correcta es alcanzada. No todas las llaves de la parte de índices necesitan aparecer también en el conjunto de secuencias. Una llave pudo haberse eliminado del conjunto secuencias, cuando su correspondiente registro fue suprimido del conjunto de registros, pero la llave pudo haber sido retenida en la parte de índices del árbol B+, con el propósito de guiar el acceso al conjunto de secuencias.
Acceso Secuencial.
Una solicitud para accesar datos en orden secuencial es atendida accesando los bloques de datos en orden secuencial. Los bloques de datos son el conjunto de secuencias; son lógicamente consecutivos pero no están necesariamente físicamente consecutivos.
Esquema Físico De Indices
Otro método para implantar el concepto de archivo secuencial indexado, consiste en basar la estructura de índices más en las características físicas de almacenamiento que en la distribución lógica de valores de las llaves. El índice puede tener varios niveles, tal como un nivel de índice de pista. El archivo de datos es generalmente instrumentado como dos archivos: un área primaria y un área de sobrecarga.
La figura siguiente ilustra este tipo de estructura para el archivo secuencial indexado de datos de animales. (अर्रिबा)

Supongamos que cada cilindro del dispositivo de almacenamiento tiene cuatro pistas. Este archivo en particular tiene seis cilindros asignados al área primaria de datos. La primera pista (número 0) de cada cilindro contiene un índice a las llaves de los registros en ese cilindro. Las entradas a este índice son de la forma:
Valor de la llave menor, número de pista.
Dentro de una pista de datos, los registros son guardados secuencialmente con base en el valor de la llave. El primer nivel del índice en el archivo de índices es llamado índice maestro. Como se muestra en la figura anterior, las entradas a este índice son de la forma:
Valor de la llave mayor, número de cilindro
El segundo nivel de índice es llamado el índice de cilindro. Este contiene apuntadores al archivo primario de datos y sus entradas tienen la forma:
Valor de la llave mayor, número de cilindro.
Acceso a registros de datos
Cuando se recibe una solicitud de acceso a un registro en particular, digamos el registro con valor de llave Borrego, el índice maestro es examinado primero. Dado que Borrego precede a Lince, el apuntador desde Lince es seguido hasta el cilindro índice. Dado que Borrego precede a Elefante, el apuntador desde elefante es seguido hasta la pista 0 del cilindro 1. Dado que Borrego le sigue a Ballena es seguido a la pista 2, la cual es examinada secuencialmente hasta encontrar a Borrego y disponer de él, o hasta determinar que no existe. Una solicitud para accesar los datos en orden secuencial es atendida, accesando los cilindros y pistas del archivo primario de datos, en esa secuencia física.
Inserción de Registros
En el ejemplo anterior el área primaria de datos fue creada con 40% de espacio libre, con el objetivo de poder realizar inserciones y supresiones del archivo.
Las solicitudes:
Insertar Ardilla
Insertar Aguila
Son fáciles de lograr. Solamente la pista de datos 1 del cilindro 1 es afectada, por lo que el contenido resultante es el siguiente:
La solicitud de insertar armadillo es un poco mas difícil. La búsqueda en la estructura índice revela que armadillo debería ubicarse en la pista 1, del cilindro 1, pero esta pista está llena. Esta condición necesita del uso de un área de sobrecarga de datos en un archivo separado con respecto al área primaria de datos, pero está apuntadas por las entradas en el área primaria de datos.

Archivo De Sobrecarga De Datos