abd tema1 parteii

Administración de Base de Datos

Manejo de memoria (Parte II)

Prof Mercy Ospina Torres [email protected]

mailto:[email protected]

El DBA

Concurrencia

Diccionario Datos

Integridad

Seguridad

Proc. Consultas

Administración de Base de Datos 2

El SMBD

Manejo de Memoria

Restauración

Contenido

• Manejo de memoria– Componentes del SMBD– Tipos de memoria– Acceso a la base de datos– Archivos

• Encabezado• Registro• Tamaño de un archivo• Organizaciones de archivo

– Secuencial– Hash– Indexada

• Vías de acceso

Marzo 2012

Manejo de memoria

El DBA

Concurrencia

Diccionario Datos

Integridad

Seguridad

Proc. Consultas


El SMBD

Manejo de Memoria

Restauración

Organizaciones de ArchivoClase anterior

• Organización Secuencial– Montículo

– Ordenada

• Organización Directa– Técnicas Hash

– Manejo de Colisiones

Marzo 2012

Manejo de memoria

El DBA

Concurrencia

Diccionario Datos

Integridad

Seguridad

Proc. Consultas


El SMBD

Manejo de Memoria

Restauración

Organizaciones de ArchivoDiscusión Hash Extensible

Marzo 2012

Manejo de memoria

El DBA

Concurrencia

Diccionario Datos

Integridad

Seguridad

Proc. Consultas


El SMBD

Manejo de Memoria

Restauración

Organización indexada

• ¿Qué es un índice?• Tipos de índices• Organización Secuencial ordenada

indexada• Organización directa indexada• Otras• Índices multinivel• Estructuras de datos

– Listas– Arboles B y B+– Indices Bitmap

Marzo 2012

Manejo de memoria


¿Qué es un

índice?

Título No pag

Marzo 2012

El DBA

Concurrencia

Diccionario Datos

Integridad

Seguridad

Proc. Consultas


El SMBD

Manejo de Memoria

Restauración


• ¿Qué es un índice?– Un índice en una BD es similar al índice de un

libro, es una estructura que puede consultarse al buscar elementos de datos en una BD.

DatosIndice

Marzo 2012

Manejo de memoria

El DBA

Concurrencia

Diccionario Datos

Integridad

Seguridad

Proc. Consultas


El SMBD

Manejo de Memoria

Restauración


• Definición de índice– Es una estructura de datos llamada Archivo de

Indice que permite al SMBD localizar registros concretos dentro de un Archivo de datos, de manera más rápida.

– Entrada de datos: registro del archivo índice

• <K, P>• <K, lista-P>K: campos indexados (clave de búsqueda)P: apuntador a página

Si K está compuesto de un solo atributo entonces el índice es simple,Si no el índice es compuesto

Marzo 2012

Manejo de memoria

El DBA

Concurrencia

Diccionario Datos

Integridad

Seguridad

Proc. Consultas


El SMBD

Manejo de Memoria

Restauración


• Organizaciones de índice– Secuenciales ordenados: están ordenados

físicamente según el valor de la clave K.– Directos (hash): están organizados según una

función hash sobre la clave K.

• En este curso se trabajara con índices secuenciales ordenados

Marzo 2012

Manejo de memoria

El DBA

Concurrencia

Diccionario Datos

Integridad

Seguridad

Proc. Consultas


El SMBD

Manejo de Memoria

Restauración


• Tipos de Índices– Primario: El índice esta construido sobre un

archivo ordenado sobre un campo clave de ordenamiento.

– Agrupado: El índice esta construido sobre un archivo ordenado sobre un campo no clave de ordenamiento.

– Secundario: El índice esta construido sobre un archivo no ordenado o sobre un campo que no es clave de ordenamiento.

Marzo 2012

Manejo de memoria


Índice primario

Los títulos está en el mismo orden interno y son únicos dentro del

libro

Marzo 2012


Índice Agrupado

Los nombres se agrupan

por letras, el índice tiene el mismo orden que la guía

Marzo 2012


Índice secundario

Las palabras están

ordenadas alfabéticament

e Indica las

páginas donde se encuentra cada palabra

Marzo 2012

El DBA

Concurrencia

Diccionario Datos

Integridad

Seguridad

Proc. Consultas


El SMBD

Manejo de Memoria

Restauración

Organizaciones secuencialIndexada

• Índice primario

1234 Maria Castillo DE1657 Ana Paredes CO3456 Jose Perdomo CO

5432 Pedro López DE5678 Luis Perez MT5879 Beatriz Martínez MT

6784 Ana Vasquez MT7865 Victor Trejo CO8762 Julio León CO

…..

Manejo de memoria

Archivo de datosArchivo índice

fb 8 registros por bloque

Marzo 2012

El DBA

Concurrencia

Diccionario Datos

Integridad

Seguridad

Proc. Consultas


El SMBD

Manejo de Memoria

Restauración

Organizaciones secuencialIndexada

• Índice primario




…..

12341657 345654325678587967847865

11122233

8762 . .

3…

Manejo de memoria



Marzo 2012

El DBA

Concurrencia

Diccionario Datos

Integridad

Seguridad

Proc. Consultas


El SMBD

Manejo de Memoria

Restauración

Organización secuencialIndexada

• Índices densos– Dispone de un registro de índice para CADA

UNO de los valores de la clave de búsqueda del archivo




…..

12341657 345654325678587967847865

11122233

8762 . .

3…

Manejo de memoria Archivo de datos

Marzo 2012

El DBA

Concurrencia

Diccionario Datos

Integridad

Seguridad

Proc. Consultas


El SMBD

Manejo de Memoria

Restauración


• Índices disperso– Dispone de un registro de índice para

ALGUNOS de los valores de la clave de búsqueda del archivo (p.e. uno por página)




…... .

…

345658798762…

123

. .…

Manejo de memoria

Marzo 2012

El DBA

Concurrencia

Diccionario Datos

Integridad

Seguridad

Proc. Consultas


El SMBD

Manejo de Memoria

Restauración


• Índice agrupado

1657 Ana Paredes CO6784 Ana Vasquez MT5879 Beatriz Martínez MT

3456 Jose Perdomo CO8762 José León CO1235 José Castillo DE

5678 Luis Perez MT2432 Luis Ramirez DE6865 Luis Urbina CO

5555 Luis Ricardo DE

AnaBeatriz JoseLuis

112?

. . …

Manejo de memoria


Marzo 2012

El DBA

Concurrencia

Diccionario Datos

Integridad

Seguridad

Proc. Consultas


El SMBD

Manejo de Memoria

Restauración


• Este tipo de archivo necesita ser reorganizado periódicamente para mantener la eficiencia

• La principal desventaja de esta organización es que es preciso mantener el orden a medida que se insertan y borran registros

• El problema se agrava debido a que se debe mantener el orden en ambos archivos tanto el de datos como en el de índice.

Marzo 2012

Manejo de memoria

El DBA

Concurrencia

Diccionario Datos

Integridad

Seguridad

Proc. Consultas


El SMBD

Manejo de Memoria

Restauración

Organización directa indexada

• Índice secundario

6784 Ana Vasquez MT2432 Luis Ramirez DE3456 Jose Perdomo CO

1657 Ana Paredes CO6865 Luis Urbina CO

5678 Luis Perez MT8762 José León CO

5879 Beatriz Martínez MT1235 José Castillo DE5555 Luis Ricardo DE

123516572432 345655555678587967846865

421142412

68658762 . .

23…



Marzo 2012

Manejo de memoria

El DBA

Concurrencia

Diccionario Datos

Integridad

Seguridad

Proc. Consultas


El SMBD

Manejo de Memoria

Restauración


• Índice secundario (atributo no único)





AnaBeatrizJoseLuis…

Archivo de datos

Registros de tamaño variable


1, 241, 3, 41, 2, 3,4

Archivo índice

Marzo 2012

Manejo de memoria

El DBA

Concurrencia

Diccionario Datos

Integridad

Seguridad

Proc. Consultas


El SMBD

Manejo de Memoria

Restauración


• Listas invertidas

N registro relativo

registro Apun-tador

123


4 (inicio)

59

45


86

67


102

8910


37null



141 1


Marzo 2012

Manejo de memoria

El DBA

Concurrencia

Diccionario Datos

Integridad

Seguridad

Proc. Consultas


El SMBD

Manejo de Memoria

Restauración


• Indice multinivel





123516572432 34565555567858796784

32113231

68658762 . .

23…

67848762

12

Archivo de datosArchivo índiceNivel 1 (interno)

Archivo índiceNivel 2

Marzo 2012

Manejo de memoria

El DBA

Concurrencia

Diccionario Datos

Integridad

Seguridad

Proc. Consultas


El SMBD

Manejo de Memoria

Restauración

Organización indexadaArboles B y B+

El inconveniente principal de la organización indexada secuencial reside en que el rendimiento, tanto para buscar en el índice se degrada según crece el archivo de datos.

Las estructuras de árbol B y B+ mantienen su eficiencia a pesar de la inserción y borrado de datos, y pueden ser usados como índices primarios, secundarios o agrupados

Marzo 2012

Manejo de memoria

El DBA

Concurrencia

Diccionario Datos

Integridad

Seguridad

Proc. Consultas


El SMBD

Manejo de Memoria

Restauración


• Son arboles de búsqueda balanceados– La profundidad de cada subarbol difiere en +-1– Un recorrido en profundidad inorden da los

elementos ordenados.

Marzo 2012

Manejo de memoria

El DBA

Concurrencia

Diccionario Datos

Integridad

Seguridad

Proc. Consultas


El SMBD

Manejo de Memoria

Restauración


• Cada nodo ocupa una página de disco.

K1<K2< ….Km-1

• Se puede ver como un índice multinivel, donde cada nodo es un subíndice

• El orden del árbol será el numero de apuntadores que pueda tener cada nodo– Si tenemos m apuntadores P y (m-1) claves K

las cuales ocupan un bloque de tamaño B entonces

P1 K1 P2 K2 ……. Km-1 Pm

P.m + K(m-1) = B m = (B+K) (P+K)º

Marzo 2012

Manejo de memoria

El DBA

Concurrencia

Diccionario Datos

Integridad

Seguridad

Proc. Consultas


El SMBD

Manejo de Memoria

Restauración


• Cada nodo, excepto la raiz debe estar lleno al menos hasta la mitad (m/2).

• La altura del árbol depende de su orden– Altura mínima:

– Altura máxima:

– n es el numero total de valores distintos de K

Marzo 2012

Manejo de memoria

El DBA

Concurrencia

Diccionario Datos

Integridad

Seguridad

Proc. Consultas


El SMBD

Manejo de Memoria

Restauración


• Árbol B– Cada celda apunta al archivo de datos.

– La cantidad de accesos para localizar un valor de K es al menos uno y a lo sumo la altura del árbol.

Marzo 2012

Manejo de memoria

El DBA

Concurrencia

Diccionario Datos

Integridad

Seguridad

Proc. Consultas


El SMBD

Manejo de Memoria

Restauración


• Árbol BP1 K1 P2 K2 ……. Km-1 Pm

Marzo 2012

Manejo de memoria

……. …….

K<K1

…….

K1<K<K2 K>Km-1

Apuntador al archivo de datos

El DBA

Concurrencia

Diccionario Datos

Integridad

Seguridad

Proc. Consultas


El SMBD

Manejo de Memoria

Restauración


• Árbol B+– Variación del Árbol B

– Solo las hojas apuntan a los datos

Marzo 2012

Manejo de memoria

El DBA

Concurrencia

Diccionario Datos

Integridad

Seguridad

Proc. Consultas


El SMBD

Manejo de Memoria

Restauración


• Árbol B+P1 K1 P2 K2 ……. Km-1 Pm

Marzo 2012

Manejo de memoria

1 2 ……. 5 6 7 ……. 10

K<K1

11 12 ……. 15

K1<=K<K2 K>Km-1

Apuntador al archivo de datos

El DBA

Concurrencia

Diccionario Datos

Integridad

Seguridad

Proc. Consultas


El SMBD

Manejo de Memoria

Restauración


• Los árboles B+ son más fáciles de mantener que los árboles B.

• Son los tipos de índice por defecto en las BD

• Los árboles B son usados para almacenar datos tipo CLOB o BLOB

Marzo 2012

Manejo de memoria

El DBA

Concurrencia

Diccionario Datos

Integridad

Seguridad

Proc. Consultas


El SMBD

Manejo de Memoria

Restauración

Organización de Archivos

• Ejercicio – Dado un archivo de datos para Proveedor con

los siguientes campos

+ un byte para marcado de borrado1. Si el tamaño del bloque es 2048 bytes, hay

500.000 registros, y los registros son de tamaño fijo no extensibles• Calcular fb y TA de Proveedores.

RIF Nombre Región Ciudad Dirección telefono email

9 80 20 30 250 50 50

Marzo 2012

Manejo de memoria

El DBA

Concurrencia

Diccionario Datos

Integridad

Seguridad

Proc. Consultas


El SMBD

Manejo de Memoria

Restauración

Organización de Archivos

• Ejercicio (continuación)2. Si el archivo Proveedor está ordenado por RIF

y se tiene un índice de 2 niveles disperso sobre este campo. Calcule la cantidad de accesos para obtener un RIF dado.

3. Calcule la altura máxima de un índice B+ sobre RIF.

4. Si el archivo está ordenado por ciudades indique que tipo de índices se pueden crear sobre este, para cualquier atributo. (primario, agrupado o secundario)

Marzo 2012

Manejo de memoria

El DBA

Concurrencia

Diccionario Datos

Integridad

Seguridad

Proc. Consultas


El SMBD

Manejo de Memoria

Restauración

Próxima clase

Marzo 2012

• Índices Bitmap• Resumen vías de acceso• Inicio tema Recuperación

Manejo de memoria

El DBA

Concurrencia

Diccionario Datos

Integridad

Seguridad

Proc. Consultas


El SMBD

Manejo de Memoria

Restauración


• Índices Bitmap– Indice especial que usa arreglos de bits

• 01000111101011

– Para crear un índice bitmap sobre un campo se crean arreglos de bits por cada valor diferente y se coloca 1 en la posición del registro que cumple dicho valor

– Cada bit corresponde a un rowid

Marzo 2012

Manejo de memoria

El DBA

Concurrencia

Diccionario Datos

Integridad

Seguridad

Proc. Consultas


El SMBD

Manejo de Memoria

Restauración


• Índice Bitmap– Indice bitmap sobre sexo

Marzo 2012

Manejo de memoriaId Apellido Región Géne-

roBitmaps

F M

1 PEREZ NORTE F 1 0

2 GARCIA CENTRO M 0 1

3 LOPEZ SUR M 0 1

4 MARTIN SUR Null 0 0

5 BROWN CENTRO F 1 0

6 CANEPA NORTE M 0 1

El DBA

Concurrencia

Diccionario Datos

Integridad

Seguridad

Proc. Consultas


El SMBD

Manejo de Memoria

Restauración


• Índices Bitmap– Índice bitmap sobre región

Marzo 2012

Manejo de memoriaId Apellido Región Géne-

roBitmap

NORTE CENTRO SUR

1 PEREZ NORTE F 1 0 0

2 GARCIA CENTRO M 0 1 0

3 LOPEZ SUR M 0 0 1

4 MARTIN SUR Null 0 0 1

5 BROWN CENTRO F 0 1 0

6 CANEPA NORTE M 1 0 0

El DBA

Concurrencia

Diccionario Datos

Integridad

Seguridad

Proc. Consultas


El SMBD

Manejo de Memoria

Restauración


• Índices Bitmap (búsquedas)

– Clientes femeninos de región centro• AND entre los bitmaps F y Centro

– Clientes masculinos de la región norte o sur• (M AND Norte) OR (M AND Sur)

Marzo 2012

Manejo de memoria

Id Apellido Región Géne-ro

Bitmaps

F M NORTE CENTRO SUR

1 PEREZ NORTE F 1 0 1 0 0

2 GARCIA CENTRO M 0 1 0 1 0

3 LOPEZ SUR M 0 1 0 0 1

4 MARTIN SUR Null 0 0 0 0 1

5 BROWN CENTRO F 1 0 0 1 0

6 CANEPA NORTE M 0 1 1 0 0

El DBA

Concurrencia

Diccionario Datos

Integridad

Seguridad

Proc. Consultas


El SMBD

Manejo de Memoria

Restauración


Marzo 2012

• Cuando usar índices bitmaps– Tablas muy grandes (millones de registros)

– Con columnas que tienen baja cardinalidad (pocos valores diferentes)

– Consulta con combinaciones de AND y OR en la clausula WHERE

– Las columnas clave de los índices son de solo lectura o se actualizan muy poco

Manejo de memoria

El DBA

Concurrencia

Diccionario Datos

Integridad

Seguridad

Proc. Consultas


El SMBD

Manejo de Memoria

Restauración


Marzo 2012

• Creación de índices en SQL– create <tipo_indice> index

<nombre_indice> on <nombre_relación> (<lista-atributos>)

– El tipo_indice depende del SMBD los más comunes son

• Hash• Bitmap• Unique

– Si no se indica el tipo del indice creado el del tipo árbol B+

Manejo de memoria

El DBA

Concurrencia

Diccionario Datos

Integridad

Seguridad

Proc. Consultas


El SMBD

Manejo de Memoria

Restauración


Marzo 2012

• Vías de acceso– Exploración: leer todos los registros del archivo.– Búsqueda con selección de igualdad: Localizar

las páginas donde están los registros y cargarlas en memoria principal

– Búsqueda por selección de rango: Igual al anterior

– Insertar un registro: Identificar la página donde se va a insertar el registro, leerla, modificarla y guardarla de nuevo.

– Borrar un registro: Buscar el registro a borrar y marcarlo como borrado.

– Actualizar un registro: Buscar el registro a actualizar, leer la página, modificarla y guardarla de nuevo

Manejo de memoria

abd tema1 parteii

Education