Unidad III

Archivos secuenciales indexados.

La indexación es una técnica que se ha utilizado desde hace mucho tiempo para optimizar

los accesos a los registros de ficheros. En sí no es un tipo de fichero, y el concepto de

fichero indexado se refiere a un fichero secuencial que contiene la indexación de otro

fichero. Para hacernos una idea más aproximada de ésto, imaginemos un fichero

secuencial de, por ejemplo, una agenda de clientes. La información puede ser basta y el

tener ordenada la información o buscar un determinado cliente puede ser harto lento y

costoso. Para ello, creamos un "fichero indexado", que contendrá únicamente la

información clave por la que buscar u ordenar, en nuestro caso por apellidos y nombre.

Así pues, cada fila de este fichero contendrá la concatenación de los apellidos más los

nombres, y un segundo campo que contiene el número de fila al que referencia en el

fichero secuencial original (a modo de índice, tal y como su nombre sugiere). Este fichero,

antes de escribirse debe ser procesado en memoria (en un array dinámico, por ejemplo)

en donde, mediante un algorritmo de ordenación (burbuja, dispersación, shell, quicksort)

se ordenan las filas que conformarán el orden del fichero original. Cuando se vaya a tratar

el fichero original, se carga el fichero indexado en memoria (mediando un vector o una

hash). Se operará la búsqueda en este información que hay en memoria (al tener sólo la

información clave, ocupa mucho menos memoria, es más rápido (al estar en memoria) y

ya está ordenado). Una vez localizado el dato, se recoge el campo del número de registro.

Se abre el fichero original como aleatorio y se accede directamente a dicho registro.

3.1 Estructura de la organización secuencial indexado

El archivo secuencial indexado mantiene las características básicas de los archivos secuenciales: los registros están organizados en una secuencia basada en un campo. Dos características se añaden: un índice del archivo para soportar los accesos aleatorios y un archivo de desbordamiento (overflow).

Un archivo está organizado en forma secuencial indexada si:

El tipo de sus registros contiene un campo clave identificador. Los registros están situados en un soporte direccionable por el orden de los valores

indicados por la clave.

Existe un índice con cada una de las posiciones direccionables, que almacena la dirección de la posición y el valor de la clave; en esencia, el índice contiene la clave del ultimo registro y la dirección de acceso al primer registro del bloque.

Un archivo en organización secuencial indexada consta de las siguientes partes:

Área de datos o primaria: contiene los registros en forma secuencial y está organizada en secuencia de claves sin dejar huecos intercalados.

Área de índices: es una tabla que contiene los niveles de índice; la existencia de varios índices enlazados se denomina nivel de indexación.

Área de desbordamiento o excedentes: utilizada, si fuese necesario, para las actualizaciones.

El área de índices es equivalente, en su función, al índice de un libro. En ella se refleja el valor de la clave identificativa más alta de cada grupo de registros del archivo y la dirección de almacenamiento del grupo.

Los archivos secuenciales indexados presentan las siguientes ventajas:

Rápido acceso El sistema de gestión de archivos se encarga de relacionar la posición de cada

registro con su contenido mediante la tabla de índices.

Y los siguientes inconvenientes:

Desaprovechamiento del espacio, por quedar huecos intermedios cada vez que se eliminan.

Se necesita espacio adicional para el área de índices.

Los soportes que se utilizan para esta organización son los que permiten el acceso directo

como los discos magnéticos. Los soportes de acceso secuencial no pueden utilizarse, ya

que no disponen de direcciones para sus posiciones de almacenamiento.

3.2 Representación de indices

La principal función de un índice dentro de una organización secuencial indexada es proveer una capacidad de búsqueda para llegar rápidamente a las proximidades de un registro deseado.

En la estructura secuencial indexada más simple, se usa un solo nivel de indexación. El índice, en este caso, es un archivo secuencial simple. Cada registro del archivo índice tiene dos campos: un campo clave, que es el mismo que el campo clave del archivo principal y un puntero al archivo principal. Para encontrar un campo específico se busca en el índice hasta encontrar el valor mayor

de la clave que es igual o precede al valor deseado de la clave. La búsqueda continúa en el archivo principal a partir de la posición indicada por el puntero.

El campo clave-secundaria sobre el cual se crea un índice se llama clave inversa o clave indexada.

Se dice que una clave inversa esta parcialmente indexada si solo algunos de sus valores claves están incluidos en el índice valor-clave. Los valores clave que están indexados son aquellos usados en la condiciones de búsqueda. Un índice parcialmente indexado se llama índice disperso. Para un índice con una gran cantidad de elementos, la búsqueda secuencial sobre el índice no es muy eficiente. Por esto, un índice se organiza generalmente como una estructura de varios niveles como es el caso de la estructura multinivel de índice principal para los archivos secuenciales indexados.

Cada vez que se inserta, borra o actualiza un registro, las entradas afectadas de un índice deben ser modificadas para que así, el índice pueda proporcionar las trayectorias de datos correctas.

Para poder estructurar esta organización (secuencial indexada) podemos utilizar uno de los métodos más comunes que es el de construir el índice como un árbol de valores llave. Otro método común es de construir el índice basándose en la disposición física de los datos almacenados.

Para poder instrumentar esta organización existen algunas técnicas como lo son:

Estructuras de árbol B +: 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.

Esquema de un árbol B+:

Esquema físico de índices

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.

Tras la decisión del tipo de organización que ha de tener el archivo y los métodos de acceso que se van a aplicar para su manipulación, es preciso considerar todas las posibles operaciones que conciernen a los registros de un archivo.

3.3 Operaciones con archivos secuenciales indexados

Las distintas operaciones que se pueden utilizar son:

Creación Apertura Consulta Actualización (altas, bajas, modificación, consulta) Clasificación Reorganización Destrucción, (borrado) Reunión, fusión Rotura, estallido

Creación de un archivo.- Es la primera operación que sufrirá el archivo de datos. Implica la elección de un entorno descriptivo que permita un ágil, rápido y eficaz tratamiento del archivo. Para utilizar un archivo, éste tiene que existir, es decir, las informaciones de este archivo tienen que haber sido almacenadas sobre un soporte y ser utilizables.

Apertura de Archivos.- En este caso se pretende abrir un archivo ya existente en disco para procesarlo, ya sea cargar o grabar datos en sus registros, o leer algún registro en especial para mandarlo a una variable de cualquier tipo. No confundir creación con apertura, creación es un proceso que solo se ejecuta una sola vez en la vida de un archivo, mientras que apertura, siempre se esta realizando por los programas especializados en algún proceso.

Consulta de un archivo.- Es la operación que permite al usuario acceder al archivo de datos para conocer el contenido de uno, varios o todos los registros.

Actualización de un archivo.- Permite tener actualizado (puesto al día) el archivo, de tal modo que sea posible realizar las siguientes operaciones con sus registros:

Consulta del contenido de un registro. Inserción de un registro nuevo en el archivo. Supresión de un registro existente. Modificación de un registro.

Clasificación de un archivo.- Una operación muy importante en un archivo es la clasificación u ordenación (sort, en ingles). Esta clasificación se realizara de acuerdo con el valor de un campo especifico, pudiendo ser ascendente (creciente) o descendente (decreciente): Alfabéticamente o numérica.

Reorganización de un archivo.- Las operaciones sobre archivos modifican la estructura inicial o la optima de un archivo. Los índices, enlaces (punteros), zonas de sinónimos, zonas de desbordamiento, etc., se modifican con el paso del tiempo, lo que hace a la operación de acceso al registro cada vez más lenta. La reorganización suele consistir en la copia de un nuevo archivo a partir del archivo modificado, a fin de obtener una nueva estructura lo mas optima posible.

Borrar (destruir).- Es la operación inversa de un archivo (kill, en ingles). Cuando se destruye (anula o borra) un archivo, este ya no se puede utilizar y por consiguiente no se podrá acceder a ninguno de sus registros.

Fusión de un archivo.- Reunión. Esta operación permite obtener un archivo a partir de otros varios.

Rotura (dividir).- Es la operación de obtener varios archivos a partir de un mismo archivo

inicial.