El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
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 2 Administración de Base de Datos
Manejo de memoria
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
El SMBD
Manejo de Memoria
Restauración
Organizaciones de Archivo Clase anterior
• Organización Secuencial
– Montículo
– Ordenada
• Organización Directa
– Técnicas Hash
– Manejo de Colisiones
Marzo 2012 3 Administración de Base de Datos
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 4 Administración de Base de Datos
Manejo de memoria
¿Qué es un
índice?
Título No pag
Marzo 2012 5 Administración de Base de Datos
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
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.
Datos Indice
Marzo 2012 6 Administración de Base de Datos
Manejo de memoria
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
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 7 Administración de Base de Datos
Manejo de memoria
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
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 8 Administración de Base de Datos
Manejo de memoria
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
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 9 Administración de Base de Datos
Manejo de memoria
Índice primario
Los títulos está en el
mismo orden interno y son únicos dentro
del libro
Marzo 2012 10 Administración de Base de Datos
Índice Agrupado
Los nombres se agrupan
por letras, el índice tiene el mismo orden que la guía
Marzo 2012 11 Administración de Base de Datos
Índice secundario
Las palabras están
ordenadas alfabéticamente
Indica las páginas donde se encuentra cada palabra
Marzo 2012 12 Administración de Base de Datos
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
El SMBD
Manejo de Memoria
Restauración
Organizaciones secuencial Indexada
• Índice primario
1234 Maria Castillo DE 1657 Ana Paredes CO 3456 Jose Perdomo CO
5432 Pedro López DE 5678 Luis Perez MT 5879 Beatriz Martínez MT
6784 Ana Vasquez MT 7865 Victor Trejo CO 8762 Julio León CO
…..
Manejo de memoria
Archivo de datos Archivo índice
fb 8 registros por bloque
Marzo 2012 13 Administración de Base de Datos
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
El SMBD
Manejo de Memoria
Restauración
Organizaciones secuencial Indexada
• Índice primario
1234 Maria Castillo DE 1657 Ana Paredes CO 3456 Jose Perdomo CO
5432 Pedro López DE 5678 Luis Perez MT 5879 Beatriz Martínez MT
6784 Ana Vasquez MT 7865 Victor Trejo CO 8762 Julio León CO
…..
1234 1657 3456 5432 5678 5879 6784 7865
1 1 1 2 2 2 3 3
8762 . .
3 …
Manejo de memoria
Archivo de datos Archivo índice
fb 8 registros por bloque
Marzo 2012 14 Administración de Base de Datos
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
El SMBD
Manejo de Memoria
Restauración
Organización secuencial Indexada
• Í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 DE 1657 Ana Paredes CO 3456 Jose Perdomo CO
5432 Pedro López DE 5678 Luis Perez MT 5879 Beatriz Martínez MT
6784 Ana Vasquez MT 7865 Victor Trejo CO 8762 Julio León CO
…..
1234 1657 3456 5432 5678 5879 6784 7865
1 1 1 2 2 2 3 3
8762 . .
3 …
Manejo de memoria Archivo de datos
Marzo 2012 15 Administración de Base de Datos
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
El SMBD
Manejo de Memoria
Restauración
Organización secuencial Indexada
• Í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 DE 1657 Ana Paredes CO 3456 Jose Perdomo CO
5432 Pedro López DE 5678 Luis Perez MT 5879 Beatriz Martínez MT
6784 Ana Vasquez MT 7865 Victor Trejo CO 8762 Julio León CO
…..
. . …
3456 5879 8762 …
1 2 3
. . …
Manejo de memoria
Marzo 2012 16 Administración de Base de Datos
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
El SMBD
Manejo de Memoria
Restauración
Organización secuencial Indexada
• Índice agrupado
1657 Ana Paredes CO 6784 Ana Vasquez MT 5879 Beatriz Martínez MT
3456 Jose Perdomo CO 8762 José León CO 1235 José Castillo DE
5678 Luis Perez MT 2432 Luis Ramirez DE 6865 Luis Urbina CO
5555 Luis Ricardo DE
Ana Beatriz Jose Luis
1 1 2 ?
. . …
Manejo de memoria
Archivo de datos Archivo índice
Marzo 2012 17 Administración de Base de Datos
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
El SMBD
Manejo de Memoria
Restauración
Organización secuencial Indexada
• 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 18 Administración de Base de Datos
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 MT 2432 Luis Ramirez DE 3456 Jose Perdomo CO
1657 Ana Paredes CO 6865 Luis Urbina CO
5678 Luis Perez MT 8762 José León CO
5879 Beatriz Martínez MT 1235 José Castillo DE 5555 Luis Ricardo DE
1235 1657 2432 3456 5555 5678 5879 6784 6865
4 2 1 1 4 2 4 1 2
6865 8762 . .
2 3 …
Archivo de datos Archivo índice
fb 8 registros por bloque
Marzo 2012 19 Administración de Base de Datos
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 (atributo no único)
6784 Ana Vasquez MT 2432 Luis Ramirez DE 3456 Jose Perdomo CO
1657 Ana Paredes CO 6865 Luis Urbina CO
5678 Luis Perez MT 8762 José León CO
5879 Beatriz Martínez MT 1235 José Castillo DE 5555 Luis Ricardo DE
Ana Beatriz Jose Luis …
Archivo de datos
Registros de tamaño variable
Ana Beatriz Jose Luis …
1, 2 4 1, 3, 4 1, 2, 3,4
Archivo índice
Marzo 2012 20 Administración de Base de Datos
Manejo de memoria
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
El SMBD
Manejo de Memoria
Restauración
Organización directa indexada
• Listas invertidas
N registro relativo
registro Apun-tador
1 2 3
6784 Ana Vasquez MT 2432 Luis Ramirez DE 3456 Jose Perdomo CO
4 (inicio)
5 9
4 5
1657 Ana Paredes CO 6865 Luis Urbina CO
8 6
6 7
5678 Luis Perez MT 8762 José León CO
10 2
8 9 10
5879 Beatriz Martínez MT 1235 José Castillo DE 5555 Luis Ricardo DE
3 7 null
Ana Beatriz Jose Luis …
Ana Beatriz Jose Luis …
1 4 1 1
Archivo de datos Archivo índice
Marzo 2012 21 Administración de Base de Datos
Manejo de memoria
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
El SMBD
Manejo de Memoria
Restauración
Organización indexada
• Indice multinivel
6784 Ana Vasquez MT 2432 Luis Ramirez DE 3456 Jose Perdomo CO
1657 Ana Paredes CO 6865 Luis Urbina CO
5678 Luis Perez MT 8762 José León CO
5879 Beatriz Martínez MT 1235 José Castillo DE 5555 Luis Ricardo DE
1235 1657 2432 3456 5555 5678 5879 6784
3 2 1 1 3 2 3 1
6865 8762 . .
2 3 …
6784 8762
1 2
Archivo de datos Archivo índice Nivel 1 (interno)
Archivo índice Nivel 2
Marzo 2012 22 Administración de Base de Datos
Manejo de memoria
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
El SMBD
Manejo de Memoria
Restauración
Organización indexada Arboles 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 23 Administración de Base de Datos
Manejo de memoria
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
El SMBD
Manejo de Memoria
Restauración
Organización indexada Arboles 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 24 Administración de Base de Datos
Manejo de memoria
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
El SMBD
Manejo de Memoria
Restauración
Organización indexada Arboles 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-P) +1 (P+K)
Marzo 2012 25 Administración de Base de Datos
Manejo de memoria
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
El SMBD
Manejo de Memoria
Restauración
Organización indexada Arboles 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 26 Administración de Base de Datos
Manejo de memoria
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
El SMBD
Manejo de Memoria
Restauración
Organización indexada Arboles 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 27 Administración de Base de Datos
Manejo de memoria
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
El SMBD
Manejo de Memoria
Restauración
Organización indexada Arboles B y B+
• Árbol B+
– Variación del Árbol B
– Solo las hojas apuntan a los datos
Marzo 2012 28 Administración de Base de Datos
Manejo de memoria
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
El SMBD
Manejo de Memoria
Restauración
Organización indexada Arboles 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 29 Administración de Base de Datos
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 borrado
1. 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 30 Administración de Base de Datos
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 31 Administración de Base de Datos
Manejo de memoria
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
El SMBD
Manejo de Memoria
Restauración
Próxima clase
Marzo 2012 Administración de Base de Datos 32
• Índices Bitmap
• Resumen vias 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
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 33 Administración de Base de Datos
Manejo de memoria
El DBA
Concurrencia
Diccionario Datos
Integridad
Seguridad
Proc. Consultas
El SMBD
Manejo de Memoria
Restauración
Organización indexada
• Índice Bitmap
– Indice bitmap sobre sexo
Marzo 2012 34 Administración de Base de Datos
Manejo de memoria Id Apellido Región Géne-
ro
Bitmaps
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
Organización indexada
• Índices Bitmap
– Índice bitmap sobre región
Marzo 2012 35 Administración de Base de Datos
Manejo de memoria
Id Apellido Región Géne-
ro
Bitmap
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
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 36 Administración de Base de Datos
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
Organización indexada
Marzo 2012 Administración de Base de Datos 37
• 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
Organización indexada
Marzo 2012 Administración de Base de Datos 38
• 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
Organización indexada
Marzo 2012 Administración de Base de Datos 39
• 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
Recommended