5. Acceso y Organización de Archivos

5.1 Conceptos generales
 

5.2  Archivos de Registros, métodos de almacenamiento manteniendo la identidad de los campos


En términos de programación cuando hablamos de un record en memoria nos estamos refiriendo a un objeto, el cual tiene sus miembros o atributos; sin embargo cuando se almacena en disco dicho objeto entonces hablamos simplemente de un registro.

Nota: cuando el objeto se guarda completamente, incluyendo sus métodos estamos hablando de "Persistencia de Objetos" (Object Serialization)


Problema:
Deseamos almacenar la siguiente información que tenemos en memoria en disco
 

Mary Ames Alan Mason
123 Maple 90 Eastgate
Stillwater OK 74075 Ada OK 74820

Si consideramos el siguiente método para almacenar dichos datos,

ostream & operator << (ostream & outFile, Person & p)
{   //insert (write) fields into stream
      outputFile << p.lastName
           << p.FirstName
           << p.Address
           << p.City
           << p.State
           << p.ZipCode;
        return outputFile;
}

los guardaremos en un archivo de manera consecutiva, tal como se fue especificando, pero ahora tenemos un gran problema. La información no se puede separar para distinguir los distintos campos que componen cada registro.
 

AmesMary123 MapleStillwaterOK74075MasonAlan90 EastgateAdaOK74820

Solución:

Existen distintas maneras de agregar estructuras de datos a archivos y mantener la identidad de los campos:
 

Forzar a los campos  a tener una longitud fija

Los campos (nombre, dirección, estado) de nuestro ejemplo anterior tenían longitudes variables.
Pero nosotros podemos pensar en establecer una medida fija para cada uno de los campos en el caso del ejemplo de Person cada campo tiene una longitud y el tamaño total de un registro siempre sera de 67 bytes (11+11+16+16+3+10)
 

class Person { public:
               char last[11];
               char first [11];
               char address [16];
               char city[16];
               char state[3];
               char zip[10];
  };

De manera que el archivo quedaría de la siguiente manera (recordar cubrir los espacios vacíos):
 

Ames Mary 123 Maple Stillwater OK 74075
Mason Alan 90 Eastgate Ada OK 74820

Para recuperar la información se puede hacer matemáticamente leyendo el número de bytes/chars correspondientes a cada campo

Desventajas


Ventaja


Comenzar cada campo con un indicador de la longitud del campo

Se coloca antes de cada campo su longitud, generalmente si los campos no son muy largos esta medida ocupará un solo byte (256 bytes de longitud)
 

04Ames04Mary09123 Maple10Stillwater02OK0574075
05Mason04Alan1190 Eastgate03Ada02OK0574820

 


Colocar un delimitador al final de cada campo para separarlo del siguiente

Escribir un caracter especial entre cada campo de manera que se pueda preservar la identidad
La decisión de cual caracter "especial"  utilizar es muy importante ya que no debe utilizarse en ninguno de los campos.
En algunos casos los espacios en blanco, el salto de línea o el tabulador pueden ser una buena opción.
 

Ames|Mary|123 Maple|Stillwater|OK|74075
Mason|Alan|90 Eastgate|Ada|OK|74820

 


Usar una pareja "keyword=value" para identificar cada campo y su contenido
 


Desventaja:

last=Ames| first=Mary|address=123 Maple|city=Stillwater|state=OK|zip=74075

 

5.3  Métodos de Almacenamiento manteniendo la identidad de los Registros

Lo anterior es muy útil e interesante pero pierde de vista el concepto original que teníamos de "registro", en el ejemplo cada registro esta compuesto por 6 campos.

Un registro es un conjunto de campos que permanecen juntos cuando el archivo es visto en términos de organización de alto nivel.

En términos de programación lo que se busca es poder leer "registros" de archivos como un todo  (buffer en memoria) para poder separar cada uno de sus campos.

Métodos para organizar registros en archivos
 

Requerir que los registros tengan una longitud fija (bytes)
Un archivo de registros de longitud fija es aquel en el cual  todos los registros contienen el mismo número de bytes

La manera de reconocer a los registros es muy similar a la forma que se utiliza para campos, aritméticamente
 

Ames Mary 123 Maple Stillwater OK74075
Mason Alan 90 Eastgate Ada OK74820

Nota: este espacio que no es utilizado pero se debe preservar para mantener la longitud de los campos, a esto se le conoce como "Fragmentación Interna"

Es necesario mencionar que un registro de longitud fija puede tener campos de longitud variable
Por otro lado es importante resaltar que se puede tener un número variable de campos, siempre y cuando la suma de su longitud (registro) sea la misma
 

Ames|Mary|123 Maple|Stillwater|OK|74075    <--------------------Unused space---------------------------->
Mason|Alan|90 Eastgate|Ada|OK|74820     <----------------------Unused space----------------------------->

 


 

Requerir que los registros tengan un número fijo de campos

De manera diferente al método anterior, también se puede tener un número fijo de campos por registros
Cuando leemos sabremos que después de leer seis campos empezaremos un nuevo registro
Lo anterior se realiza a través de la función "modulo"  (%) , cual éste sea 0 hablaremos de un registro nuevo
 

Ames|Mary|123 Maple|Stillwater|OK|74075|Mason|Alan|90 Eastgate|Ada|OK|74820

 

Comenzar cada registro con un indicador de la longitud
(suma de todos los bytes de cada campo en el registro + separadores)

Esto es de gran utilidad cuando hablamos de registros de longitud variable

40Ames|Mary|123 Maple|Stillwater|OK|74075|36Mason|Alan|90 Eastgate|Ada|OK|74820

 

Utilizar un segundo archivo para mantener una bitácora del byte de inicio donde comienza cada registro

El uso de un índice nos sirve para conocer el desplazamiento (offset) de cada registro en el archivo original

Ames|Mary|123 Maple|Stillwater|OK|74075|Mason|Alan|90 Eastgate|Ada|OK|74820
00                                                                       40

 


Colocar un delimitador al final de cada registro para separarlo del siguiente

Al igual que con los campos el caracter que se escoja para separar los registros debe ser un caracter especial que no se utilice dentro de la información

Ames|Mary|123 Maple|Stillwater|OK|74075|#Mason|Alan|90 Eastgate|Ada|OK|74820

 

5.4  Acceso Secuencial y Acceso Directo

Existen dos maneras de accesar  y buscar registros de una archivo:
Secuencial

Existe una técnica que permite aumentar la velocidad de estos accesos llamada "Blocking"
Se basa en leer bloques de registros en lugar de leer uno por uno
El leer un bloque es más lento porque se traen en cada viaje al disco más datos, pero nuevamente la separación se hace en memoria donde la velocidad es mucho mayor y ahí se gana tiempo.
Aunque el rendimiento mejora considerablemente en realidad no es algo considerable ya que el número de las comparaciones para buscar el patrón o valor que se requiere sigue siendo el mismo.

Directo

5.5 Reutilizando el espacio en Archivos

Hasta el momento hemos hablado de organización de archivos, de agregar datos y poder distinguir los distintos campos y registros que componen la información.

Qué sucede si eliminamos un registro ??

De manera que tenemos 3 operaciones que modifican la organización de nuestro archivo:


Si el archivo que se pretende utilizar sólo se utiliza para guardar información (agregar) entonces no hay mayor complejidad en su manipulación; se vuelve más interesante cuando hablamos de actualización y eliminación tanto en archivos de registros de tamaño fijo, como aquellos con registros de tamaño variable.
Algo importante que debemos recordar es que se puede ver a la actualización como un "borrar y agregar" así que nos concentraremos primeramente en la eliminación de registros.


5.5.1 Eliminación de Registros y Compactación de Espacio

Mencionábamos anteriormente que una solución para el borrado de registros consiste en recorrer todos los demás registros para evitar que queden espacios. A este procedimiento se le conoce como "Compactación de espacio".
Aunque su desventaja es el tiempo requerido para compactar el archivo este esquema llega a ser el más adecuado para archivos no muy grandes.

Por otro lado también decíamos que otra estrategia del borrado consiste en mantener el hueco de aquel registro que hemos eliminado.
Para fines prácticos lo que se hace es colocarle una marca al registro para identificarlo como "eliminado"; esta marca puede estar en algún campo del registro o designar algún campo en específico para este fin.
 

Ames|Mary|123 Maple|Stillwater|OK|74075    <--------------------Unused space---------------------------->
*|son|Alan|90 Eastgate|Ada|OK|74820     <--------------------Unused space----------------------------->
Brown|Martha|625 Kimbark|Des Moines|IA|50311 <--------------------Unused space---------------------->

Nota: una de las ventajas de este esquema es que se pueden recuperar los registros eliminados (ej, utilizando un campo especial para indicar si el registro está activo o no)

Ya que podemos identificar aquellos registros que se han eliminado ahora la pregunta es:
Cómo se reutiliza el espacio ??
 


5.5.2 Reclamación de espacio

Antecedente:
Existen aplicaciones donde la reutilización de espacio es crítica, y se debe de hacer lo antes posible.

Recordar los dos tipos de archivos: con registros de longitud fija y los de longitud variable
Los primeros son más sencillos ya que podemos aprovechar el espacio agregando simplemente otro registro en el hueco.

Para poder reclamar el espacio disponible se necesita:


La tarea de saber si existen huecos y dónde se encuentran no es tarea fácil
La primer idea que se nos viene a la mente es usar una "lista ligada" (linked list)donde colocamos los números de los registros que se van eliminando.
Esta idea es bastante buena, pero una mejoría es ver a la lista como una "pila" (stack) donde vamos colocando "arriba" aquellos registros que se van eliminando, esto facilita el manejo de la lista de espacio disponible.
 
 

header --> libre4 --> libre3 --> libre2 --> libre1--> null

Stack con las referencias de los registros disponibles










Una limitante de  nuestro programa que manipula archivos es que al iniciar tendríamos que leer todo el archivo, verificar cuales son los huecos y crear la pila

Pero esto afortunadamente no es así, la pila se encuentra "inmersa" en el archivo como se muestra a continuación (registros de longitud fija):
 

Head de la pila: 5

0 1 2 3 4 5 6
Edwards Bates Wills *-1 Masters *3 Chavez

Eliminamos el registro 1
Head de la pila: 1

0 1 2 3 4 5 6
Edwards *5 Wills *-1 Masters *3 Chavez

Agregamos 3 registros nuevos
Head de la pila: -1

0 1 2 3 4 5 6
Edwards NUEVO_1 Wills NUEVO_3 Masters NUEVO_2 Chavez

Notas:
-En el ejemplo estamos usando como referencia el número del registro, pero en la práctica lo que se utiliza es el offset para desplazarnos en el archivo.
-El head se puede almacenar en otro archivo o bien en el "header" del mismo archivo (sección 5.8)

Lo anterior es un mecanismo bastante útil pero recordemos que se refiere a registros de longitud fija, donde los registros eliminados y los nuevos son del mismo tamaño; en el caso de registros de longitud variable los espacios libres y los nuevos registros pueden o no ser del mismo tamaño.

Para registros de longitud variable se necesita:

Los más fácil:

Size=47 
--> 		Size=38 
--> 		Size=72
--> 		Size=68 
--> null

Reutilizando el registro de tamaño 72
Size=47 
--> 		Size=38 
--> 		Size=68 
--> null

Lista de disponibles para registros de longitud variable

Head de la lista: 5

0 1 2 3 4 5 6
Edwards *-1, Size=68 Wills *1, Size=72 Masters *3, Size=38 Chavez

Eliminando el registro 6
Head de la lista: 6

0 1 2 3 4 5 6
Edwards *-1, Size=68 Wills *1, Size=72 Masters *3, Size=38 *5,Size=47

Insertando un registro nuevo de 50 bytes
Head de la lista: 6

0 1 2 3 4 5 6
Edwards *-1, Size=68 Wills NUEVO Masters *1, Size=38 *5,Size=47

Notas:
-En el ejemplo estamos usando como referencia el número del registro, pero en la práctica lo que se utiliza es el offset para desplazarnos en el archivo.
-El head se puede almacenar en otro archivo o bien en el "header" del mismo archivo (sección 5.8)
 

Esta solución es muy común y bastante utilizada, pero tiene una ligera mejoría:

5.6 Llaves (Keys)

Hemos mencionado como se almacena la información y como se elimina, pero es importante aclarar algunos conceptos.
 



5.7 Ordenamiento Interno y Búsqueda Binaria

Las búsquedas secuenciales son demasiado lentas ya que tienen que recorrer todo o casi todo el archivo; aún cuando se encuentre algún resultado podríamos saber de antemano que existe la posibilidad de encontrar más registros que cumplan con el criterio de búsqueda, de ahí que se deba continuar recorriendo todo el archivo.

Por otro lado las búsquedas por acceso directo son extremadamente rápidas, ya que podemos ir al "offset" deseado dentro del archivo, desafortunadamente esto requiere un método o fórmula para saber ubicar donde se encuentra un registro en el archivo.

De manera que si buscamos el registro de la persona con ID 35 sabremos que es el registro 35 del archivo y solo habría que multiplicarlo por su longitud (para el caso de registros de longitud fija) para obtener el desplazamiento que debemos hacer para leer del disco dicho registro.
Pero desafortunadamente este "método" no es muy adecuado en todos lo casos ya que no hay muchas maneras de garantizar que cada  registro tendrá una posición única.
Ej. Si queremos hacer búquedas de registros que no tienen números y solo texto (nombre, dirección, ciudad), la manera de relacionarlos con el lugar que ocupan en disco puede volverse demasiado complicado, aunque sigue siendo una opción.
 

Por otro lado cuando se habla de búsquedas en memoria primaria, donde los accesos son mucho más rapidos, se han desarrollado algoritmos que garantizan el encontrar registros ágilmente. Tal es el caso de la Búsqueda Binaria cuyo tiempo de búsqueda es de O(log2 n).

El algoritmo de Búsqueda Binaria se basa en la metodología "divide y vencerás", de manera que dado un arreglo de registros "ordenados" podemos buscar rápidamente alguno partiendo el arreglo a la mitad y viendo en que mitad podría estar dicho registro, y a su vez esa mitad es dividida en 2 y así sucesivamente hasta encontrar el registro.

Para el  caso de un archivo este algoritmo sería de gran utilidad:
Si por ejemplo tenemos un archivo de 2000 registros y quisiéramos hacer una búsqueda secuencial, ésta nos tomaría  en promedio:


A simple vista luce mucho más atractiva la búsqueda binaria, pero hay un "precio" que pagar,  el tener que ordenar el archivo.
Nota: recordemos que no es lo mismo ordenar un arreglo en memoria , que un conjunto de registros en disco, lo segundo es considerablemente más lento.

 

5.7.1 Ordenamiento de un archivo en memoria.

Como mencionábamos el ordenar un archivo es muy lento ya que se requerirían muchas "pasadas" por los mismos registros varias veces para poder hacer el ordenamiento; sin olvidar que tenemos: posicionar, leer, posicionar, escribir  y esto de repite muchas veces.

Una solución es lo que se conoce como "internal sorting" u "ordenamiento interno", el cual consiste en leer todo el archivo en memoria, secuencialmente, ordenarlo en la memoria primaria y entonces volver a bajarlo a disco. Esto teóricamente es lo ideal ya que el tiempo que toma hacerlo es demasiado corto, pero desafortunadamente para nuestro fin (búsqueda binaria) tiene sus inconvenientes:

a ) La Búsqueda Binaria requiere más de 1 o 2 accesos para encontrar en el archivo


b ) Mantener el archivo ordenado es demasiado caro

Algunas soluciones:
En aplicaciones donde se puede acumular la nueva información esta se guarda en un archivo separado y luego a través de algun ordenamiento tipo "merge sort" se actualizan los datos.

Las soluciones deben cumplir los siguientes criterios:


c ) El Ordenamiento Interno sólo funciona para archivos pequeños
 


 

5.7.2 Keysorting

Una solución para el ordenamiento interno es algo muy simple, el lugar de mantener todo el registro en memoria lo que almacenamos es la "llave"  y su posición en el archivo.
 
 

Arreglo 
           Key                          Posición
Itaca
1
Kellog
2
Harris
3
   
Bell
k

Archivo
   Posición                         Registro
1
Itaca | 56 | Chicago
2
Kellog | 77 | New York
3
Harris | 99 | California
   
k
Bell |  32 | Denver

De manera que el procedimiento sería el siguiente

1) Leer cada registro secuencialmente y mantener en un arreglo en memoria las llaves de dichos registros, asi como su posición dentro del archivo
2) Ordenar el arreglo (obviamente por llave)
3) Recorrer el arreglo:
    3.1)  Para cada registro del arreglo se lee del disco el registro asociado (ya que de antemano sabemos su posición)
    3.2) En otro archivo por separado se van guardando los registros leídos
4) Al final eliminamos el archivo original y nos quedamos con el que ya está ordenado.
 
 

Arreglo 
           Key                          Posición
Bell
k
Harris
3
Itaca
1
   
Kellog
2

Archivo
   Posición                         Registro
1
Itaca | 56 | Chicago
2
Kellog | 77 | New York
3
Harris | 99 | California
   
k
Bell |  32 | Denver

Ordenar el arreglo


Arreglo 
           Key                          Posición
Bell
k
Harris
3
Itaca
1
   
Kellog
2

Archivo
   Posición                         Registro
1
Bell | 32 | Denver
2
Harris | 99 | California
3
Itaca | 56 | Chicago
   
k
Kellog | 77 | New York

Reordenar el archivo
Limitaciones del Keysorting


La solución:
Para qué volver a escribir todos los registros ??
Mejor únicamente escribir el "arreglo" que ya se tiene en memoria a disco
En dicho archivo índice (index file) si podemos realizar las búsquedas binarias como se pretendía.
 
 

Archivo Indice (index file)
           Key                          Posición
Bell
k
Harris
3
Itaca
1
   
Kellog
2

Archivo
   Posición                         Registro
1
Itaca | 56 | Chicago
2
Kellog | 77 | New York
3
Harris | 99 | California
   
k
Bell |  32 | Denver

Este es el origen de lo que se conoce como Indexamiento, que se verá en la siguiente sección.
 


5.8 Archivos que no se basan en Registros

Antecedentes


Ejemplo más comunes:

Abstract Data Models

Estos modelos o formatos definen la estructura del archivo, de manera que se tienen:

Headers:

Offset Name Description
0 magic magic number
4 width image width in pixels
8 height image height in pixels
12 depth bits per pixel
16 length image size in bytes
20 type encoding type
24 maptype type of colormap
28 maplength lenght of colormap

Sun Rasterfile Header

Contenido:

Ejemplo del uso de headers

Directorio de Archivos

Una referencia de los formatos más populares: http://www.wotsit.org