CAPÍTULO II: ESTRUCTURA DE ARCHIVOS

publicado a la‎(s)‎ 11 jun. 2012 8:14 por Hernan Nina Hanco

2.1. Organización de los archivos

Los archivos se organizan lógicamente como secuencias de registros y estos se corresponden con los bloques de disco. Los bloques son de tamaño fijo y las tuplas suelen ser de tamaño diferente, por lo tanto, es necesario aplicar enfoques de correspondencia entre la base de datos y archivo, dentro de los cuales tenemos:

  • Archivos con registros de longitud fija (implementación sencilla)

  • Archivos con registros de longitud variable

Registros de longitud fija

Considérese un archivo de cuentas bancarias con la siguiente especificación:

type cuenta = record

 número_cuenta: char(10);

 nombre_sucursal: char (22);

 saldo: numeric(12,2);

 end;

Cada carácter es un byte; el tipo numeric(12,2) = 8 bytes, entonces cada registro ocupa 40 bytes, por lo tanto, un enfoque sencillo es usar los primeros 40 bytes para el primer registros, los siguientes 40 bytes para el segundo y así sucesivamente.

En la siguiente figura se muestra un archivo que contiene los registros de cuenta


Problemas en el enfoque de registros de longitud fija

  1. Resulta difícil borrar registros de esta estructura, puesto que debemos rellenar el espacio ocupado por el registro que se va a borrar con algún otro registro del archivo, o tener alguna manera de marcar los registros borrados para poder pasarlos por alto.

  2. A menos que el tamaño de los bloques sea un múltiplo de cuarenta (lo que resulta improbable) algún registro se saltará los límites de los bloques. Es decir, parte del registro se guardará en un bloque y parte en otro. Harán falta, por tanto, dos accesos a bloques para leer o escribir esos registros.


Cuando se borra un registro, se puede desplazar el situado a continuación al espacio ocupado que ocupaba el registro borrado y hacer lo mismo con los demás. hasta que todos los registros situados a continuación del borrado se hayan desplazado hacia delante. Este enfoque necesita desplazar gran número de registros. Puede que fuera más sencillo desplazar simplemente el último registro del archivo al espacio ocupado por el registro borrado.

Figura. Borrado del registro 2 y todos los registros desplazados

Figura. Registro 2 borrado y el último registro desplazado


No resulta deseable desplazar registros, puesto que se necesitan accesos adicionales. Dado que las operaciones de inserción son más frecuentes que las de borrado es mejor dejar el espacio libre y esperar una inserción para ocupar ese espacio.

Para identificar un registro borrado podemos señalar con una simple marca en el registro borrado, pero ello no es suficiente, por ser complicada la ubicación del registro borrado para realizar una nueva inserción, por lo tanto es necesario una estructura adicional.

Podemos utilizar una cabecera de archivo que contiene gran variedad de información del archivo, entre ellos se guarda la dirección del primer registro cuyo contenido haya sido borrado se utiliza este primer registro para guardar la dirección del segundo registro disponible, y así sucesivamente generando así una estructura de lista libre, que es una lista enlazada de los registros disponibles enlazados con punteros.

Lista libre después del borrado de los registros 1,4 y 6.

Registros de longitud variable
Surgen de varias maneras en los sistemas de bases de datos:
  • Almacenamiento de varios tipos de registros en un mismo archivo.
  • Tipos de registro que permiten longitudes variables para uno o varios campos.
  • Tipos de registro que permiten campos repetidos, como los arrays o multiconjuntos.

Existen diferentes técnicas para implementar los registros de longitud variable. La estructura de páginas con ranuras se utiliza habitualmente para organizar los registros en bloques. Hay una cabecera al principio de cada bloque, que contiene la información siguiente:

  1. El número de elementos del registro de la cabecera

  2. El final del espacio vacío del bloque

  3. Un array cuyas entradas contienen la ubicación y el tamaño de cada registro.

Estructura de páginas con ranuras


Los registros reales se ubican de manera contigua en el bloque, empezando desde el final del mismo. El espacio libre dentro del bloque es contiguo, entre la última entrada del array de la cabecera y el primer registro. Si se inserta un registro se le asigna espacio al final del espacio libre y se añade a la cabecera una entrada que contiene su tamaño y su ubicación. Si se borra un registro se libera el espacio que ocupa y se da el valor de “borrada” a su entrada (por ejemplo, se le da a su tamaño el valor de –1). Además, se desplazan los registros de bloque situados antes del registro borrado, de modo que se ocupe el espacio libre creado por el borrado y todo el espacio libre vuelve a hallarse entre la última entrada del array de la cabecera y el primer registro.

También se actualiza de manera adecuada el puntero de final del espacio libre de la cabecera. Se puede aumentar o disminuir el tamaño de los registros utilizando técnicas parecidas, siempre y cuando quede espacio en el bloque. El coste de trasladar los registros no es demasiado elevado, dado que el tamaño del bloque es limitado: un valor típico es cuatro kilobytes.

A menudo las bases de datos almacenan datos que pueden ser mucho más grandes que los bloques  del disco. Las BD Relacionales suelen limitar el tamaño de los registros para que no superen el tamaño de los bloques. Los objetos de gran tamaño se suelen representar en organizaciones de archivos de árboles B+.

2.2. Organización de los registros en archivos

Hasta ahora se ha estudiado la manera en que se representan los registros en la estructura de archivos. Las relaciones son conjuntos de registros. Dado un conjunto de registros ¿Cómo organizarlos en archivos?.

  • Organización de los archivos en montículos, se puede colocar cualquier registro en cualquier parte del archivo en que haya espacio suficiente. Los registros no se ordenan. Generalmente sólo hay un archivo por cada relación.

  • Organización secuencial de los archivos, Los registros se guardan en orden secuencial según el valor de la “clave de búsqueda”.
  • Organización asociativa (hash) de los archivos, Se calcula una función de asociación para algún atributo de cada registro que indica el bloque del archivo donde se debe colocar el registro

Generalmente se emplea un archivo separado para almacenar los registros de cada relación, No obstante, en cada organización de archivos en agrupaciones de varias tablas se pueden guardar en el mismo archivo registros de relaciones diferentes, además, los registros relacionados de las diferentes relaciones se guardan en el mismo bloque, por lo que cada operación de E/S afecta a registros relacionados de todas esas relaciones.


Organización de archivos secuenciales

Diseñados para el procesamiento eficiente de los registros con un orden basado en alguna clave de búsqueda. La clave de búsqueda es cualquier atributo o conjuntos de atributos, no necesariamente la clave primaria. Los registros se vinculan mediante punteros, para recuperarlos rápidamente y se guardan físicamente en el orden indicado por la clave de búsqueda o lo más cercano posible.


Los archivos secuenciales permiten que los registros se leen de forma ordenada y resulta difícil mantener el orden físico secuencial por el costo de desplazamiento de varios registros. En el caso de la inserción se aplican las siguientes reglas:

  • Localizar el registro que precede al que se va a insertar según el orden de la clave de búsqueda.
  • Si existe algún espacio libre dentro del mismo bloque, el nuevo registro se insertará ahí. Caso contrario se inserta en un bloque de desbordamiento.
  • Luego de insertar, ajustar los punteros.

Inserción de registros en organización secuencial


Organización de archivos en agrupaciones de varias tablas

Los archivos secuenciales son útiles en SBD pequeños que pueden organizar un archivo por cada relación con los servicios del SO. Sin embargo, muchos SBD de gran tamaño no utilizan directamente el sistema operativo subyacente para la gestión de los archivos. Se asigna al SBD un archivo de gran tamaño del SO. En este archivo el SGBD guarda y administra todas las relaciones.

Algunas comparaciones de guardar muchas relaciones en un solo archivo.
Ejemplo de guardar muchas relaciones en un solo archivo

select número-cuenta, nombre-cliente, calle-cliente, ciudad-cliente
from impositor, cliente

where impositor.nombre-cliente = cliente.nombre-cliente

Una organización de archivos en agrupaciones de varias tablas es una organización de archivos que almacena registros relacionados de dos o más relaciones en cada bloque. Este tipo de organización de archivos permite leer registros que satisfacen la condición de reunión en un solo proceso de lectura de bloques.

Si embargo, en algunas situaciones puede retardar el procesamiento de algunos tipos de consultas, como:

Select * from Cliente
Los registros se hallan en bloques diferentes y para encontrar todas las tuplas de la relación cliente, se pueden enlazar todos los registros de esta relación mediante punteros.
2.3. Almacenamiento con diccionario de datos

Un sistema de bases de datos relacionales necesita tener datos sobre las relaciones, como el esquema de las mismas. Esta información se denomina diccionario de datos o catálogo del sistema. Entre los tipos de información que debe guardar el sistema figuran los siguientes:

  • Los nombres de las relaciones

  • Los nombres de los atributos de cada relación

  • Los dominios y las longitudes de los atributos

  • Los nombres de las vistas definidas en la base de datos y las definiciones de esas vistas

  • Las restricciones de integridad (por ejemplo, las restricciones de las claves)


Además, muchos sistemas guardan los datos siguientes de los usuarios del sistema:

  • Los nombres de los usuarios autorizados

  • La información de las cuentas de usuarios

  • Contraseñas u otra información usada para autenticar a los usuarios


Además, se puede guardar información estadística y descriptiva sobre estos asuntos:

  • Número de tuplas de cada relación

  • Método de almacenamiento utilizado para cada relación (por ejemplo, con agrupaciones o sin agrupaciones)


El diccionario de datos puede también anotar la organización del almacenamiento (secuencial, asociativa o con montículos) de las relaciones y la ubicación donde se almacena cada relación:

  • Si las relaciones se almacenan en archivos del sistema operativo, el diccionario no podría anotar los nombres de los archivos que almacenan cada relación.

  • Si la base de datos almacena todas las relaciones en un único archivo, el diccionario puede anotar los bloques que almacenan los registros de cada relación en una estructura de datos como una lista enlazada.

Guardar información sobre cada índice de cada una de las relaciones:

  • El nombre del índice

  • El nombre de la relación para la que se crea el índice

  • Los atributos sobre los que se define el índice

  • El tipo de índice formado

Toda esta información constituye, en efecto, una base de datos en miniatura. Algunos sistemas de bases de datos guardan esta información utilizando estructuras de datos

y código especiales. Suele resultar preferible guardar los datos sobre la base de datos en la misma base de datos. Al utilizar la base de datos para guardar los datos del sistema se simplifica la estructura global del sistema y se permite que se utilice toda la potencia de la base de datos en obtener un acceso rápido a los datos del sistema.

La elección exacta de la manera de representar los datos del sistema utilizando relaciones debe tomarla el diseñador del sistema. A continuación se ofrece una representación posible con las claves primarias subrayadas:


Metadatos-catálogo-sistema = (nombre-relación, número-atributos)

Metadatos-atributos = (nombre-atributo, nombre-relación, tipo-dominio, posición, longitud)

Metadatos-usuarios = (nombre-usuario, contraseñacifrada, grupo)

Metadatos-índices = (nombre-índice, nombre-relación, tipo-índice, atributos-índice)

Metadatos-vistas = (nombre-vista, definición)


2.5. Almacenamiento para las bases de datos orientado a objetos - Ser investigado por el estudiante
Comments