UNPA

1

1Bases de Datos – Analista de Sistemas – Unidad Académica Río GallegosBases de Datos – Analista de Sistemas – Unidad Académica Río Gallegos

Docente:

Albert A. Osiris Sofía 1º Cuatrimestre 2002

2Bases de Datos – Analista de Sistemas – Unidad Académica Río GallegosBases de Datos – Analista de Sistemas – Unidad Académica Río Gallegos

Indexación y

Asociación

3Bases de Datos – Analista de Sistemas – Unidad Académica Río GallegosBases de Datos – Analista de Sistemas – Unidad Académica Río Gallegos

Archivos Indice

• Conceptos Básicos• Indices Ordenados• Arboles• Asociación

UNPA

2

4Bases de Datos – Analista de Sistemas – Unidad Académica Río GallegosBases de Datos – Analista de Sistemas – Unidad Académica Río Gallegos

Archivos Indice

Ordenados Asociativos

Primario Secundario

Denso Disperso Multinivel

Arboles

B+ B

Estática Dinámica

5Bases de Datos – Analista de Sistemas – Unidad Académica Río GallegosBases de Datos – Analista de Sistemas – Unidad Académica Río Gallegos

Conceptos Básicos

6Bases de Datos – Analista de Sistemas – Unidad Académica Río GallegosBases de Datos – Analista de Sistemas – Unidad Académica Río Gallegos

Conceptos Básicos• Indices: permiten acceder en forma más

rápida y eficiente a los registros buscados.• Muchas técnicas de ordenación y

asociación. Adecuado de acuerdo a:– Tipo de acceso (que permite hacer)– Tiempo de acceso (busqueda)– Tiempo de inserción (lugar + estructura)– Tiempo de borrado (registro + estructura)– Espacio adicional requerido (archivo)

• Clave de búsqueda <> Clave primaria

UNPA

3

7Bases de Datos – Analista de Sistemas – Unidad Académica Río GallegosBases de Datos – Analista de Sistemas – Unidad Académica Río Gallegos

Conceptos Básicos• Los índices o indicadores se utilizan para acelerar

la búsqueda de registros en archivos.• El archivo de índices es mucho más pequeño que

el archivo original.• Toda superclave sirve para construir un archivo de

índices:4clave4puntero

• Sobre un archivo de datos se pueden construirvarios índices simultáneamente.

• Tipos básicos de archivos de índices:4índices ordenados4acceso directo (hash)

8Bases de Datos – Analista de Sistemas – Unidad Académica Río GallegosBases de Datos – Analista de Sistemas – Unidad Académica Río Gallegos

Indices Ordenados

9Bases de Datos – Analista de Sistemas – Unidad Académica Río GallegosBases de Datos – Analista de Sistemas – Unidad Académica Río Gallegos

Indices Ordenados

• Archivo ordenado secuencialmente por alguna clave (suele ser la clave primaria).

• Si es la clave primaria Indice Primario• INDICE DENSO: un registro en el archivo

índice para cada clave de búsqueda de la BDD

• INDICE DISPERSO: ídem perso sólo para un subconjunto de las claves de búqueda.

UNPA

4

10Bases de Datos – Analista de Sistemas – Unidad Académica Río GallegosBases de Datos – Analista de Sistemas – Unidad Académica Río Gallegos

Indice Denso

11Bases de Datos – Analista de Sistemas – Unidad Académica Río GallegosBases de Datos – Analista de Sistemas – Unidad Académica Río Gallegos

Indices Disperso

12Bases de Datos – Analista de Sistemas – Unidad Académica Río GallegosBases de Datos – Analista de Sistemas – Unidad Académica Río Gallegos

Indices Multinivel• Si el indice primario no se puede mantener en

memoria, el acceso es muy costoso• Para reducir el número de accesos a disco se

puede construir un índice disperso sobre el índice inicial– Indice externo: indice disperso del indice primario– Indice interno: archivo de indice primario

• Si todavía el índice externo es demasiado grande, se puede crear un índice adicional

• En inserción y borrado se deben revisar los índices a todos los niveles

UNPA

5

13Bases de Datos – Analista de Sistemas – Unidad Académica Río GallegosBases de Datos – Analista de Sistemas – Unidad Académica Río Gallegos

Indice Multinivel

14Bases de Datos – Analista de Sistemas – Unidad Académica Río GallegosBases de Datos – Analista de Sistemas – Unidad Académica Río Gallegos

Inserción y Borrado• Los algoritmos se aplican por igual a todos los

niveles• Borrado4Si es un índice denso

• se elimina en la tabla de índices y en el archivo4Si es un índice disperso

• Si está en la tabla de índices como en el denso• Si no, solo se borra del archivo

• Inserción4Si es denso

• se añade en la tabla de índices y en el archivo4Si es disperso

• Se añade en el índice si es comienzo de bloque

15Bases de Datos – Analista de Sistemas – Unidad Académica Río GallegosBases de Datos – Analista de Sistemas – Unidad Académica Río Gallegos

Indice Secundario• Construcción de índices basados en claves

que no son la clave primaria.• Tienen que ser índices densos4el archivo de datos no está ordenado por la

clave secundaria.• Cuando se modifica la BD hay que modificar

todos los índices.• La búsqueda secuencial en un índice

secundario no es muy eficiente.

UNPA

6

16Bases de Datos – Analista de Sistemas – Unidad Académica Río GallegosBases de Datos – Analista de Sistemas – Unidad Académica Río Gallegos

Indice Secundario Disperso

17Bases de Datos – Analista de Sistemas – Unidad Académica Río GallegosBases de Datos – Analista de Sistemas – Unidad Académica Río Gallegos

Arboles

18Bases de Datos – Analista de Sistemas – Unidad Académica Río GallegosBases de Datos – Analista de Sistemas – Unidad Académica Río Gallegos

Arboles B+• Los archivos de índices secuenciales se

degradan cuando crece el archivo4aparecen muchos bloques de desbordamiento4hay que reorganizar el archivo periódicamente.

• El árbol B+ se reorganiza automáticamentecon pequeños cambios al realizar lasmodificaciones.

• No necesita reorganización periódica.• La desventaja es que consume más espacio• Como el espacio es barato se utiliza mucho.

UNPA

7

19Bases de Datos – Analista de Sistemas – Unidad Académica Río GallegosBases de Datos – Analista de Sistemas – Unidad Académica Río Gallegos

Arboles B+• Es un árbol que cumple ciertas propiedades• Todos los caminos desde la raíz a las hojas

tienen la misma longitud• Cada nodo que no es raíz ni hoja tiene entre

n/2 y n hijos (n es fijo en cada árbol)• Cada hoja tiene entre (n-1)/2 y n-1 valores• Casos especiales:4Si la raíz no es hoja, tiene al menos 2 hijos4Si la raíz es hoja tiene entre 0 y n-1 valores

20Bases de Datos – Analista de Sistemas – Unidad Académica Río GallegosBases de Datos – Analista de Sistemas – Unidad Académica Río Gallegos

Ejemplo (n=5)

21Bases de Datos – Analista de Sistemas – Unidad Académica Río GallegosBases de Datos – Analista de Sistemas – Unidad Académica Río Gallegos

Ejemplo (n=3)

UNPA

8

22Bases de Datos – Analista de Sistemas – Unidad Académica Río GallegosBases de Datos – Analista de Sistemas – Unidad Académica Río Gallegos

Observaciones• Como las conexiones entre nodos se hacen

con punteros, no hay seguridad de que losnodos lógicamente agrupados lo esténfísicamente.

• Los niveles que no son raíz forman unajerarquía de índices dispersos.

• Un árbol B contiene un número pequeño deniveles (logaritmo el tamaño del archivo)

• Operaciones4búsqueda eficiente4inserción y borrado eficientes

23Bases de Datos – Analista de Sistemas – Unidad Académica Río GallegosBases de Datos – Analista de Sistemas – Unidad Académica Río Gallegos

Búsqueda en un árbol B+• Empezar en el nodo raíz4Buscar la clave mas pequeña que sea mayor de

la buscada4Si existe el valor acceder al hijo4Si no existe, acceder al anterior

• Si el nodo accedido no es una hoja, repetir elprocedimiento anterior

• Si el nodo accedido es una hoja, buscar laclave en ese nodo y seguir su puntero.4Si la clave no aparece es que no está

24Bases de Datos – Analista de Sistemas – Unidad Académica Río GallegosBases de Datos – Analista de Sistemas – Unidad Académica Río Gallegos

Proceso de búsquedas• Siempre se atraviesa el árbol desde la raíz a una

hoja.• El camino de búsqueda nunca es mas de4 log n/2 (K)4n número de claves por nodo4K claves

• Un nodo suele ser del tamaño de un bloque de disco (4KB) y n 100 (40 B por índice)4con 1 millón de claves y n=1004solo se accede a 4 nodos en la búsqueda

• En un árbol binario balanceado serían 20 nodos4mucho tiempo (30 milisegundos por acceso)

UNPA

9

25Bases de Datos – Analista de Sistemas – Unidad Académica Río GallegosBases de Datos – Analista de Sistemas – Unidad Académica Río Gallegos

Inserción en árbol B+• Buscar el nodo hoja en el que debe aparecer

el nuevo registro• si la clave ya existe en el nodo hoja4añadir el registro al archivo4encadenarlo con los otros registros de igual

clave• si la clave no está4añadir el registro al archivo4añadir la clave al archivo de índices

• si hay sitio en el nodo hoja, meterlo• si no hay sitio, dividir el nodo hoja y reajustar índices

26Bases de Datos – Analista de Sistemas – Unidad Académica Río GallegosBases de Datos – Analista de Sistemas – Unidad Académica Río Gallegos

Dividir nodos• Tomar los pares puntero-nodo incluido el nuevo4poner los n/2 primeros en el nodo original4poner el resto en un nuevo nodo

• Formar la pareja4(clave-pequeña-nuevo-nodo, puntero-nuevo-nodo)

• Meter la nueva pareja en el nodo padre4si es padre se llena repetir el procedimiento.

• La división de nodos se hace de abajo-arriba hasta que se encuentra un nodo vacío.4En el caso peor hay que crear una nueva raíz

27Bases de Datos – Analista de Sistemas – Unidad Académica Río GallegosBases de Datos – Analista de Sistemas – Unidad Académica Río Gallegos

Ejemplo (Dario)

UNPA

10

28Bases de Datos – Analista de Sistemas – Unidad Académica Río GallegosBases de Datos – Analista de Sistemas – Unidad Académica Río Gallegos

Borrado en árbol B+ • Encontrar el registro y eliminarlo del archivo

principal• Eliminar el par (clave,puntero) del nodo hoja4si no hay otro registro con esa misma clave

• Si el nodo se queda con pocas entradas después del borrado y se pueden acomodar en otro nodo4meter todas las claves de los dos nodos en uno,

borrando el nodo sobrante4Borrar la pareja (clave, puntero) de su padre y aplicar de

nuevo el algoritmo recursivamente.• Si el nodo raíz se queda solo con un puntero, se borra y el hijo se

convierte en raíz.

29Bases de Datos – Analista de Sistemas – Unidad Académica Río GallegosBases de Datos – Analista de Sistemas – Unidad Académica Río Gallegos

Ejemplo (luis)

30Bases de Datos – Analista de Sistemas – Unidad Académica Río GallegosBases de Datos – Analista de Sistemas – Unidad Académica Río Gallegos

Archivo de datos en el árbol B+ • La degradación de los archivos de índices se

resuelve con índices como árboles B+.• La degradación del archivo de datos se resuelve

con un archivo como árbol B+.• Las hojas del árbol almacenan registros en vez de

punteros.• Como los registros son mayores que los punteros,

se pueden almacenar menos registros por nodo.• La inserción y el borrado se realizan igual.• Como antes los nodos hoja están rellenos a la

mitad.• Para ganar espacio se admiten 2n/3 registros por

nodo (se consideran 3 nodos en las inserciones).

UNPA

11

31Bases de Datos – Analista de Sistemas – Unidad Académica Río GallegosBases de Datos – Analista de Sistemas – Unidad Académica Río Gallegos

Asociación

32Bases de Datos – Analista de Sistemas – Unidad Académica Río GallegosBases de Datos – Analista de Sistemas – Unidad Académica Río Gallegos

Acceso directo (hash)• Los archivos de índices obligan a leer de disco para

encontrar un registro a partir de su clave.• El acceso directo permite eliminar los archivos de

índices.• La técnica hash consiste en obtener la posición de

un registro a partir de su clave4posicion = F(clave)

• El acceso es inmediato con solo aplicar la fórmula hash

• Para que el archivo tenga un tamaño realista, el número de posiciones es mucho menor que el número de claves

• El problema es resolver la colisión de claves.

33Bases de Datos – Analista de Sistemas – Unidad Académica Río GallegosBases de Datos – Analista de Sistemas – Unidad Académica Río Gallegos

Función hash

UNPA

12

34Bases de Datos – Analista de Sistemas – Unidad Académica Río GallegosBases de Datos – Analista de Sistemas – Unidad Académica Río Gallegos

Función hash• El caso peor es que todas las claves usadas

coincidan en la misma posición4el tiempo de búsqueda es proporcional al número de

claves• El caso ideal es tantos registros como datos y todas

las claves trasformadas en registros distintos.• La función hash convierte la clave en un código

numérico para usarlo como parámetro4suma de todos los caracteres de la clave

• También se puede usar para archivos de índices

35Bases de Datos – Analista de Sistemas – Unidad Académica Río GallegosBases de Datos – Analista de Sistemas – Unidad Académica Río Gallegos

Bloques de registros• La función hash transforma la clave en la

dirección de un bloque.• Un bloque es una unidad de almacenamiento

que contiene uno o mas registros.• Puede tener el tamaño de un bloque de

disco.• Un bloque almacena todos los registros que

colisionan.• La búsqueda de un registro dentro de un

bloque es secuencial.

36Bases de Datos – Analista de Sistemas – Unidad Académica Río GallegosBases de Datos – Analista de Sistemas – Unidad Académica Río Gallegos

Ej. Dimensionado del archivo• No queda ningún bloque libre4se elige como mínimo un tamaño4nB > nr / fr

• nB es el número de bloques• nr número total de registros• fr número de registros por bloque

• Hay demasiadas colisiones en un bloque4se reduce si se aumenta el tamaño del archivo4nB > (nr / fr) * (1 + d)

• d es un factor de aumento ~ 20%4A pesar de todo se produce desbordamiento

UNPA

13

37Bases de Datos – Analista de Sistemas – Unidad Académica Río GallegosBases de Datos – Analista de Sistemas – Unidad Académica Río Gallegos

Resolución de colisiones• Hashing cerrado4el archivo aumenta con las colisiones.4se crea un nuevo bloque y el primero se enlaza con el4es el más utilizado en bases de datos

• Hashing abierto4el archivo no aumenta con las colisiones.4registros siguientes vacíos4área de desbordamiento4función de rehash

• Lo peor es que una vez elegido el sistema no se puede cambiar

38Bases de Datos – Analista de Sistemas – Unidad Académica Río GallegosBases de Datos – Analista de Sistemas – Unidad Académica Río Gallegos

Índices basados en hash• El Hash se utilizar para organizar archivos de

índices.• Los índices hash son siempre índices

secundarios4un archivo basado en hash ya tiene un índice

primario (la clave de acceso)

39Bases de Datos – Analista de Sistemas – Unidad Académica Río GallegosBases de Datos – Analista de Sistemas – Unidad Académica Río Gallegos

Ejemplo

UNPA

14

40Bases de Datos – Analista de Sistemas – Unidad Académica Río GallegosBases de Datos – Analista de Sistemas – Unidad Académica Río Gallegos

Problemas del hash estático• Es difícil a priori fijar el número de bloques de

un archivo de datos4si la BD es mucho mayor que el tamaño previsto

se degrada mucho el sistema4si se opta por un tamaño muy grande y luego no

se usa, se pierde mucho espacio.4redefinir la función cada vez que aumenta el

archivo es una tarea muy costosa• La solución es aplicar técnicas que permitan

modificar dinámicamente el número debloques.

41Bases de Datos – Analista de Sistemas – Unidad Académica Río GallegosBases de Datos – Analista de Sistemas – Unidad Académica Río Gallegos

Hashing dinámico• El hashing extensible permite adaptar la función de

hashing dinámicamente con el tamaño del archivo4tanto si aumenta como si disminuye

• La función hash genera valores en un rango muy grande (32 bits)

• En cada momento se usa solo un prefijo paraacceder a la tabla de bloques (0 < i < 32)4i aumenta o disminuye en función del nº de registros

• El número de bloques también aumenta ydisminuye (< 2i)

42Bases de Datos – Analista de Sistemas – Unidad Académica Río GallegosBases de Datos – Analista de Sistemas – Unidad Académica Río Gallegos

Comparación entre métodos• Costo de la reorganización periódica• Relación de inserciones y borrados frente a

búsquedas• Elegir entre optimizar el tiempo de acceso

medio y el tiempo de acceso en el caso peor• El acceso directo suele ser mejor cuando se

buscan registros aislados• Los índices ordenados se comportan mejor

cuando se hacen peticiones sobre rangos declaves.

UNPA

15

43Bases de Datos – Analista de Sistemas – Unidad Académica Río GallegosBases de Datos – Analista de Sistemas – Unidad Académica Río Gallegos

Bases de Datos

Clase Nº 7