Almacenamiento y Recuperación de
la Información
2do Semestre 2005
Wenceslao Palma M. <[email protected]>
www.inf.utfsm.cl/~wpalma/ari
Representación de Datos
Organización Física de los Datos
• Representación y organización física sobre un
medio de almacenamiento (índices, punteros, listas,
etc.).
• Representa la visión del administrador de los
archivos (o de la base de datos, DBA), que es
dependiente del dispositivo.
• El archivo es visto como una colección de bloques
en memoria secundaria.
Representación de Datos
Organización Física de los Datos
Operaciones a considerar:
• Controlar accesos.
• Asignar y administrar buffers.
• Crear y mantener directorios.
• Crear y mantener tablas en la memoria principal.
Representación de Datos
Elementos de Datos
• Pregunta a responder: ¿cómo se registran en el
disco los diferentes tipos de datos, al momento de
declaraciones como:
create table ActorDeCine
( nombre CHAR(30),
domicilio VARCHAR(255),
sexo CHAR(1),
fecha_nacimiento DATE
);
Representación de Datos
Elementos de Datos
Tipo CHAR(n): este string de largo fijo se representa
mediante un arreglo de n bytes.
• Si el valor guardado tiene un largo menor, se
completa el espacio con algún carácter especial.
Representación de Datos
Elementos de Datos
Tipo VARCHAR(n): este string de largo variable se
puede representar de dos formas:
• Largo más contenido: asignando un arreglo de (n+1)
bytes, siendo el primero de éstos el largo real del
dato. Bytes no usados se ignoran.
Representación de Datos
Elementos de Datos
• String terminado en Nulo: asigna, también, un
arreglo de (n+1) bytes, pero sin registrar el largo, sino
que tras el último byte de dato válido, se coloca un
carácter nulo.
Representación de Datos
Elementos de Datos
Tipo DATE: representable mediante un string de largo
fijo (típicamente CHAR(10).
• Ejemplo: 15-04-2004 se presenta con 10 caracteres,
uno por cada dígito más uno por cada guión.
Una idea similar se sigue con las horas, expresadas
como HH:MM:SS, o similar.
Representación de Datos
Elementos de Datos
En la mayoría de los otros tipos de datos, en
particular los BIT(n), booleanos y enumerativos se
representan con tantos bytes como sean suficientes
para contener el total de bits presentes, lo que
normalmente significa que el último de los bytes no se
usa totalmente.
Representación de Datos
Registros
• Registros de Largo Fijo
struct deposito
{
char nombre_sucursal[20];
int número_cuenta;
char nombre_cliente[20];
float saldo;
};
Representación de Datos
Registros de Largo Fijo
Almacenamiento secuencial:
R egistro
R egistro
R egistro
R egistro
R egistro
R egistro
R egistro
R egistro
R egistro
0
1
2
3
4
5
6
7
8
Perryridge
R ound H ill
M ianus
D ow ntow n
R edw ood
Perryridge
B righton
D ow ntow n
Perryridge
102
305
215
101
222
201
217
110
218
H ayes
T urner
Sm ith
Johnson
L indsay
W illiam s
G reen
Peterson
L yle
400
350
700
500
700
900
750
600
700
Representación de Datos
Registros de Largo Fijo
Almacenamiento secuencial: problemas...
• Difícil la eliminación de un registro...marca de
borrado o llenar con otro registro.
• A menos que el tamaño del bloque sea un múltiplo
del registro, algunos registros no podrán almacenarse
completamente en un bloque.
Representación de Datos
Registros de Largo Fijo
Almacenamiento secuencial:
R egistro
R egistro
R egistro
R egistro
R egistro
R egistro
R egistro
R egistro
0
1
3
4
5
6
7
8
P erryridge
R ound H ill
D owntown
R edwood
P erryridge
B righton
D owntown
P erryridge
102
305
101
222
201
217
110
218
H ayes
T urner
Johnson
L indsay
W illiams
G reen
P eterson
L yle
400
350
500
700
900
750
600
700
Eliminación del Registro 2, con corrimientos de
datos
Representación de Datos
Registros de Largo Fijo
Almacenamiento secuencial:
R egistro
R egistro
R egistro
R egistro
R egistro
R egistro
R egistro
R egistro
0
1
8
3
4
5
6
7
P erryridge
R ound H ill
P erryridge
D owntown
R edwood
P erryridge
Brighton
D owntown
102
305
218
101
222
201
217
110
H ayes
T urner
L yle
Johnson
L indsay
W illiams
G reen
P eterson
400
350
700
500
700
900
750
600
Eliminación del Registro 2, con traslado del registro
8
Representación de Datos
Registros de Largo Fijo
Almacenamiento secuencial, con uso de punteros:
E ncabezado
R egistro 0
R egistro 1
R egistro 2
R egistro 3
R egistro 4
R egistro 5
R egistro 6
R egistro 7
R egistro 8
P erryridge
102
H ayes
400
M ianus
D ow ntow n
215
101
S mith
Johnson
700
500
P erryridge
201
W illiams
900
D ow ntow n
P erryridge
110
218
P eterson
L yle
600
700
Eliminación de los Registros 1, 4 y 6.
Representación de Datos
Registros de Largo Fijo
Encabezados:
• El esquema del registro, o bien un puntero al lugar
donde el SABD almacena el esquema para este tipo
de registro.
• El largo del registro.
• Estampillas de tiempo que indican el momento que
el registro fue modificado/leído por última vez.
Representación de Datos
Registros de Largo Fijo
Encabezados: la base de datos mantiene información
del esquema, rescatada del create table, con:
• Los atributos de la relación, y sus tipos.
• El orden en el cual aparecen en la tupla.
• Restricciones sobre los atributos y la relación
misma.
Representación de Datos
Registros de Largo Variable
Campo de Largo Variable:
• Por lo general, se guardan al final del registro.
• En el encabezado se maneja un puntero al inicio de
cada campo de este tipo.
Representación de Datos
Registros de Largo Variable
Campo Repetitivo:
• Una alternativa es usar un caracter de separación
para delimitar los valores repetitivos del campo, y otro
separador para indicar el término del campo.
• Otra alternativa es usar un puntero a la primera
ocurrencia del campo, más un número que indique la
cantidad de veces de la repetición.
Representación de Datos
Registros de Largo Variable
Campo de Distintos Tipos:
• Cada tipo es precedido por un campo indicador de
tipo.
Representación de Datos
Registros de Largo Variable
Campo Opcional:
• Si el número total de campos del registro es alto,
pero el número de campos fijos es bajo, se puede
incluir una secuencia de duplas <nombre del campo,
valor del campo>, en vez de guardar sólo los valores.
• La secuencia anterior puede considerar un número
de campo, en lugar del nombre + un esquema para
mantener una correspondencia entre los campos y
dichos números.
Representación de Datos
Registros de Largo Variable
Grupo Repetitivo:
struct deposito
{
int número_cuenta;
char nombre_cliente[20];
float saldo;
};
struct lista-deposito
{
char
nombre_sucursal[20];
deposito set(info_cuenta);
}
Representación de Datos
Registros de Largo Variable
Grupo Repetitivo: uso de marca especial como fin de
registro.
Perryridge
102
Hayes
400
201
Round Hill
305
Turner
350

M ianus
215
Smith
700
Downtown
101
Johnson
500

110
Redwood
222
Lindsay
700

Brighton
217
Green
750

W illiams
900
218
Peterson
600

Lyle
700

Representación de Datos
Registros de Largo Variable
Grupo Repetitivo: uso de marca especial como fin de
registro ….problemas!!
• No es fácil volver a usar el espacio que ocupaba un
registro que se eliminó.
• En general, los registros no disponen de espacio
para crecer.
por lo tanto, no se usa normalmente.
Representación de Datos
Registros de Largo Variable
Grupo Repetitivo: Espacio Reservado.
Perryridge
R ound H ill
102
305
H ayes
T urner
400
350
201
W illiams
900
218
Lyle
700






M ianus
215
Smith
700

Johnson
500

600

101

Peterson

D owntown

110



R edwood
222
Lindsay
700






Brighton
217
G reen
750






Representación de Datos
Registros de Largo Variable
Grupo Repetitivo: Punteros (básico)
P er r yr idge
R ou nd H ill
M ia nu s
D ow ntow n
R edw ood
B r ighton
102
305
215
101
222
201
217
110
218
H a yes
T u r ner
S m ith
Johnson
L indsa y
W illia m s
G r een
P eter son
L yle
400
350
700
500
700
900
750
600
700
Representación de Datos
Registros de Largo Variable
Grupo Repetitivo: Punteros con dos archivos.
P erryridge
R ound H ill
M ia nus
D ow ntow n
R edw ood
B righton
201
110
218
102
305
215
101
222
217
W illia m s
P eterson
L yle
H a yes
T urner
S m ith
Johnson
L indsa y
G reen
900
600
700
400
350
700
500
700
750
Representación de Datos
Organización de Registros en Bloques
• Factor de bloqueo (fb):
tamaño del bloque / tamaño del registro
• En general, el cuociente no entrega un valor exacto.
Luego, se usa la fórmula:
tamaño del bloque / tamaño del registro
• Este factor permite saber el número de bloques del
archivo.
Representación de Datos
Organización de Registros en Bloques
Está la posibilidad de usar el espacio libre que queda
porque el tamaño del bloque no es múltiplo del
tamaño del registro, mediante registros atravesados
(SPAN).
Representación de Datos
Organización de Registros en Bloques
B loque i
B loque i+ 1
R egistro 1
R egistro 2
Registro 1
R egistro
4
Registro
Registro 2
R egistro 55
Registro
4
R egistro 3
Registro 3
R egistro 6
6
Registro
R egistros no A travesados
B loque i
B loque i+ 1
R egistro 11
Registro
R egistro 4b
Registro 4b
R egistro
2
Registro
R egistro 5
Registro 5
2
RRegistro
egistro 33
R egistro 6
Registro 6
R egistro 4a
Registro
4a
R egistro 7
Registro 7
…
R egistros A travesados (R egistros S pan)
Representación de Datos
Organización de Bloques en Archivos
• Asignación Contigua.
bloque
1
bloque
2
bloque
3
bloque
4
• Asignación Enlazada.
bloque
1
bloque
2
bloque
3
bloque
4
Representación de Datos
Organización de Bloques en Archivos
Representación de Datos
Organización de Bloques en Archivos
• Asignación Indexada.
Representación de Datos
Organización de Bloques en Archivos
Un archivo tiene un encabezado o descriptor de
archivo con:
• Información para determinar las direcciones de disco
de los bloques del archivo.
• Descripción de los formatos de registros: largo de
registro, orden de los campos en el registro,
separadores.
Representación de Datos
BLOBs
• Un dato de tipo BLOB representa un dato de gran
tamaño.
• Ejemplos comunes de datos BLOB son las
imágenes (GIF, JPEG), películas en formato MPEG y
el audio.
Representación de Datos
BLOBs
Almacenamiento:
• Debe almacenarse como una secuencia de bloques,
comúnmente asignados consecutivamente en un
cilindro para ser recuperado fácilmente.
• No obstante puede ser almacenado como una lista
enlazada de bloques.
Representación de Datos
BLOBs
Almacenamiento: (cont.)
• Por otro lado, puede requerirse que el BLOB sea
recuperado rápidamente, de modo que guardarlo en
un solo disco resulte insuficiente.
• Luego, será necesario particionar el BLOB entre
varios discos, alternando sus bloques entre ellos.
• Así, varios bloques del BLOB pueden ser leídos a la
vez, aumentando la tasa de recuperación por un
factor similar al número de discos de la partición.
FIN
Descargar

Representacion de los datos