Estructura de Datos : Archivos ( Files )

Definiciones

Los Archivos ( Files ) son una colección de Registros ( Records ), donde cada uno de ellos consiste de uno o más Campos ( Fields ).
Ejemplo :

Empleados

Empleado_Numero
Empleado_Nombre
Empleado_Ocupacion
Empleado_Titulo
Empleado_Sexo
Empleado_Direccion
Empleado_Estado_Civil
Empleado_Salario

fig. 1 : Ejemplo de datos para el Archivo de Empleados

Registro	Campos	Claves	Primarias	Secundarias
Employee Number (E#)	Sí	Sí	Sí
Name	Sí
Occupation	Sí	Sí		Sí
Degree	Sí
Sex	Sí	Sí		Sí
Location	Sí
Marital Status (MS)	Sí
Salary	Sí	Sí		Sí

Los Objetivos de la estructura de datos archivo son :

Recuperar Registros

Actualizar Registros

Insersión de nuevos registros
Actualización de algunos campos de registros existentes
Eliminiación de registros existentes

Las Claves ( Keys ) son campos de los registros designados explicitamente como tales. Los Archivos pueden tener una clave o más de una clave.
Ejemplo :

Archivo_Empleados

Empleado_Numero
Empleado_Ocupacion
Empleado_Sexo
Empleado_Salario

Los Valores de las Claves ( Key Values ) pueden tener las siguientes limitaciones :

Los valores de las claves deben ser todos distintos.

Los valores de las claves pueden estar repetidos.

Los Modos de Recuperacion y Actualizacion ( Mode of Retrieval and Update ) son

Tiempo Real ( Real Time )

Por Lotes ( Batched )

Archivo de Transacciones ( Transaction File )
Archivo Maestro ( Master File )

Las Consultas ( Queries ) son combinaciones de valores de campos claves.

Los Tipos de Consultas ( Query Types ) son los siguientes :

Consultas Simples.
Cuando se especifica un valor de una clave simple.
Ejemplo : Empleado_Sexo = M.

Consultas Rangos.
Cuando se especifica un rango de valores de una clave simple.
Ejemplo : 10000 > Empleado_Salario > 9000.

Consultas Funcionales.
Cuando se especifica una función de los valores de una clave simple.
Ejemplo : Promedio Empleado_Salario.

Consultas Booleanas.
Cuando se especifica una combinación de consultas simples, rangos o funcionales usando los operadores booleanos and, or, not.
Ejemplo : ( Empleado_Sexo = M ) and ( Empleado_Ocupacion = Programador ) and ( Empleado_Salario > 3000 )

	Query	Tipo
Q1	Sex = M	Query Simple
Q2	Salary > 9000	Query Rango
Q3	Salary > salario promedio de todos los empleados	Query Funcional
Q4	(Sex = M and Occupation = Programmer) or (Employee Number > 700 and Sex = F )	Query Booleano

Los Dispositivos de Almacenamiento Externo ( DAE ) ( External Storage Devices ( ESD ) ) permiten disponer los datos de un archivo en un medio externo y persistente.
Ejemplos de ESD son los Dispositivos de Almacenamiento de Acceso Directo ( DAAD ) ( Direct Access Storage Devices ( DASD ) ), que son lo popularmente conocidos como Discos Magneticos, Disco Duro, Floppy Disk, Diskette o ZIPDisk.

Diferencias entre Tablas de Símbolos y Archivos

Las Tablas de Símbolos son suficientemente pequenas para contenerlas en la memoria principal de la computadora, mientras que los Archivos son suficientemente grandes como para requerir un medio de almacenamiento externo para disponerlos.

Organizaciónes de Archivos ( File Organizations )

Las Organizaciones de Archivos ( File Organizations ) son formas de disponer fisicamente los registros de los archivos en los medios de almacenamiento externo. Existen las siguientes organizaciones de archivos :

Organización Secuencial ( Sequential Organization )

Organización Azarosa ( Random Organization )

Organización Enlazada ( Linked Organization )

Organización Invertida ( Inverted Organization )

Organización Celular ( Cellular Organization )

Las Archivos se componen u organizan en dos partes, el Directorio ( Directory ) y los Datos ( Datas ).

El Directorio de un Archivo es una colección de Indices. Un Directorio puede tener un índice por cada clave o puede tener índices para solamente algunas claves.


           *-------------------------------------------------------------------*
           |                                                                   |
           |                            Directorio                             |
           |                                                                   |
           | *---------------------------------------------------------------* |
           | |                                                               | |
           | | *--------*       *--------*       *--------*       *--------* | |
           | | |        |       |        |       |        |       |        | | |
           | | | Indice |       | Indice |       | Indice |       | Indice | | |
clave x ...|.|>| Clave  |       | Clave  |       | Clave  |       | Clave  |<|.|... clave y
           | | |   A    |       |   B    |       |   C    |       |   D    | | |
           | | |        |       |        |       |        |       |        | | |
           | | *--------*       *--------*       *--------*       *--------* | |
           | |      .                                                 .      | |
           | *---------------------------------------------------------------* |
           |        .                                                 .        |
           |        .                                                 .        |
           |        ....................   Datos                      .........|...
           |                           .                                       |  .
           | *-------------------------V-------------------------------------* |  .
           | | *--------**--------**--------* *--------**--------**--------* | |  .
           | | |Registro||Registro||Registro| |Registro||Registro||Registro| | |  .
           | | *--------**--------**--------* *--------**--------**--------* | |  .
           | | *--------**--------**--------* *--------**--------**--------* | |  .
           | | |Registro||Registro||Registro| |Registro||Registro||Registro| | |  .
           | | *--------**--------**--------* *--------**--------**--------* | |  .
           | | *--------**--------**--------* *--------**--------**--------* | |  .
           | | |Registro||Registro||Registro| |Registro||Registro||Registro| | |  .
           | | *--------**--------**--------* *--------**--------**--------* | |  .
           | | *--------**--------**--------* *--------**--------**--------* | |  .
           | | |Registro||Registro||Registro| |Registro||Registro||Registro|<|.|...
           | | *--------**--------**--------* *--------**--------**--------* | |
           . .                                                               . .
           . .                                                               . .
           . .                                                               . .
           . .                                                               . .
           . .                                                               . .
           . .                                                               . .
           . .                                                               . .
           . .                                                               . .
           . .                                                               . .
           | | *--------**--------**--------* *--------**--------**--------* | |
           | | |Registro||Registro||Registro| |Registro||Registro||Registro| | |
           | | *--------**--------**--------* *--------**--------**--------* | |
           | | *--------**--------**--------* *--------**--------**--------* | |
           | | |Registro||Registro||Registro| |Registro||Registro||Registro| | |
           | | *--------**--------**--------* *--------**--------**--------* | |
           | *---------------------------------------------------------------* |
           *-------------------------------------------------------------------*

Los Indices son una colección de pares de la forma ( Valor de la Clave, Direccion ).
Ejemplo :
Si los registros son los siguientes :
A ( Empleado_Numero = 800 )
B ( Empleado_Numero = 510 )
C ( Empleado_Numero = 950 )
D ( Empleado_Numero = 750 )
E ( Empelado_Numero = 620 )
y están almacenados en las direcciones a, b, c, d, e respectivamente, entonces para la Clave Empleado_Numero habra las siguientes entradas en el Indice :
( 800, a )
( 510, b )
( 950, c )
( 750, d )
( 620, e )

Los Tipos de Indices ( Index Types) son :

Densos ( Contienen una entrada para cada registro )

No Densos ( Contienen una entrada para solamente algunos registros )

Organización de los Indices

Existen las siguientes organizaciones de indices :

Indexacion Cilindro-Superficie ( Cylinder-Surface Indexing )

Indexacion Mutilada ( Hashed Indexing )

Indexacion Arbolada ( Tree Indexing )

Indexacion Trie ( Trie Indexing )

Indexación Cilindro-Superficie ( Cylinder-Surface Indexing )

La Indexacion Cilindro-Superficie ( Cylinder-Surface Indexing ) es solamente util para la clave primaria de un archivo con organizacion secuencial ordenada. Esta forma de indexacion asume la interpretacion secuencial de la memoria del disco magnetico. Estamos en presencia de un indice no denso.
El indice tiene :

Un indice de cilindros

Varios indices de superficie

Ejemplo :
Si el Archivo tiene c cilindros ( 1 a c ) el indice de cilindro tiene c entradas.
Cada entrada tiene el valor mas alto de la clave primaria en el cilindro.
Si el Archivo tiene s superficies ( 1 a s ) los indices de superficies tienen s entradas.
Cada entrada tiene el valor mas alto de la clave primaria en la superficie.
La busqueda de una clave x se ejecuta de la siguiente manera :

Se busca en el indice de cilindros y se determina en que cilindro puede estar x
Se busca en el indice de superficie del cilindro determinado en el punto anterior
Se lee la pista determinada en el punto anterior
Se recupera el registro con la clave x


           *------------*-----*                       *-------------*-----*
           |            |  1  |--------------+        |             |  1  |
           |            |-----*              |        |             |-----*
           |   Indice   |  2  |-----------+  |        |   Indice    |  2  |
Clave x    |            |-----*           |  |        |             |-----*
---------->|     de     |     .           |  +------->|     de      |     .
           |            |     .           |           |             |     .
           | Cilindros  |     .           |           | Superficies |     .
           |            |-----*           |           |             |-----*
           |            |  c  |----+      |           |             |  s  |
           *------------*-----*    |      |           *-------------*-----*
                                   |      |
                                   |      |           *-------------*-----*
                                   |      |           |             |  1  |
                                   |      |           |             |-----* Clave x
                                   |      |           |   Indice    |  2  |-------------> Leo la pista --------> Recupero el registro
                                   |      | Clave x   |             |-----*                                          de Clave x
                                   |      +---------->|     de      |     .
                                   |                  |             |     .
                                   |                  | Superficies |     .
                                   |                  |             |-----*
                                   |                  |             |  s  |
                                   |                  *-------------*-----*
                                   |
                                   |
                                   |
                                   |
                                   |
                                   |
                                   |
                                   |                  *-------------*-----*
                                   |                  |             |  1  |
                                   |                  |             |-----*
                                   |                  |   Indice    |  2  |
                                   |                  |             |-----*
                                   +----------------->|     de      |     .
                                                      |             |     .
                                                      | Superficies |     .
                                                      |             |-----*
                                                      |             |  s  |
                                                      *-------------*-----*

Indexación Hashed ( Hashed Indexing )

La Indexacion Hashed ( Hashed Indexing ) es lo visto al analizar la Hash Tables.

Indexación Arbol ( Tree Indexing )

La Indexacion Arbol ( Tree Indexing ) es lo visto al analizar los Arboles de Busqueda.

Indexación Trie ( Trie Indexing )

La Indexacion Trie ( Trie Indexing ) es lo visto al analizar la Arboles Trie.