estructura de archivos base de datos

Silberschatz, Korth and Sudarshan11.NDatabase System Concepts - 5th Edition, Oct 23, 2005.

Organizacin de los archivos

Los archivos se organizan lgicamente como secuencias de

registros.

Los registros se corresponden con los bloques de disco.

Los bloques son de tamao fijo y las tuplas suelen ser de

tamao diferente.

Existen diversas enfoques de correspondencia entre base de

datos y archivo:

Archivos con registros de longitud fija (implementacin sencilla)

Archivos con registros de longitud variable


Registros de longitud fija

Considrese un archivo de cuentas bancarias con la siguiente

especificacin:

type cuenta = record

nmero_cuenta: char(10);

nombre_sucursal: char (22);

saldo: numeric(12,2);

end;

Cada carcter = 1 byte; el tipo numeric(12,2) = 8 bytes

Cada registro ocupa 40 bytes

Un enfoque sencillo es usar los primeros 40 bytes para el

primer registros, los siguientes 40 bytes para el segundo y asi

sucesivamente.


Archivo que contiene los archivos de cuenta


Problemas con registros de longitud fija

Resulta difcil borrar registros de esta estructura Hay que

rellenar el espacio ocupado por el registro que hay que borrar

con algn otro registro del archivo o tener algn medio de

marcar los registros borrados para que puedan pasarse por

alto.

A menos que el tamao de los bloques sea un mltiplo de

cuarenta (lo que resulta improbable) algunos de los registros

se saltarn los lmites de los bloques. Es decir, parte del

registro se guardar en un bloque y parte en otro. Harn falta,

por tanto, dos accesos a bloques para leer o escribir ese tipo

de registros.


Ocupar el espacio vacio por el borrado de un registro

desplazando varios registros

Cuando se borra un registro, se puede desplazar el situado a

continuacin al espacio ocupado que ocupaba el registro

borrado y hacer lo mismo con los dems.

Este enfoque necesita desplazar gran numero de registros.

Por ejemplo, borrar el registro 2:


Ocupar el espacio vacio por el borrado de un registro

desplazando el ltimo registro

Ejemplo: Borrar el registro 2 y desplazar el ltimo registro:

No resulta deseable desplazar registros, puesto que se

necesitan accesos adicionales.

Dado que las operaciones de insercin son mas frecuentes

que las de borrado es mejor dejar el espacio libre y esperar

una insercin para ocupar ese espacio..


Listas enlazadas libres para evitar desplazamientos

No basta con una simple marca en el registro borrado, es necesario

una estructura adicional.

Cabecera de archivo: contiene gran variedad de informacin del

archivo. Entre ellos se guarda la direccin del primer registro cuyo

contenido haya sido borrado. Se utiliza este primer registro para

guardar la direccin del segundo registro disponible, y as

sucesivamente.

Lista libre, que es una lista enlazada de los registros disponibles

enlazados con punteros.

Archivo que contiene los archivos de

cuenta

Borrado de los registros 1, 4 y 6 utilizando

estructura de lista libre


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.


El formato del registro con longitud variable

type lista-cuentas = record

nombre-sucursal : char (22);

informacin-cuenta : array [1 .. ] of record;

nmero-cuenta : char(10);

saldo : real;

end

end.


Tcnicas para implementar los registros de longitud

variable

1.Representacin en cadena de bytes

Adjunta smbolos especiales de fin de registro

Cada registro se guarda como una cadena de bytes

consecutivos

Inconvenientes:

Utilizacin del espacio dejado por un registro borrado. Gran

cantidad de fragmentos de disco desaprovechados.

No queda espacio para el aumento de tamao de registros

(campos variables), lo cual ocasiona desplazamiento fsico del

registro.


Estructura de pginas con ranuras

Se utiliza habitualmente para organizar los

registros en bloques

Contiene una cabecera con la siguiente

informacin:

Nmero de elementos del registro de la cabecera

El final del espacio vaco del bloque

Un array cuyas entradas contienen la ubicacin y el tamao

de cada registro.


Estructura de pginas con ranuras (Cont.)

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 aade a la cabecera una entrada que contiene su tamao y su

ubicacin.

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 tamao el valor

de 1). Adems, 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.

Tambin se actualiza de manera adecuada el puntero de final del

espacio libre de la cabecera. Se puede aumentar o disminuir el

tamao de los registros utilizando tcnicas parecidas, siempre y

cuando quede espacio en el bloque. El coste de trasladar los registros

no es demasiado elevado, dado que el tamao del bloque es limitado:

un valor tpico es cuatro kilobytes.


Estructura de pginas con ranuras (Cont.)

A menudo las bases de datos almacenan datos que

pueden ser mucho ms grandes que los bloques

del disco.

Las BD Relacionales suelen limitar el tamao de los

registros para que no superen el tamao de los

bloques.

Los objetos de gran tamao se suelen representar

en organizaciones de archivos de rboles B+.


Representacin en longitud fija

Espacio reservado

a.

a.


Representacin con listas


Representacin con listas, utilizando bloques ancla y

bloques de desbordamiento


Organizacin 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 Cmo

organizarlos en archivos?.

Organizacin de los archivos en montculos

Cualquier registro en cualquier parte del archivo en que haya

espacio suficiente

Los registros no se ordenan

Un archivo por cada relacin

Organizacin secuencial de los archivos

Registros guardados de manera secuencial segn el valor de la

clave de bsqueda

Organizacin asociativa (hash) de los archivos

Se calcula una funcin de asociacin para algn atributo de cada

registro que indica el bloque del archivo donde se debe colocar el

registro


Organizacin de archivos secuenciales

Diseados para el procesamiento eficiente de los

registros con un orden basado en alguna clave de

bsqueda.

La clave de bsqueda es cualquier atributo o

conjuntos de atributos, no necesariamente la clave

primaria.

Los registros se vinculan mediante punteros, para

recuperarlos rapidamente.

Los registros se guardan fsicamente en el orden

indicado por la clave de bsqueda o lo ms cercano

posible


Caractersticas de archivos secuenciales

Permite que los registros se lean de forma ordenada.

Resulta difcil mantener el orden fsico secuencial por el costo de desplazamiento de varios registros.

Para la insercin se aplican las siguientes reglas:

Localizar el registro que precede al que se va a insertar segn el orden de la clave de bsqueda.

Si existe algn 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.


Archivo secuencial para los registros de

cuenta

El archivo secuencial despus de una

insercin

Este enfoque funciona bien si hay que guardar un nmero relativamente

pequeo de registros en los bloques de desbordamiento. Cuando se

pierde la correspondencia entre el orden de la clave de bsqueda y el

fsico, el archivo debe ser reorganizado.

Insercin de registros en organizacin secuencial

Clave de bsqueda nombre sucursal


Organizacin de archivos en agrupaciones de varias

tablas

Los archivos secuenciales son tiles en SBD

pequeos que pueden organizar un archivo por

cada relacin con los servicios del SO.

Muchos SBD de gran tamao no utilizan

directamente el sistema operativo subyacente para

la gestin de los archivos.

Se asigna al SBD un archivo de gran tamao del

SO. En este archivo el SGBD guarda y administra

todas las relaciones.


select nmero-cuenta, nombre-cliente, calle-cliente, ciudad-cliente

from impositor, cliente

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

Ejemplo de guardar muchas relaciones en un solo archivo

Relacin: Impositor Relacin: Cliente

Estructura de archivo eficiente

para consultas que involucren a

Impositor |X| Cliente

22


Ventajas de archivos con agrupaciones de varias

tablas

Una organizacin de archivos en

agrupaciones de varias tablas es una

organizacin de archivos que

almacena registros relacionados de

dos o ms relaciones en cada bloque.

Este tipo de organizacin de archivos

permite leer registros que satisfacen la

condicin de reunin en un solo

proceso de lectura de bloques.

23


Desventajas de archivos con agrupaciones de varias tablas

Retarda el procesamiento de algunos tipos

de consultas, como:

Select * from Cliente

Los registros se hallan en bloques diferentes.

Para encontrar todas las tuplas de la relacin

cliente, se pueden enlazar todos los registros de

esta relacin mediante punteros.

24


Almacenamiento con diccionario de datos

Un SBD relacionales necesita tener datos sobre las relaciones, como puede ser su esquema. Esta informacin se denomina diccionario de datos o catlogo del sistema.

Contiene, entre otras cosas:

El nombre de las relaciones

El nombre de los atributos de cada relacin.

El dominio y la longitud de los archivos.

El nombre y la definicin de las vistas.

Restricciones de integridad.


Almacenamiento con diccionario de datos (cont)

Datos de usuario

Nombre de los usuarios autorizados

Autorizacin e informacin sobre las

cuentas.

Contraseas (formas de autentificacin)

Informacin estadstica y descriptiva

Nmero de tuplas de cada relacin

Mtodo de almacenamiento utilizado para

cada relacin (Ej. con agrupaciones o sin

agrupaciones)



Organizacin del almacenamiento

(secuencial, asociativa o en montculos) de

las relaciones y la ubicacin donde se

guarda cada relacin:

Si las relaciones se guardan en archivos del SO,

el diccionario guarda los nombres y direcciones

de los archivos.

Si la BD almacena todas las relaciones en un

solo archivo, el SBD puede guardar los bloques

que contienen los registros a travs de

estructuras de datos, como por ejemplo, las

listas.

27



Informacin sobre ndices

Nombre del ndice

Nombre de la relacin para la que se crea.

Atributos sobre los que se define.

Tipo de ndice formado.

28

Metadatos-relacin = (nombre-relacin, nmero-atributos)

Metadatos-atributos = (nombre-atributo, nombre-relacin, tipo-

dominio, posicin, longitud)

Metadatos-usuarios = (nombre-usuario, contrasea-cifrada, grupo)

Metadatos-ndices = (nombre-ndice, nombre-relacin, tipo-ndice,

atributos-ndice)

Metadatos-vistas = (nombre-vista, definicin)

estructura de archivos base de datos

Documents