Post on 13-Jun-2015
description
Administración de Base de Datos
Manejo de memoria (Parte II)
Prof Mercy Ospina Torres mercy.ospinat@gmail.com
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
Administración de Base de Datos 3
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
Administración de Base de Datos 4
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
Administración de Base de Datos 5
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
Administración de Base de Datos 6
¿Qué es un
índice?
Título No pag
Marzo 2012
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
Administración de Base de Datos 7
El SMBD
Manejo de Memoria
Restauración
Organización indexada
• ¿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
Administración de Base de Datos 8
El SMBD
Manejo de Memoria
Restauración
Organización indexada
• 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
Administración de Base de Datos 9
El SMBD
Manejo de Memoria
Restauración
Organización indexada
• 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
Administración de Base de Datos 10
El SMBD
Manejo de Memoria
Restauración
Organización indexada
• 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
Administración de Base de Datos 11
Índice primario
Los títulos está en el mismo orden interno y son únicos dentro del
libro
Marzo 2012
Administración de Base de Datos 12
Índice Agrupado
Los nombres se agrupan
por letras, el índice tiene el mismo orden que la guía
Marzo 2012
Administración de Base de Datos 13
Í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
Administración de Base de Datos 14
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
Administración de Base de Datos 15
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
…..
12341657 345654325678587967847865
11122233
8762 . .
3…
Manejo de memoria
Archivo de datosArchivo índice
fb 8 registros por bloque
Marzo 2012
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
Administración de Base de Datos 16
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
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
…..
12341657 345654325678587967847865
11122233
8762 . .
3…
Manejo de memoria Archivo de datos
Marzo 2012
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
Administración de Base de Datos 17
El SMBD
Manejo de Memoria
Restauración
Organización secuencialIndexada
• Í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)
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
…... .
…
345658798762…
123
. .…
Manejo de memoria
Marzo 2012
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
Administración de Base de Datos 18
El SMBD
Manejo de Memoria
Restauración
Organización secuencialIndexada
• Í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
Archivo de datosArchivo índice
Marzo 2012
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
Administración de Base de Datos 19
El SMBD
Manejo de Memoria
Restauración
Organización secuencialIndexada
• 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
Administración de Base de Datos 20
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…
Archivo de datosArchivo índice
fb 8 registros por bloque
Marzo 2012
Manejo de memoria
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
Administración de Base de Datos 21
El SMBD
Manejo de Memoria
Restauración
Organización directa indexada
• Índice secundario (atributo no único)
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
AnaBeatrizJoseLuis…
Archivo de datos
Registros de tamaño variable
AnaBeatrizJoseLuis…
1, 241, 3, 41, 2, 3,4
Archivo índice
Marzo 2012
Manejo de memoria
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
Administración de Base de Datos 22
El SMBD
Manejo de Memoria
Restauración
Organización directa indexada
• Listas invertidas
N registro relativo
registro Apun-tador
123
6784 Ana Vasquez MT2432 Luis Ramirez DE3456 Jose Perdomo CO
4 (inicio)
59
45
1657 Ana Paredes CO6865 Luis Urbina CO
86
67
5678 Luis Perez MT8762 José León CO
102
8910
5879 Beatriz Martínez MT1235 José Castillo DE5555 Luis Ricardo DE
37null
AnaBeatrizJoseLuis…
AnaBeatrizJoseLuis…
141 1
Archivo de datosArchivo índice
Marzo 2012
Manejo de memoria
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
Administración de Base de Datos 23
El SMBD
Manejo de Memoria
Restauración
Organización indexada
• Indice multinivel
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 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
Administración de Base de Datos 24
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
Administración de Base de Datos 25
El SMBD
Manejo de Memoria
Restauración
Organización indexadaArboles B y B+
• 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
Administración de Base de Datos 26
El SMBD
Manejo de Memoria
Restauración
Organización indexadaArboles B y B+
• 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
Administración de Base de Datos 27
El SMBD
Manejo de Memoria
Restauración
Organización indexadaArboles B y B+
• 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
Administración de Base de Datos 28
El SMBD
Manejo de Memoria
Restauración
Organización indexadaArboles B y B+
• Á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
Administración de Base de Datos 29
El SMBD
Manejo de Memoria
Restauración
Organización indexadaArboles B y B+
• Á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
Administración de Base de Datos 30
El SMBD
Manejo de Memoria
Restauración
Organización indexadaArboles B y B+
• Á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
Administración de Base de Datos 31
El SMBD
Manejo de Memoria
Restauración
Organización indexadaArboles B y B+
• Á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
Administración de Base de Datos 32
El SMBD
Manejo de Memoria
Restauración
Organización indexadaArboles B y B+
• 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
Administración de Base de Datos 33
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
Administración de Base de Datos 34
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
Administración de Base de Datos 35
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
Administración de Base de Datos 36
El SMBD
Manejo de Memoria
Restauración
Organización indexada
• Í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
Administración de Base de Datos 37
El SMBD
Manejo de Memoria
Restauración
Organización indexada
• Í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
Administración de Base de Datos 38
El SMBD
Manejo de Memoria
Restauración
Organización indexada
• Í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
Administración de Base de Datos 39
El SMBD
Manejo de Memoria
Restauración
Organización indexada
• Í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
Administración de Base de Datos 40
El SMBD
Manejo de Memoria
Restauración
Organización indexada
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
Administración de Base de Datos 41
El SMBD
Manejo de Memoria
Restauración
Organización indexada
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
Administración de Base de Datos 42
El SMBD
Manejo de Memoria
Restauración
Organización indexada
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