Los registros están dispuestos uno a continuación de otro. Existen dos formas de este tipo: simple y encadenado.
Simple
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:
A) Consulta muy rápida en procesamiento secuencial.
B) Modificaciones del fichero:
- Si el soporte es secuencial la modificación 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).
Encadenado
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 recordemos que 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 o procesamiento 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, o sea, es un registro de punteros que apuntan al principio de la lista correspondiente a la ordenación que deseemos.
Como los registros no se almacenan secuencialmente, y sin embargo si se accede secuencialmente, este acceso es más lento porque la cabeza tiene que ir dando saltos.
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 funcionesprincipales: la construcción de índices y de ficheros.
El tipo de árbol que se emplea generalmente es el binario, en su variante de árbol binario de búsqueda, se usa porque permite que se procesen los registros de forma directa y porque es sencillo hacer un recorrido secuencial en ellos, al procesar el árbol en in-orden.
Los árboles binarios no de búsqueda sirven para desarrollar cualquier tipo de estructura jerárquica siguiendo la técnica del enlace al sucesor - enlace al gemelo. En esta técnica el hijo izquierdo de cada nodo es un sucesor, y el hijo derecho un gemelo. Veamos como se aplicaría esta técnica al siguiente árbol:
En los árboles la consulta y la inserción son sencillas. Las supresiones se pueden hacer o bien por marca (no se precisa reorganizar), o bien supresiones reales que tienen la ventaja de que no dejan huecos en la estructura. Las organizaciones encadenadas se prestan bien a compartir espacio en el soporte con otras organizaciones encadenadas que haya. La estructura de árbol tiene muy pocas desventajas.
Sin embargo uno de los principales problemas de las demás estructuras encadenadas, es que si se hacen muchas supresiones, quedan excesivos huecos, con lo que el fichero se desaprovecha excesivamente. Para evitar esto existen dos técnicas: la recuperación de huecos y la gestión dinámica del espacio libre.
La recuperación de huecos consiste en lo siguiente: al crear el fichero se reserva espacio y se encadenan los huecos por medio de punteros (por tanto los registros deben ser de longitud fija). Siempre se tiene un puntero señalando a la primera posición libre del fichero (que es el hueco al que se acude a la hora de realizar una nueva inserción). Si fuese necesario hacer una supresión, el puntero de inserción pasaría a apuntar al registro borrado, y dicho registro apuntaría a donde estaba apuntando el puntero de inserción antes de realizar el borrado. Veamos un ejemplo:
En un principio tenemos el fichero distribuido de esta manera donde cada cuadro representa un registro (los sombreados son registros ocupados). El puntero marcado es el de inserción.
Si borramos uno de los registros ocupados, por ejemplo el de la segunda fila y la segunda columna, el fichero quedaría como sigue:
Como vemos el puntero de inserción apunta ahora al registro que acaba de ser borrado, por tanto cuando hagamos la próxima inserción esta se realizará en dicho registro.
La gestión dinámica del espacio libre permite:
- Tener registros de longitud variable.
- Que los nuevos registros se inserten lo más cerca posible de los anteriores.
- Reorganizar los huecos para que queden juntos, esto quiere decir que al hacer supresiones habrá movimiento de registros a nivel físico.
Este método se podría representar gráficamente de la siguiente forma:
R1 R2 R3 R4 Hueco Hueco
Si borramos R2 quedaría:
R1 R3 R4 Hueco Hueco Hueco
