ORGANIZACIÓN DE ARCHIVOSOrganización de Archivos 
Secuenciales y Relativos
Escrito por Rodrigo López
 
La Organización de un Archivo es la colección de registros lógicos en el archivo 
y la percepción que tiene el usuario programador de aplicaciones acerca de la 
disposición lógica de los registros almacenados en el archivo; una organización 
de archivo soporta algún(os) método de acceso mediante el cual estos registros 
pueden ser accedidos. 
A continuación se presentan algunas organizaciones de archivo.
 
  Organización Secuencial
El término organización secuencial implica que lógicamente los registros del 
archivo están almacenados consecutivamente; esto es, en forma adyacente, en el 
orden en que el usuario final los percibe. En particular se puede hacer una 
distinción entre archivos secuenciales ordenados y archivos secuenciales 
desordenados. Una organización de archivo secuencial ordenada almacena los 
registros lógicos secuencialmente pero en orden creciente (o decreciente) de 
acuerdo con los valores de alguna de sus claves, mientras que la organización de 
archivo secuencial no ordenada almacena los registros lógicos consecutivamente 
pero sin un orden específico.
La organización secuencial es la organización de archivo más común. Los 
registros son almacenados uno tras otro en orden de llegada. Para acceder un 
registro determinado se deben leer todos los registros que están almacenados 
antes de éste. Cuando el orden secuencial coincide con el orden físico se dice 
que existe un orden serial (en una cinta magnética siempre se cumple esta 
característica). 
Operaciones:
  La operación de inserción de un registro en un archivo organizado 
  secuencialmente puede ser realizada de dos maneras:
  Crear un nuevo archivo. Es costoso (en términos de número de transferencias de 
  datos entre memoria principal y secundaria), pero puede la única forma posible 
  en caso de que el archivo se encuentre organizado secuencialmente ordenado.
  Agregarlo al final. De bajo costo. Puede NO ser útil en el caso de que el 
  archivo encuentre organizado secuencialmente ordenado.
  La operación de eliminación puede ser realizada de dos maneras:
  Creando un nuevo archivo secuencial que no contenga el registro eliminado. Es 
  de alto costo.
  Marcar el registro en cuestión, es decir, realizar una eliminación lógica. 
  Normalmente esta operación no es posible de realizar en dispositivos de acceso 
  secuencial como las cintas magnéticas.
 
A nivel físico, los bloques están almacenados "consecutivamente" ya sea:
  Almacenados de tal forma que ellos están físicamente adyacentes y por lo tanto 
  residen en la misma sola extensión (archivo secuencial físico); o
  Almacenados de tal forma que pertenezcan a grupos (clusters) diferentes y, por 
  lo tanto, pertenezcan a más de una extensión, con su adyacencia lógica 
  mantenida vía punteros de disco. (archivo secuencial enlazado físico)
Debido a que las operaciones que modifican el estado del archivo secuencial 
(sobre todo eliminación y modificación ) son costosas (en términos de tiempo de 
respuesta), la mayoría de las veces se postergan hasta que se hayan acumulado un 
cierto número de este tipo de operaciones, en un archivo especial llamado 
archivo de transacciones (el cuál en sí mismo puede ser un archivo organizado 
secuencialmente). Llegado un momento, todas las operaciones pendientes 
(almacenadas en el archivo de transacciones) son aplicadas "juntas", generando 
un nuevo archivo.
Por todo lo anterior, se tiene que los archivos de organización secuencial se 
desempeñan bien para operaciones Batch (recuperar muchos registros) y 
Recuperar_Todos (recuperar todos los registros), y normalmente requieren de un 
espacio de almacenamiento bastante pequeño (por ejemplo, no necesitan de 
estructuras auxiliares como ocurre en los archivos ordenados de forma secuencial 
indexada).
Como desventaja se tiene que no existe una manera rápida de acceder a un 
registro lógico específico (en contraste, por ejemplo, con lo que sucede en los 
archivos relativos y en los archivos indexados, en dónde es posible acceder a un 
registro determinado en pocos accesos).
Un archivo almacenado en una cinta magnética está siempre organizado 
secuencialmente. 
En un disco duro, la organización secuencial puede ser lograda mediante una capa 
de "abstracción" de software; sin embargo, un archivo organizado en forma 
secuencial desaprovecha las características de acceso directo que proporciona el 
disco duro.
  
  Organización de Archivos Relativos
En un archivo relativo existe una relación predecible entre la clave utilizada 
para identificar al registro en particular y la localización del registro dentro 
del archivo. El ordenamiento lógico de los registros no necesita tener ninguna 
relación con su secuencia física. Los registros no necesariamente aparecen 
físicamente ordenados de acuerdo con el valor de sus llaves.
Cuando un archivo relativo se establece debe definirse una relación que será 
utilizada para obtener una dirección física a través de un valor de clave. Esta 
relación es llamada función de mapeo (también conocida como transformación KTA, 
Key-To-Address).
R(Valor de Clave) -> Dirección
Cuando se debe guardar un registro en un archivo relativo, la función de mapeo R 
se utiliza para traducir el valor de clave del registro en una dirección que 
indica dónde deberá almacenarse el registro.
Cuando se desea recuperar un registro, el valor de clave de éste es entregado a 
la función R la cual traduce el valor de clave a una dirección en la cual está 
el registro.
En general, los archivos organizados en forma relativa permiten acceder a 
registros en un número de accesos igual o cercano a uno.
Los archivos relativos deben ser almacenados en medios de almacenamiento de 
acceso directo (como los discos duros).
 
Técnicas de Direccionamiento
 
A continuación se presentan dos técnicas fundamentales utilizadas por las 
funciones de mapeo R:
  Mapeo Directo 
  Por cálculo (Transformaciones Hashing)
 
Técnicas de Mapeo Directo.
Es la técnica más simple de traducir un valor de clave en una dirección de 
registros. Estas técnicas presentan desventajas tan serias que muy rara vez son 
utilizadas. A continuación se mencionan dos técnicas de mapeo directo: el 
direccionamiento absoluto y el direccionamiento relativo.
 
Direccionamiento Absoluto
R(Valor de Clave) -> Dirección
Donde, valor de clave = dirección.
Esta función de correlación se llama direccionamiento absoluto. El valor de la 
llave suministrado por el usuario es igual a la dirección real del registro. En 
este esquema, la localidad del registro debe ser proporcionada por el usuario 
cuando se desea recuperar o almacenar un registro (por ejemplo, en el Disco IBM 
3310, se debe especificar el número de bloque físico; en algunos otros 
dispositivos sería necesario especificar [número de cilindro, número de 
superficie, numero de bloque]).
Ventajas:
    La función de mapeo R es muy simple.
    No se requiere de tiempo de procesamiento para determinar la localidad del 
    registro en el almacenamiento secundario.
Desventajas:
    Las consideraciones lógicas y físicas no son independientes; el usuario debe 
    conocer exactamente cómo están almacenados físicamente los registros.
    En general, los valores de claves proporcionadas por los usuarios para 
    identificar los registros no son apropiados para utilizarlos como 
    direcciones físicas.
    Las direcciones absolutas dependen de los dispositivos.
    Las direcciones absolutas dependen del espacio direccionable. Una 
    reorganización del archivo conlleva a cambiar los valores de la clave.
 
Direccionamiento Relativo
R(Valor de Clave) -> Dirección
Donde valor de clave = dirección relativa.
La dirección relativa puede suministrarse al programa de canal para su 
traducción en dirección absoluta.
La dirección relativa de un registro en un archivo es el número ordinal del 
registro dentro del archivo. Un archivo con espacio para N registros tiene 
registros con direcciones relativas que están en el conjunto [1,2,3,...,N-1,N]. 
El I-ésimo registro tiene la dirección relativa I.
Ventajas:
    La función de mapeo R es muy simple.
    Casi no se requiere de tiempo de procesamiento para determinar la localidad 
    del registro en el almacenamiento secundario.
    Las direcciones relativas no dependen tanto del dispositivo como las 
    direcciones absolutas.
Desventajas:
  En general, los valores de claves proporcionadas por los usuarios para 
  identificar los registros no son apropiados para utilizarlos como direcciones 
  físicas.
  Las direcciones relativas dependen del espacio direccionable. Una 
  reorganización del archivo podría implicar un cambio en los valores de la 
  clave.
 
Cálculo de Direcciones (Hashing)
La idea básica del cálculo de direcciones consiste en aplicar la función que 
traduce un conjunto relativamente grande de posible valores de llave, a un rango 
relativamente pequeño de valores de direcciones relativas. Un problema potencial 
es que tal función no pueda ser uno a uno; las direcciones calculadas pueden no 
ser todas únicas. Cuando R(k1) = R(k2), donde k1 es distinto de k2, se dice que 
se produce una colisión; en estos casos a k1 y k2 se les llama sinónimos.
Ventajas:
    Se pueden usar los valores naturales de las claves, puesto que se traducen 
    internamente a direcciones.
    La independencia lógica y física es lograda, debido a que los valores de las 
    llaves son independientes del espacio de dirección. Si el archivo relativo 
    es reorganizado, la función hash puede tener que ser cambiada, pero el valor 
    de la llave no será afacetado.
Desventajas:
    El tiempo de procesamiento requerido para la aplicación de la función hash.
    El tiempo de procesamiento y los accesos de E/S requeridos para solucionar 
    las colisiones.
 
Una buena función hash es aquella que produce relativamente pocas colisiones.
 
La eficiencia de una función hash particular depende de:
    La distribución de los valores de llave que realmente se usan.
    El número de valores de llave realmente están en uso con respecto al tamaño 
    del espacio de direcciones.
    El número de registros que pueden almacenarse en una dirección dada sin 
    causar una colisión.
    La técnica utilizada para resolver el problema de las colisiones.
 
Algunas de las funciones hash más comunes son:
    Residuo de la división
    Medio del cuadrado
    Pliegue.
 
Hashing por residuo de la división
Consiste en dividir el valor de la clave entre un número apropiado, y después 
utilizar el residuo de la división como dirección relativa para el registro. En 
este caso, la función
R(valor de clave) -> dirección
en C puede codificarse así:
int R(int valor_llave){
return valor_llave % DIV;
}
Dónde DIV es un número entero apropiado, considerando los siguientes puntos:
El rango de valores que resultan de la operación valor_llave % DIV, va desde 0 a 
DIV – 1. Luego, el valor del divisor determina el tamaño del espacio de 
dirección relativa.
El divisor debe seleccionarse de tal forma que la probabilidad de colisión sea 
minimizada. Algunas investigaciones siguieren que son buenos divisores:
  Los números primos.
  Los números no primos que no contienen números primos pequeños como factores 
  (factores primos menores que 20).
 
Hashing por medio del cuadrado
La llave es elevada al cuadrado, después se extraen algunos dígitos de la mitad 
del resultado para construir la dirección relativa. Si se desea una dirección 
relativa de n dígitos, entonces los dígitos se truncan en ambos extremos de la 
llave elevada al cuadrado, tomando los n dígitos intermedios.
Utilizando la función hashing del medio del cuadrado, el tamaño del archivo 
resultante es de 10n, donde n es el número de dígitos extraídos de los valores 
de la clave elevada al cuadrado.
Desventaja: tiende a generar muchas colisiones.
Ejemplo:
Valor de llave: 1234567890
Llave al cuadrado = 15241578997104100
Se desea obtener una dirección de 4 dígitos; se extraen los dígitos de la 
posición 7 a la 10.
Dirección relativa = 8997
 
Hashing por pliegue
En esta técnica el valor de la llave es particionado en varias partes, cada una 
de las cuales (excepto quizá la última) tiene el mismo número de dígitos que 
tiene la dirección relativa objetivo. Estas particiones son después plegadas una 
sobre otra y sumadas. El resultado, con el dígito de mayor orden truncado si es 
necesario, es la dirección relativa.
Ventaja: es fácil de calcular.
Desventaja: proporciona resultados erráticos, a menos que la longitud de la 
llave sea aproximadamente igual a la longitud de la dirección.
Ejemplo: considere el valor de clave 123456789, y suponga que la dirección 
relativa objetiva tendrá 4 dígitos. El valor de la clave es particionado en 
partes de 4 dígitos.
      123456789

Después se pliegan unos sobre otros:
      1000
      2345
      9876

La suma es igual a 13221.
El dígito de mayor orden es truncado para dar la dirección relativa 3221.
 
Métodos para Resolución de Colisiones
Considere el caso en que dos valores de llave, K1 y K2, son sinónimos con la 
función hash R y no existen otro sinónimo de K1 (por lo tanto tampoco de K2). Si 
K1 es primero almacenado en el archivo y su dirección es R(K1), entonces se dice 
que K1 es almacenado en su dirección de origen.
Existen dos métodos básicos para determinar dónde debe ser alojado K2: 1) 
Direccionamiento abierto, en el cual otra dirección distinta de la dirección de 
origen es encontrada para K2 en el mismo archivo relativo y 2) Separación de 
desborde, en el cual alguna dirección es encontrada para K2 fuera del área 
principal del archivo relativo, en un área especial de desborde.
A continuación se presentan dos técnicas de para manejar colisiones:
  Sondeo lineal, que es un técnica de direccionamiento abierto.
  Doble hashing, que puede ser aplicado como técnica de direccionamiento abierto 
  o como separación de desborde.
 
Sondeo Lineal
Consiste en una búsqueda secuencial desde la dirección de origen para encontrar 
la siguiente localidad vacía. Si se utiliza esta técnica para almacenar 
registros, también deberá usarse para recuperarlos.
Algoritmo de sondeo lineal simple:
Direc := R(key)
Direc _Origen:= Direc
Inicio_Ciclo:
SI NO Esta_Ocupado( Direc ) ENTONCES
Almacenar_Registro( Direc )
Cambiar el Indicador para que Marque Ocupado
Terminar Proceso
DE_LO_CONTRARIO
//Buscar en la siguiente dirección para ver si está desocupada
Direc := Direc + 1
SI Direc > Tamaño_Archivo ENTONCES
Direc := 1 //Para seguir desde el inicio del archivo 
FIN SI
SI Direc = Direc _Origen ENTONCES
//El Archivo está completamente lleno
Terminar Proceso
DE_LO_CONTRARIO
GOTO Inicio_Ciclo
FIN SI
FIN SI
 
La búsqueda de un registro es similar al algoritmo anterior:
Direc := R(key)
Direc _Origen:= Direc
Inicio_Ciclo:
SI NO Esta_Ocupado( Direc ) ENTONCES
//El registro no está en el archivo
Terminar Proceso
DE_LO_CONTRARIO
Leer_Registro
SI Valor_Llave_Registro_Leido = key ENTONCES
//Registro encontrado
Terminar Proceso
DE_LO_CONTRARIO
//Sondeo Lineal
Direc := Direc + 1
SI Direc > Tamaño_Archivo ENTONCES
Direc := 1 //Para seguir desde el inicio del archivo 
FIN SI
SI Direc = Direc _Origen ENTONCES
//No está el registro
Terminar Proceso
DE_LO_CONTRARIO
GOTO Inicio_Ciclo
FIN SI
FIN SI
FIN SI
 
 
Como se puede apreciar, la técnica de sondeo lineal es bastante sencilla de 
implementar. Sin embargo, los algoritmos de almacenamiento y recuperación de 
registros podrían volverse algo más complejos al considerar la operación de 
eliminación de registros.
Doble Hashing
Consiste en aplicar una segunda función hashing sobre la clave que provoca 
colisión. El espacio de dirección objetivo del segundo hash puede ser el mismo 
archivo relativo (direccionamiento abierto) o bien un archivo de desborde 
separado (separación de desborde).
Comparación de Sondeo Lineal v/s Doble Hashing
La técnica de sondeo lineal tiende a agrupar sinónimos dentro de un archivo 
relativo, al contrario de lo que sucede con el doble hashing en donde los 
sinónimos tienden a dispersarse.
El resultado es que las búsquedas de registros cuando se ha utilizado la técnica 
de sondeo lineal tienden a ser más largas. Sin embargo, en un ambiente paginado 
el hecho de que los sinónimos estén agrupados puede ser beneficioso.
Técnicas para Mejorar la Eficiencia de los Archivos Relativos
    Encadenamiento de Sinónimos: Consiste en mantener una lista ligada de 
    registros con la misma dirección de origen. Puede utilizarse con cualquier 
    técnica de solución de colisiones.
    Direccionamiento por Cubetas: Consiste en asignar bloques de espacio que 
    pueden contener múltiples instancias de registros. De esta forma, los 
    registros que son enviados a las mismas cubetas no provocan colisiones 
    problemáticas. Cuando una cubeta es desbordada, se debe encontrar una nueva 
    localización para el registro. Se pueden utilizar los mismos métodos para el 
    manejo de colisiones vistos anteriormente (direccionamiento abierto y 
    separación de desborde).
 
Lecturas Complementarias
  [Loomis 1991] "Estructuras de Datos y Organización de Archivos": Mary Loomis; 
  Prentice-Hall Hispanoamericana; 1991; Capítulos 11 al 13. 
  [Livadas 1990] "File Structures, Theory and Practice": Panos E. Livadas; 
  Prentice-Hall International; 1990. 

http://informatica.comunalia.com/modules/tutorials/tutoriales/arch_sec_rel/arch_sec_relativos.htm