1.-Organización secuencial:
Los
registros están dispuestos uno a
continuación de otro. Existen dos formas de este tipo: simple y encadenado.
La
disposición de los ficheros (uno detrás de otro) se traduce en
un almacenamiento sin huecos entre ellos.
Nota: un
registro físico es el bloque fijo que se transfiere del disco a la memoria principal,
y por tanto puede contener más de un registro lógico.
A
continuación veremos las principales características de
los ficheros lineales simples:
B) Modificaciones
del fichero:
Si el soporte es secuencial la modificación que
obliga a hacer una copia del fichero. Al realizar una inserción hay que desplazar hacia atrás todos los
que siguen. Al efectuar un borrado hay que
desplazar hacia delante todos los registros que seguían al registro borrado, y
por último para modificar un
registro también hay que hacer una copia ya que para modificarlo hay que leerlo entero,
con lo cual, una vez leído, la cabeza ya ha pasado por él y habría que
volverla hacia atrás (cosa que no podemos hacer).
Si el soporte es directo es posible hacer modificaciones sencillas, pero la inserción y el borrado requieren
una copia del fichero. Para hacer dicha copia se emplea el Algoritmo de la Línea de Balance que consiste en tener un fichero de movimientos que
almacena los registros que van a sufrir modificación. Este fichero y aquel
del que proceden los datos deben tener la misma clave, se procesa el
primer registro de ambos y se graba en otro fichero la modificación (si
procede) de ese registro, o bien si en el fichero de movimientos se indica el
borrado no se copia.
C) Proceso
lento para consultas puntuales
D)
Aprovechan mucho el espacio de almacenamiento (sólo se precisa el justo
para los datos)
E)
Posibilidad de usar cualquier tipo de soporte.
F) Problema para procesar un fichero por más de una clave (campo de
registro), ya que si un registro está ordenado en función de una
clave no puede estarlo por otra. Las soluciones a este problema son: o bien se
tienen dos ficheros iguales o más (tantos como
clasificaciones diferentes haya) cada uno ordenado con respecto a una clave, o
bien se clasifica el fichero cada vez que se quiera acceder (lo cual es muy
lento).
2.-Organización relativa directa:
Un fichero de
organización directa o aleatoria es aquel al que se accede
directamente a un registro por la posición
que ocupa. En este tipo de
organización, la
clave juega un papel fundamental, ya que se va a utilizar para obtener
la posición
relativa de cada registro dentro del fichero.
En este tipo de organización no se puede almacenar un
registro cuya clave este por encima de los
limites máximos
del fichero, ya que cada dirección sólo puede ser ocupada por
un registro.
Por ello, para que
un archivo pueda tener organización directa necesita:
-
Almacenarse en un soporte direccionable.
-
La existencia de un campo clave.
-
Establecer una correspondencia entre los valores de la
clave y las direcciones disponibles en el soporte.
Las ventajas de este
tipo de organización de ficheros son:
•
Acceso directo a los registros.
•
Permite realizar operaciones de
escritura y lectura simultáneamente, ya
que primero
se localiza el registro y luego se realiza la operación deseada: inserción,
eliminación, consulta, modificación, etc
Los inconvenientes de este
tipo de organización de ficheros son:
•
Al realizar un acceso secuencial, en
una consulta sobre todos los registros del fichero hay que
recorrer todas las direcciones aunque estén vacías.
•
Deja gran cantidad de posiciones
libres de memoria dentro del fichero.
•
Se producen colisiones, ya que puede
existir más de un registro con la
misma clave.
La transformación
de la clave de un registro en la dirección en la que debe encontrarse en
el fichero, se realiza mediante lo que se denomina algoritmo o función de conversión (hash).
Siendo:
- k la clave.
-
f la función
que se aplica a la clave.
-
p la posición lógica en el soporte.
3.-Organización aleatoria o indirecta:
Son ficheros con organización relativa y clave alfanumérica, que hay que transformar
para
conseguir un valor numérico entero que facilite la
correspondencia directa entre la clave y
la dirección de memoria. En este caso las
claves no coinciden con la dirección física, que son las
posiciones de cada registro.
Para transformar
dicha clave alfanumérica y obtener la dirección física
usamos las siguientes fórmulas:
f(clave) = clave /
2 (división entera)
Otras funciones
hash, no producen
colisiones, pero en cambio provocan que muchas direcciones físicas
no sean utilizadas, con lo que se desaprovecha el
espacio de almacenamiento.
Ventajas:
-Acceso inmediato
a los registros mediante su clave.
-No es necesario
ordenar el fichero.
-Se pueden
realizar operaciones de escritura y lectura a la vez.
-Son muy rápidos
en el tratamiento individual de registros.
-Se pueden
realizar accesos secuenciales.
Inconvenientes:
-El fichero
contiene gran cantidad de huecos o espacios.
-El algoritmo para
la conversión de las claves y el algoritmo para el
almacenamiento y tratamiento de sinónimos han de ser creados de modo
que dejen el menor numero de huecos libres y se genere el menor numero de sinónimos.
Al calcular la
dirección de memoria puede ser que una clave diferente nos de cómo
resultado la
misma dirección de memoria, ese registro iría
a la zona de
overflow.
Para el borrado, borramos el registro y queda el hueco libre
para poder poner un nuevo registro.
4.-Organización secuencial encadenada: Punteros
Los
ficheros lineales encadenados mejoran a los simples. Los registros se procesan en el orden lógico (uno detrás de otro), pero este no tiene porque coincidir con el orden físico (los
registros se enlazan por punteros). Es imprescindible un soporte de acceso directo.
Los registros deben contener un campo extra para
almacenar el puntero (que puede dar la dirección exacta del siguiente
registro o bien ser una dirección relativa
respecto del comienzo del fichero). Se crea para evitar las copias implicadas
en el proceso de inserción y borrado; estos
procesos sólo conllevan un reajuste de punteros.
Los
punteros son entre registros físicos, y en un registro físico cabe más de un
registro lógico.
Este tipo
de organización se usa mucho con diferentes estructuras:
A) Listas Simples. Son de acceso secuencial y suelen ser pilas o colas. Son las más sencillas y responden a
la descripción general que se ha hecho para los ficheros secuenciales encadenados.
B) Listas Múltiples. Son también de acceso secuencial, es decir,
que para llegar a un registro lógico, hay que pasar
previamente por todos los anteriores a él. En este tipo de listas cada registro lleva más de un puntero.
Permiten tener clasificados los registros
por más de una
clave, teniendo varios campos de puntero. Suele haber un registro índice que es
cabeza de todas las listas. Regularmente se deben reorganizar los datos para
acelerar el acceso a través de la clave más habitual.
C) Anillos. Se emplean como
estructura de muchos de los modelos de bases de datos.
D) Árboles. Tienen dos funciones principales: la construcción de índices y de ficheros.
5.-Organización secuencial indexada:
Este método usa un
fichero de datos
secuencial y un índice
secuencial.
Divide el espacio del soporte en tres zonas: área de Datos, área de índices y área de Desborde, las cuales se subdividen en otras
según la estructura de los soportes. Los datos se organizan en pistas (que es la unidad de transferencia con la memoria principal) y éstas en cilindros lógicos.
La pista 0 de todos
los cilindros se reserva para crear los llamados índices de pistas y alguna
más para los excedentes del cilindro (al final).
Cuando se
llene una pista se pasa a la siguiente pista libre de ese mismo cilindro (se va rellenando cilindro a cilindro). Al rellenar una pista
se crea en el índice de pista una entrada con la clave de mayor
orden de esa pista y un puntero a esa pista.
Al llenar un cilindro, en el área de índices se crea una entrada en el índice de cilindros con la
clave de mayor orden y un puntero al cilindro.
Puede
existir un tercer índice, el índice maestro, muy pequeño que
apunta al índice del cilindro.
La mejora
que obtenemos con este método es que al poder
llevar una pista entera a memoria principal se trabaja más rápido; si al hacer una
inserción excedo el tamaño de la pista el/los registro/s excedente/s va/n a las pistas del área de excedentes del
cilindro.
6.-Organización secuencial indexada-encadenada:
Se caracteriza principalmente por la utilización de punteros e índices, de
forma simultánea, lo que implica un considerable aumento del espacio ocupado en memoria para
la implementación de índices y campos puntero, pero se consigue respecto a la organización indexada,
mejorar los tiempos de búsqueda en la zona de overfloat y
mantener la organización lógica de
los registros en el fichero.
· Insertar.
Para insertar un nuevo registro es necesario encontrar el que le sigue en la zona
de registros. Se escribe el nuevo registro en la zona de desbordamientos y se reescribe el siguiente en
orden lógico para
incluir el puntero al registro recién grabado.
· Eliminación.
La eliminación de los registros debe realizarse mediante marcas. Se
generan huecos que
realmente son posiciones de memoria ocupadas
por
registros marcados pero que NO han sido
eliminados físicamente del fichero. La única posibilidad de
eliminar estos huecos, es en futuras operaciones en las cuales necesitemos reorganizar el fichero.
· Consulta.
Es similar a la realizada a la indexada, con la
particularidad de que dos punteros
distintos de un valor predeterminado va ha indicar que hay un acceso
a la zona de overfloat.
En esta organización
cuando el numero de registros borrados es grande, o las cadenas de
desbordamiento son largas su utilización deja de ser eficiente, siendo
necesario
reorganizar el archivo.
