clase 2(1)

Vista previa del material en texto

11/04/2011
1
Clase 2
Introducción a las Bases de Datos
Curso especial - Recursantes
1
Temario
 Índices 
 Arboles
2
11/04/2011
2
Búsqueda de datos - Indices
3
 Búsqueda de información: 
 debemos minimizar el número de accesos
 Secuencial
 Binaria
 Estructuras auxiliares
Búsqueda de datos - Indices
4
 Las últimas págs. de un libro suelen contener un índice (tabla 
que contiene una lista de temas y los nº de pág. donde pueden 
encontrarse) 
 El uso de un índice es mejor alternativa que buscar un tema a 
lo largo del libro en forma secuencial
11/04/2011
3
Búsqueda de datos - Indices
5
 Otro ejemplo: encontrar libros en una biblioteca (por autor, 
título o tema)
 Alternativa 1: disponer 3 copias de cada libro y 3 edificios de 
biblioteca separados. Edificio1: libros clasificados por autor, Edif 2: 
libros clasif por titulo, Edif 3: libros clasif por tema (absurdo)
 Alternativa 2: usar un catálogo de tarjetas. En realidad es un conjunto 
de 3 índices, cada uno tiene una campo clave distinto, pero todos 
tienen el mismo número de catálogo como campo de referencia.
 El uso de índices proporciona varios caminos de acceso a un 
archivo
Búsqueda de datos - Indices
6
 Índices: definiciones
 Herramienta para encontrar registros en un archivo. Consiste 
de un campo de llave (búsqueda) y un campo de referencia que 
indica donde encontrar el registro dentro del archivo de datos.
 Tabla que opera con un procedimiento que acepta información 
acerca de ciertos valores de atributos como entrada (llave), y 
provee como salida, información que permite la rápida 
localización del registro con esos atributos.
 Estructura de datos (clave, dirección) usada para decrementar 
el tiempo de acceso a un archivo.
11/04/2011
4
Búsqueda de datos - Indices
7
 Índice: equivale a índice temático de un libro
 (tema, #hoja)
 (clave, NRR/distancia en bytes)
 Estructura más simple es un árbol
 Característica fundamental
 Permite imponer orden en un archivo sin que realmente este se 
reacomode
 Varias posibilidades
 Una: tantas entradas como tenga el archivo de datos.
 Otra: que no esté completo
Búsqueda de datos - Indices
8
Dir. Reg. Cía Nº ID Título Compositores Artista
32 LON 2312 Romeo y Julieta Prokofiev Maazel
77 RCA 2626 Cuarteto en Do... Beethoven Julliard
132 WAR 23699 Touchstone Corea Corea
167 ANG 3795 Sinfonía Nº 9 Beethoven Giulini
211 COL 38358 Nebraska Springsteen Springsteen
256 DG 18807 Sinfonía Nº 9 Beethoven Karajan
300 MER 75016 Suite el Gallo... Rymsky-Korsakov Leinsdorf
353 COL 31809 Sinfonía Nº 9 Dvorak Bernstein
396 DG 139201 Concierto para Violín Beethoven Ferras
422 FF 245 Good News Sweet Honey in.. Sweet Honey in..
11/04/2011
5
Búsqueda de datos - Indices
9
 Llave primaria: cía grabadora + Nº de identificación de la cía 
 Unívoca. Forma canónica: cía en mayúsculas + Nº identificación
 No se puede hacer búsqueda binaria sobre el archivo ya que 
tiene reg. de long variable (no se puede usar en NRR como 
medio de acceso)
 Dos Archivos: índice y datos
 Se construye un índice: llave de 12 caracteres (alineada a izq. y 
completada con blancos) más un campo de referencia (dir. del 
primer byte del registro correspondiente)
 Estructura del índice: archivo ordenado de reg. de long fija (puede 
hacerse búsqueda binaria). 
 En memoria
 Más fácil de manejar que el arch. de datos
Búsqueda de datos - Indices
10
Llave Ref Dir. de registro Registro de Datos
ANG3795 167 32 LON¦2312¦Romeo y Julieta¦Prokofiev... 
COL31809 353 77 RCA¦2626¦Cuartetoen Do... 
COL38358 211 132 WAR¦23699¦Touchstone¦Corea...
DG139201 396 167 ANG¦3795¦Sinfonía Nº9¦Beethoven...
DG18807 256 211 COL¦38358¦Nebraska¦Springsteen...
FF245 442 256 DG¦18807¦Sinfornía Nº 9¦Beethoven...
LON2312 32 300 MER¦76016¦Suite El gallo de Oro¦Rimsky...
MER75016 300 353 COL¦31809¦Sinfornía Nº9¦Dvorak...
RCA2626 77 396 DG¦139201¦Concierto para violín¦Beethoven...
WAR23699 132 422 FF¦245¦Good News¦Sweet Honey in the....
11/04/2011
6
Búsqueda de datos - Indices
11
 Operaciones básicas en un archivo indizado
 Índice en memoria (búsqueda binaria + rápida, comparada con 
archivos clasificados)
 Crear los archivos (el indice y el arch. de datos se crean vacíos, 
solo con registro cabecera)
 Cargar el índice en memoria (se supone que cabe, ya que es lo 
suficientem. pequeño. Se almacena en un arreglo)
Búsqueda de datos - Indices
12
 Operaciones básicas en un archivo indizado
 Reescritura del archivo de índice
 Cambios: activar un flag en el reg. cabecera cuando cambia la copia del 
índice en memoria ppal. Todos los programas deberían revisar el flag 
antes de utilizarlo. Si se encuentra el flag activo, el prg sabrá que el 
índice no está actualizado
 Si un prg. detecta el índice desactualizado, debe acceder a un 
procedimiento para su reconstrucción
11/04/2011
7
Búsqueda de datos - Indices
13
 Agregar nuevos registros 
 Implica agregar al archivo de datos y al archivo de indices
 Archivo de datos: copiar al final (se debe saber el NRR (fija) o 
distancia en bytes (variable) para el índice)
 Índice ordenarse con cada nuevo elemento en forma canónica (en 
mem.), setear el flag anterior
 Eliminar un registro
 Arch. datos  Cualquier técnica de las vistas para reutilizar el espacio
 Arch. índices  se quita la entrada (ó se podría marcar como 
borrado).
Búsqueda de datos - Indices
14
 Actualización de registros
 Sin modificar la clave (que pasa con el índice?)
 Si el reg. no cambia de longitud, se almacena en la misma posición física, el 
índice “no se toca”.
 Si el reg. cambia de longitud (se agranda) y se reubica en el arch. de datos 
 se debe guardar la nueva posición inicial en el índice
 Modificando la clave (que sucede?)
 Se modifica el archivo de datos
 Se debe actualizar y reorganizar el archivo de índices 
 Cómo simplificar  Modificar = Eliminar + Agregar (ya vistos)
11/04/2011
8
Búsqueda de datos - Indices
15
 Índices grandes para entrar en memoria
 Acceso y mantenimiento del índice: almacén secundario 
 Ventajas
 Posibilita búsqueda binaria en un arch. con reg. de long. variable 
 La reorganización y mantenimiento es menos costoso que hacer estas 
tareas sobre el arch. de datos directamente (siguen siendo más 
pequeños que el arch. de datos) 
 Desventajas 
 # de desplazamientos (para búsqueda binaria en disco)
 Reacomodo del índice debido a la adición o borrado de reg.
Búsqueda de datos - Indices
16
 Índices grandes para entrar en memoria
 Soluciones
 Organización por Dispersión (hashing) (prioriza la velocidad de 
acceso)
 Uso de Árboles 
 Otra alternativa
 Niveles de índices (indices de indices): permiten almacenar índices 
más grandes 
11/04/2011
9
Búsqueda de datos - Indices
17
 Índices Secundarios
 No sería natural solicitar un dato por clave
 En su lugar se utiliza normalmente un campo mas fácil de 
recordar( ej: buscar una canción por su título o por su 
compositor) 
 Este campo es un campo que pertenece a una llave secundaria 
 El índice secundario relaciona la llave secundaria con la llave 
primaria
 Las claves secundarias se pueden repetir
 Acceso  1º por llave secundaria (se obtiene la clave primaria) 
y luego llave primaria (en índice primario)
Búsqueda de datos - Indices
18
 Índices selectivos
 Contienen llaves solo para una porción de los registros del 
archivo de datos que interesa acceder
 Ej. sólo contenga los títulos de música clásica
 Vemos solo un subconjunto de los registros del archivo
11/04/2011
10
Árboles
19
 Índices: problemas
 Indices grandes  memoria secundaria
 Acceso a memoria secundaria  lento
 Búsqueda binaria  demasiados desplazamientos
 En un índice de 1000 ítems se requieren 9.5 (aprox.) desplazamientos 
en promedio
 Costo de mantener índice ordenado
 Es necesario un método donde las reorganizaciones sean locales y no 
masivas
Arboles20
 Arbol: Estructura de datos que permiten localizar en 
forma más rápida información de un archivo. (usando esta 
estructura para los índices)
 Tipos de árboles
 Binarios
 AVL
 Multicamino
 Balanceado (B, B*, B+)
11/04/2011
11
Arboles
21
 Un árbol se caracteriza por estar formado por una serie 
de nodos conectados por una serie de aristas que 
verifican que:
 hay un único nodo raíz
 cada nodo, excepto la raíz, tiene un único padre
 hay un único camino (desde la raíz hasta cada nodo)
 Puede estar ordenado o no
Arboles: terminología básica
22
 Grado de un nodo: número de descendientes directos
 Grado del árbol: mayor grado de sus nodos
 Árbol binario: árbol de grado 2
 Cada nodo tiene a lo sumo dos descendientes directos
 Árbol multicamino: 
 Cada nodo puede tener n descendientes directos
 Lista= árbol degenerado de grado 1
11/04/2011
12
Arboles: terminología básica
23
 Profundidad de un nodo: número de predecesores
 Altura del árbol: profundidad máxima de cualquier nodo
A
B DC
G HE F
I J K
profundidad(A)=0
profundidad(H)=2
altura=3
24
Arboles: terminología básica
 Camino: existe un camino del nodo 
X al nodo Y, si existe una sucesión 
de nodos que permitan llegar desde 
X a Y. 
camino(A,K)={A,B,F,K}
camino(C,K)={}
A
B DC
G HE F
I J K
11/04/2011
13
25
Arboles: árbol binario
 Cada nodo es un registro de longitud fija
 Cómo se almacena ?
 Archivo con registros de longitud fija
 La información en el archivo no está físicamente ordenada
 Ver ejemplo del archivo para el árbol del slide anterior
 Costo de espacio (muchos campos vacios)
Arboles: árbol binario
26
 Insertar las claves LV NP MB
KF
SD
FB
CL
DEAX
HN
JD
FT
PA
RFNR
WS
YSTK
LV
NP
MB
11/04/2011
14
Arboles: árbol binario
27
 Arbol balanceado: la altura de la trayectoria más corta 
hacia una hoja no difiere de la altura de la trayectoria mas 
grande
 Inconveniente: los árboles binarios (como en el ejemplo) 
se desbalancean fácilmente  búsquedas más costosas 
(mayor cantidad de desplazamientos)
 Solución: reorganizar los nodos del árbol a medida que se 
reciben las claves. Resultado: Arboles AVL
Arboles
28
 Volviendo a los 2 problemas iniciales:
 La búsqueda binaria requiere demasiados desplazamientos
 Mantener un índice en orden es costoso
 Los árboles balanceados en altura proporcionan solución 
aceptable al segundo problema.
11/04/2011
15
Arboles Binarios paginados
29
 Desplazarse en memoria secundaria tiene un costo de 
tiempo relativamente alto
 Aunque, una vez en posición, leer o escribir un conjunto 
de bytes continuos es rápido
 La combinación de : desplazamiento lento + transferencia 
rápida  conduce a la idea de paginación
Arboles Binarios paginados
30
 Al dividir un arbol binario en págs y después almacenar 
c/pág en bloques de localidad contiguas en disco  se 
puede reducir el Nº de desplazamientos para cualquier 
búsqueda.
 Paginación  solución potencial al problema de 
búsqueda. 
11/04/2011
16
Arboles Binarios paginados
31
 Estrategia:
 Dividir el árbol binario en páginas
 Almacenar cada página en un bloque de direcciones contiguas 
en disco
 Ver ejemplo (posibilidad de acceder a 63 nodos con sólo 2 
accesos a disco)
 Dividir el árbol en páginas permite búsquedas más rápidas 
en almacenamiento secundario.
Arboles Binarios paginados
32
 Uso de páginas grandes:
 Cada acceso a una página requiere transmitir muchos datos, la 
mayoría no usados.
 Hay tiempo de transmisión adicional, pero se ahorran muchos 
desplazamientos que consumen más tiempo que las 
retransmisiones.
 Problemas:
 Cómo construirlo ?
 Cómo elegir la raiz ?
 Cómo mantenerlo balanceado ?
 La idea de agrupar claves en páginas es muy buena, pero no se 
ha encontrado forma de agrupar las claves correctamente
11/04/2011
17
Arboles Multicamino
33
 Árboles n-arios o Multicamino:
 Árbol en el que cualquier nodo puede tener cualquier número 
de hijos
 
 Árboles con grado  2
34
Arboles Multicamino
 Implementación 1
 Hijos como arreglo de referencias
 Desaprovecha memoria si el número de hijos es muy 
variable
 No puede usarse si el número de hijos es ilimitado
...
A
...
B
...
C
...
D
...
E
...
F
...
G
...
H
...
I
...
J
11/04/2011
18
Arboles B
35
 Hasta ahora, se han construido árboles desde la raiz hacia 
abajo.
 Problemas: 
 Elegir la raiz
 Mantenerlo balanceado
 Arboles B  construirlos hacia arriba a partir de la base. 
La raíz emerge con la construcción.
Arboles B
36
 Árboles B (balanceados)
 Son árboles multicamino con una construcción especial en 
forma ascendente que permite mantenerlo balanceado a bajo 
costo.
11/04/2011
19
37
Arboles B
 Propiedades de un árbol B de orden M:
 Orden: cant. máx. de punteros por nodo
 Cant. de punteros= cant. claves + 1
 Ningún nodo tiene más de M hijos
 C/nodo (menos raíz y los terminales) tienen como mínimo 
[M/2] hijos
 La raíz tiene como mínimo 2 hijos (o sino ninguno)
 Todos los nodos terminales a igual nivel
 Nodos no terminales con K hijos contienen K-1 claves.
 Los nodos terminales tienen:
 Minimo: [M/2]–1 claves
 Máximo: M–1 claves
 Formato del nodo
 Cada Ri-1 < Ri < Ri+1
PO R1 P1 R2 P2 R3 P3 R4 P4 R5 P5 Nro de registros
Arboles B
38
 Definición: nodo adyacente hermano
 Dos nodos son adyacentes hermanos si tienen el mismo padre 
y son apuntados por punteros adyacentes en el padre.
 Operaciones
 Búsqueda
 Borrado
 Creación e inserción
 modificación
11/04/2011
20
Arboles B
39
 Búsqueda de información
 Comienza desde el nodo raíz
 Busca la llave en el nodo
 Sino la localiza se toma el puntero correspondiente entre las claves 
existentes 
 Si no es puntero nulo se toma ese nodo y se repite desde principio. Si 
es un puntero nulo el elemento no se encuentra en el árbol.
 Ver ejemplos 
Arboles B
40
 Performance (búsqueda)
 Orden M, # de nodos terminales N, N+1 punteros nulos.
 Accesos:
 Mejor caso: 1 lectura 
 Pero caso: h lecturas (con h altura del árbol)
 Como acotamos h
 Nivel # mínimo de descendientes
 1 2
 2 2 * [M/2]
 3 2 * [M/2] * [M/2]
 ………………………………………………….
 h 2 * [M/2]h-1
11/04/2011
21
Arboles B
41
 Relacion entre h (cant. niveles), N (cant. de claves), y M (orden)
 N+1 >= 2 * [M/2]h-1
 h <= 1 + log[M/2] ((N+1)/2)
 M = 512 y N = 1.000.000
 h <= 3,37 (4 lecturas encuentra un registro)
Arboles B
42
 Inserción (creación)
 Comienza con una búsqueda que llega hasta el nivel hoja
 Después de encontrar lugar de inserción en el nivel hoja, el 
trabajo de inserción, división y promoción continúa en forma 
ascendente desde abajo
11/04/2011
22
Arboles B
43
 Inserción (creación)
 Los registros se insertan en un nodo terminal
 Casos posibles
 El registro tiene lugar en el nodo terminal (no se produce overflow): 
solo se hacen reacomodamientos internos en el nodo
 El registro no tiene lugar en el nodo terminal (se produce overflow): 
el nodo se divide y los elementos se reparten entre los nodos, hay 
una promoción al nivel superior, y esta puede propagarse y generar 
una nueva raíz.
 Ver ejemplos
Arboles B
44
 Performance (inserción)
 Mejor caso (sin overflow)
 H lecturas
 1 escritura
 Peor caso (overflow hasta la raíz, aumenta en uno el nivel del 
árbol)
 H lecturas
 2h+1 escrituras (dos por nivel más la raíz)
 Estudios realizados
 M = 10 25% divisiones
 M = 100 2% divisiones
11/04/2011
23
Arboles B
45
 Eliminación
 Mejor caso: borra un elemento del nodo y no produce underflow, 
solo reacomodos ( cant claves >= [M/2]-1)
 Peor caso: se produce underflow, (cant claves < [M/2] – 1)
 Eliminar
 Nodo terminal Caso 1
 Nodo no terminal (llevar a un nodo terminal) Caso 2
 Dossoluciones
 Redistribuir Caso 3
 Concatenar Caso 4
Arboles B
46
 Redistribuir
 Cuando un nodo tiene underflow puede trasladarse claves de un 
nodo adyacente hermano (en caso que este tenga suficientes 
elementos)
 Concatenación
 Si un nodo adyacente hermano está al minimo (no le sobra 
ningún elemento, no se puede redistribuir), se concatena con 
un nodo adyacente disminuyendo el # de nodos (y en algunos 
casos la altura del árbol)
11/04/2011
24
Arboles B
47
 Performance (Borrado)
 Mejor caso (borra de un nodo terminal)
 h lecturas
 1 escritura (escribir el nodo sin el elem. borrado)
 Peor caso (concatenación lleva a decrementar el nivel del árbol 
en 1)
 2h – 1 lecturas
 H + 1 escrituras
48
Arboles B
 Inserción Vs Eliminación
División concatenación
? Redistribución
 la redistribución podría posponer la creación de páginas 
nuevas
 se pueden generar árboles B más eficientes en términos 
de utilización de espacio
11/04/2011
25
Arboles B*
49
 Arbol B especial en el que cada nodo está lleno por lo 
menos en 2/3 partes (excepto la raiz)
 Propiedades (orden M)
 Cada página o nodo tiene máximo M descendientes
 Cada página o nodo, menos la raíz y las hojas, tienen al menos [(2M –
1) / 3] descendientes
 La raíz tiene al menos dos descendientes (o ninguno)
 Todas las hojas aparecen en igual nivel
 Una página o nodo que no sea hoja si tiene K descendientes contiene 
K-1 llaves
 Una página o nodo hoja contiene por lo menos [(2M – 1) / 3] llaves, y 
no más de M-1.
Arboles B*
50
 Operaciones
 Búsqueda:
 Igual que el arbol B común
 Inserción: (Division + Redistribución) -> ver ejemplo
 Tres casos posibles
 Derecha
 Izquierda o derecha
 Izquierda y derecha
 Derecha: redistribuir con nodo adyacente hermano de la derecha (o izq. 
si es el último)
 Izquierda o derecha: si el nodo de la derecha está lleno y no se puede 
redistribuir, se busca el de la izquierda.
 Izquierda y derecha: busca llenar los tres nodos, estos tendrán un 2/3 
parte llena.
 Borrado: similar a árbol B (concatenación, redistribución)
11/04/2011
26
Arboles B*
51
 Manejo de páginas o nodos en Buffers 
 Objetivo: minimizar cantidad de accesos a disco
 Transferir el nodo raiz a RAM ahorra 1 acceso a mem. 
secundaria
 Almacenar la raiz y los nodos solicitados en un buffer de 
nodos en RAM ahorra más accesos a mem. secundaria
52
Arboles B*
 Manejo de páginas o nodos en Buffers 
 Técnicas de paginado 
 estrategias de reemplazo: LRU (least recently used)
# claves = 2400 # páginas = 140 Altura del árbol= 3 niveles
cant págs. en Buffer 1 5 10 20
cant acceso prom. por búsqueda 3.00 1.71 1.42 0.97
11/04/2011
27
Arboles B+
53
 Archivos secuenciales indizados
 Indizado (ordenado por una llave)
 Secuencial (acceder secuencialmente al archivo, devolviendo los 
registros en orden de llave)
 Permiten una mejor recorrida por algún tipo de orden
 Hasta ahora métodos disjuntos, se opta:
 rápida recuperación (árbol)
 Recuperación ordenada (secuencial)
 Debemos encontrar una solución que agrupe ambos casos
54
Arboles B+
 Los árboles B+ constituyen otra mejora sobre los 
árboles B.
• Conservan la propiedad de acceso aleatorio rápido 
(de los árboles B), es decir indizado, permitiendo 
además un recorrido secuencial rápido
11/04/2011
28
55
Arboles B+
Este árbol esta compuesto por dos partes:
 Índice: nodos interiores
 Secuencia: paginas hojas enlazadas secuencialmente 
en las que se repiten las claves anteriores 
56
Arboles B+
11/04/2011
29
Arboles B+
57
 Todas las claves se encuentran en las hojas (duplicándose 
en la raíz y nodos interiores, aquellas necesarias para 
definir los caminos de búsqueda)
 Las hojas están vinculadas, obteniéndose de ese modo 
una trayectoria secuencial para recorrer las claves del 
árbol
Arboles B+
58
 Ocupan más espacio que los árboles B (ya que algunas 
claves se encuentran más de una vez en el árbol)
 Las claves de la página raiz e interiores se utilizan 
únicamente como índice (para búsqueda)
11/04/2011
30
Arboles B+
59
 Propiedades
 Cada página tiene máximo M descendientes
 Cada página, menos la raíz y las hojas, tienen entre [M/2] y M hijos
 La raíz tiene al menos dos descendientes (o ninguno)
 Todas las hojas aparecen en igual nivel
 Una página que no sea hoja si tiene K descendientes contiene K-1 
llaves
 Los nodos terminales representan un conjunto de datos y son 
linkeados juntos.
 Los nodos no terminales no tienen datos sino punteros a los 
datos.
Arboles B+
60
 Operaciones clásicas
 Búsqueda: la búsqueda no debe detenerse cuando se encuentre 
la clave en la raiz o nodo interior, sino que debe seguir en la 
pág. apuntada por la rama derecha de dicha clave
11/04/2011
31
Arboles B+
61
 Operaciones clásicas
 Inserción:
 El proceso de inserción es similar a de los árboles B, excepto cuando 
se desea insertar una clave en donde la página se encuentra llena. 
 Cuando se inserta una nueva clave en una nueva página llena, esta se 
divide también en otras dos, pero ahora la primera contendrá m/2 
claves y la segunda 1+m/2 y lo que subirá al padre será una copia de la 
clave central
62
Arboles B+
 Inserción clave 13 (M=5)
11/04/2011
32
Arboles B+
63
 Operaciones clásicas
 Eliminación
 Este proceso es más simple que en los árboles B, porque todas las 
claves se encuentran en las páginas hojas. 
 Si al eliminar la clave (siempre en una hoja) la cant. de claves >= m/2, 
el proceso ha terminado 
 Las claves de la raiz o nodos internos no se modifican pues siguen siendo 
un separador válido entre las claves de las páginas descendientes
 Si al eliminar la clave (siempre en una hoja) la cant. de claves < m/2, es 
necesario una fusión y redistribución de las mismas, en las hojas y el 
índice
Arboles B+
64
 Separadores
 Derivados de las llaves de los registros que limitan un bloque en el 
conjunto de secuencia
 Separadores más cortos, ocupan espacio mínimo
 Árbol B+ de prefijos simples
 Árbol B+ en el cual el conjunto índice está constituido por 
separadores más cortos
11/04/2011
33
Arboles Balanceados 
65
 Comparaciones
Arbol B Arbol B+
Ubicación de datos
Nodos 
(cualquiera)
Nodo 
terminal
Tiempo de búsqueda = =
Procesamiento 
secuencial
Lento (complejo)
Rápido (con 
punteros)
Inserción eliminación Ya discutida
Puede requerir + 
tiempo