Bases de Datos - Parte 8/10 Memoria secundaria

Tecnologas de Informacin
Tema 8. Estructuras de datos en memoria secundaria

Carlos Castillo

UPF 2007

Bibliografa:

Elmasri y Navathe: Fundamentos de Sistemas de Bases de Datos

3 edicin, 2002 (Captulo 6).

Garcia-Molina, Ullman y Widom: Database systems: the complete book. Prentice-Hall (Captulos 12 y 13).

Principios de diseo

Utilizar bloques de disco

Unidad mnima de lectura es un bloque

Evitar acceso aleatorio

Leer bloques contiguos

No siempre estn presentes ambos principios

Registros

Registro (tupla, fila)

Secuencia de campos de distinto tipo

Preguntas

Cmo se representa cada campo en disco?

Cmo se almacenan varios registros en bloques?

Qu pasa si los registros tienen distinto tamao?

Operaciones

Bsqueda Borrado Actualizacin - Insercin

Representacin de elementos de datos

Cada valor de un campo fsicamente ser una secuencia de bytes

Strings (cadenas) de ancho fijo

Strings de ancho variable

Fechas

Booleanos

Jerga informal

Ancho normalmente se refiere a un campo

Largo normalmente se refiere a un registro

Strings de tamao fijo

Tipo en SQL

CHAR(3)

Ejemplo

Cdigos de aeropuerto

Codificacin, siempre 3 bytes, ni menos ni ms, se usa un smbolo especial NULL (#, \000)

CDGC D G

MIAM I A

LLL L #

XX # #

Strings de tamao variable

Tipo en SQL

VARCHAR(30)

Ejemplo

Nombres de personas

Codificacin 1: Largo

Joan

L = log2(largo mximo) bytes representando el largo. Por eso se usa tanto VARCHAR(255)

Codificacin 2: Terminar con smbolo

Joan

L J O A N

J O A N #

Nmeros

Enteros

Siempre un nmero fijo de bytes

Utilizar mnimo posible

Con signo/sin signo aumenta rango

Misma representacin para enums

Flotantes

Representacin independiente del procesador

Fecha y hora

Tipo en SQL

TIMESTAMP

Codificacin 1: CHAR(14) YMDhms

4 de Marzo del 2005

10 de Enero del 1988 13:25

Se utilizan 14 caracteres => 14 bytes

Codificacin 2: Unix Time

Nmero de segundos transcurridos desde 1/1/1970 GMT

Se utiliza 1 entero => 4 bytes

19 de Enero del 2038 a las 3:14 AM

20050304120000

19880110132500

Bit

Tipo en SQL

BOOLEAN, BIT

Ejemplo

Gnero

Estado (activo/inactivo, ocupado/desocupado, etc.)

Consejo: reservar espacio para ms estados siempre = usar shortint/smallint

Representacin

1 byte completo

Registros

Esquema fsico

Forma de leer el registro de disco

Registros de largo fijo

Tamao mnimo del registro = 30+100+1+4 = 135 bytes

CREATE TABLE persona (

nombre CHAR(30),

direccin CHAR(100),

sexo BOOLEAN,

fnacimiento TIMESTAMP

);

Offsets

Problema:

Campos deben comenzar en mltiplo de 4 (u 8), especialmente los numricos

Registro debe comenzar en mltiplo de 4 (u 8)

nombre +0

direccin +30

sexo +130

fnacimiento +131

Offsets alineados

Los bytes extra normalmente no son usados, pues pueden aparecer-desaparecer al modificar el orden de los campos

nombre +0 [2 bytes extra]

direccin +32

sexo +132 [3 bytes extra]

fnacimiento +136

Encabezado de registro

Esquema usado (direccin)

Ej.: 2 bytes => 64k tablas distintas

Largo del registro

Ej.: 4 bytes => registros de hasta 2G

Fecha de ltimo acceso

Bloqueo

Ej.: 1 byte (RW, R, Libre)

OID

Campo extra que agregan algunas BD

Ejercicio 1

Registro con:

char(15), short int (2 bytes), timestamp, integer

Cunto espacio ocupa?

Registros comienzan en cualquier posicin

Alinear a mltiplos de 4


Ejercicio 2

Registro con:

double, varchar(17),byte, timestamp





Ejercicio 3

Registro con:

double, varchar(17),byte, timestamp

Registro requiere encabezado con dos punteros de 4 bytes y un byte





Bloques de Registros

Tamao fijo (ej.: 4Kb)

Varios registros, dependiendo del tamao

Encabezado de bloque

Identificador del bloque

Directorio de offsets de los registros en el bloque

Con espacio extra para crecer

Fechas de ltimo acceso/modificacin

Bloques ordenados

Cada bloque un conjunto de registros

Si los bloques tienen algn orden:

Reservar espacio en cada bloque

Bloques para overflow

Dividir el bloque y encadenarlos

Direccionamiento de bloques

Necesitamos asignar un ID a cada bloque

Referencias entre bloques (ej.: bloque siguiente)

Mantener tabla de bloques en cach

Indexar por bloques

Opciones

ID con significado => representa una posicin fsica del registro => direccin fsica

ID correlativo => simplemente numera bloques => direccin lgica

Ejemplos de direccionamiento fsico

Hostname (4 bytes en Ipv4)

Superficie

Cilindro

Pista

Sector

Bloque

Pueden cambiar en el tiempo

=> tabla de direccionamiento lgico a fsico

Registros de largo variable

Encabezado de registro contiene largos

Ejemplo

persona(nombre,gnero,direccin,fnacimiento)

Encabezado del registro

Largo del registro

Offset de fnacimiento (no es necesario!)

Offset de nombre

Offset de direccin

Mejor orden:

Gnero Fnacimiento Nombre - Direccin

Registros de largo variable: ideas para optimizar

Se ponen los campos de ancho fijo primero

Campos que admiten NULL pueden ser tratados como un caso especial

En vez del offset, se guarda un NULL

Registros grandes

Ejemplo: campo de tipo TEXT

Idea:

Usar varios bloques

En el encabezado del bloque, se guarda un puntero al siguiente bloque

En el siguiente bloque, se indica que es un bloque de continuacin

Registros muy grandes

Ejemplo: campo de tipo BLOB

Imagen

Sonido

Se recupera normalmente completo

Normalmente no se buscan por contenido

Almacenamiento: en espacio aparte

Registros muy grandes: administracin externa

Guardar una URL

Se ahorra transmitir el BLOB a travs del socket usado para la BD

Se ahorra cargar el BLOB en memoria

Requiere: borrado, modificacin, insercin aparte

Podemos hacer ms: dividir el BLOB en varios discos para mejor velocidad

El eterno dilema

Es ms eficiente, pero es ms difcil de mantener

Modificaciones

Insercin

Registros ordenados => cada registro va a un bloque especfico

Borrado

Lista de espacios libres en el bloque

Marcar registros como no usados => fragmentacin

Polticas de asignacin: first-fit, best-fit

Actualizacin

Si cambia el tamao => borrado + insercin

Indexacin
Indizacin?

ndice primario

ndice

Valor de (algunas) clave(s) primaria(s) (ordenado)

Puntero a bloque con esa clave primaria (ordenado)

Aaron, Ed1Adams, John2...Wong, Jamesn-1Wright, Pamn

Bloque 1Aaron, Ed Acosta, Marc

Bloque 2Adams, John Akers, Jan

Bloque nWright, Pam Zimmer, Byron

Densidad de ndice

ndice denso

Todos los registros tienen 1 puntero

ndice disperso

No todos los registros tienen 1 puntero

Densidad = Registros existentes / Registros indexados

Los ndices primarios son dispersos

Pueden combinarse ndices de distinta densidad => skip lists

ndice de agrupacin

Registros ordenados por un campo que no es nico.

Ej.: cod_aero, num_vuelo

Cod_aero BloqueAAR1LAN1QAT2VAR3

Bloque 1AAR, 222AAR, 333LAN, 444

Bloque 2LAN, 555LAN, 666QAT, 777

Bloque 3VAR, 888

ndice de agrupacin con bloques separados

Se reserva espacio en cada bloque

Cod_aero BloqueAAR1LAN2QAT4...

Bloque 1AAR, 222AAR, 333#next #

Bloque 2LAN, 444LAN, 555LAN, 666next 3

Bloque 3LAN,777##next #

Bloque 4QAT,888QAT,999#next #

ndice secundario

Se construye sobre un campo que no es clave primaria

Es un ndice denso (cada registro tiene un lugar en el ndice)

ndice secundario,
sobre campo nico

Ej.:

Pais( id_pais, nombre_pais )

nombre_paisid_bloqueArgentina3Argelia1Burund3Camern2Chad2...

Bloque 11, Francia2, Argelia3, Suecia

Bloque 24, Camern5, Chad6, Mxico

Bloque 37, Burund8, Noruega9, Argentina

ndice secundario,
sobre campo no-nico

Ej.:

Persona( dni, nombre, apellido )

nombreid_indiceAnna1Joan2Jordi3Xavier4

Bloque 1x, Anna, xx, Joan, x

Bloque 2x, Jordi, xx, Anna, x

Bloque 3x, Joan, xx, Jordi, x

1B1R1, B2R2

2B1R2, B3R1

3B3R2, B2R1

Se utiliza un nivel intermedio de indireccin

ndice invertido

ndice para textos o documentos

Recuperacin por palabra

Variante de ndice secundario con clave no-nica

Ejemplo ndice invertido

Pre-proceso de ndice invertido

Lematizacin

Hay varios tipos de documentos

Haber|varios|tipo|de|documento

No siempre es fcil

cruces (cruz o cruzar, depende del contexto)

Eliminacin stopwords

Son muy frecuentes

No aportan informacin

ndice al documento/prrafo/posicin

Ejercicio

Documento 1

Un caballo es ms rpido que un coche

Documento 2

Conduca un coche blanco

Document 3

Dos caballos blancos

Crear ndice al documento y a la palabra

Algoritmo de Construccin

En memoria

Leer para ver frecuencias, obtener espacio, escribir listas de posteo

Variante a disco

Por bloques

Construir en memoria para un bloque

Vaciar a disco

Unir bloques

Compresin de listas de posteo

Hashing

Hashing en memoria secundaria

Cada bucket de la tabla de hashing es un bloque

Se admiten k colisiones, k=registros por bloque

Los bloques pueden tener punteros a bloques para desbordamiento

Crecer puede ser muy lento en disco (rehashing)

Hashing extensible

La funcin de hashing tiene x bits

Se ocupa primero 1 bit => slo 2 buckets

Cuando se produce overflow, se reorganiza para ocupar 2 bits => 4 buckets

La tabla de hashing crece dinmicamente duplicando su tamao

Resumen

Los SGBD ocultan una alta complejidad

Conocer cmo se organizan cada motor de bases de datos ayuda a obtener mejor eficiencia

ndices generan sobrecosto en espacio y sobrecosto en tiempo al modificar los datos => usar responsablemente

Tecnologas de la Informacin

Dr. Ricardo Baeza-Yates, Dr. Carlos CastilloUniversitat Pompeu Fabra - 2005

Click to edit the title text format

Click to edit the outline text format

Second Outline Level

Third Outline Level

Fourth Outline Level

Fifth Outline Level

Sixth Outline Level

Seventh Outline Level

Eighth Outline Level

Ninth Outline Level

Documents

Bases de Datos - Parte 8/10 Memoria secundaria