BASES DE DATOS II

Profesor Guillermo Baquerizo P.

BÚSQUEDA Y EXTRACCIÓN DE REGISTROSSi se examina un registro individual, es

conveniente identificarlo con una clave o llave respecto de los demás, la cual se basa en el contenido del registro.

Cuando se busca un registro se debe definir una forma estándar para el manejo de claves. A esta forma se le denomina forma canónica.

Una forma canónica para una clave es la representación única para esa clave que se ajusta a algún tipo de regla.

CONCEPTOS FUNDAMENTALES DE ESTRUCTURAS DE ARCHIVOS

BÚSQUEDA SECUENCIALUna medida de la eficiencia de este método

está basada en el número de comparaciones requeridas para realizar la búsqueda.

Si el registro está al inicio, sólo se necesitará un intento.

Si el registro está al final, se necesitarán n intentos, siendo n la cantidad de registros.

En promedio se necesitarán n/2 intentos hasta realizar la búsqueda secuencial.

CONCEPTOS FUNDAMENTALES DE ESTRUCTURAS DE ARCHIVOS

BÚSQUEDA BINARIALa restricción es que los registros deben estar

previamente ordenados.En cada nuevo intento se decide buscar en la

mitad del arreglo y así recursivamente.Si n es la cantidad de registros y ésta es igual a

1024Para la búsqueda secuencial se necesitarán 512

intentos en promedio.Para la búsqueda binaria se necesitará en el peor

de los casos un total de 10 iteraciones.

CONCEPTOS FUNDAMENTALES DE ESTRUCTURAS DE ARCHIVOS

BÚSQUEDA SECUENCIAL vs. BÚSQUEDA BINARIA

Mientras mayor sea el número de registros, la BS será más ineficiente que la BB.

La búsqueda secuencial tiene un orden O(n)La búsqueda binaria tiene un orden O(log 2 n)

CONCEPTOS FUNDAMENTALES DE ESTRUCTURAS DE ARCHIVOS

BÚSQUEDA SECUENCIAL MEJORADASi el dispositivo de almacenamiento es de

acceso directo se puede colocar al inicio del registro y leerlo.

El orden para este caso será O(1).Es necesario disponer del NRR (número

relativo de registro) para poder acceder directamente.

Para algunos lenguajes el NRR comienza en 0, el siguiente en 1 y así sucesivamente.

CONCEPTOS FUNDAMENTALES DE ESTRUCTURAS DE ARCHIVOS

SOBRECARGA POR DATOS USADOS PARA CONTROL

Suponga que se tiene una unidad de disco con referencia a direcciones por bloques con 20000 bytes por pista, y que la cantidad de espacio dedicada a los sub-bloques y los huecos entre bloques es equivalente a 300 bytes por bloque.

¿Cuántos registros pueden almacenarse por pista?a) Si el factor de bloque es 10b) Si el factor de bloque es 60

Dispositivos de almacenamiento DISCOS MAGNÉTICOS

SOBRECARGA POR DATOS USADOS PARA CONTROL

a)Si hay 10 registros de 100 bytes por bloque y cada bloque almacena 1000 bytes de datos y emplea 300 + 1000, o 1300 bytes de espacio de la pista, tomando en cuenta la sobrecarga de datos de control. El número de bloques que pueden entrar en una pista se puede expresar como:

20000/1300 = 15 De modo que se pueden almacenar 15 bloques, o 150

registros, por pista. (Nótese que se tiene que redondear hacia abajo el resultado, debido a que un bloque no puede distribuirse en 2 pistas).

Dispositivos de almacenamiento DISCOS MAGNÉTICOS

SOBRECARGA POR DATOS USADOS PARA CONTROL

b) Si hay 60 registros de 100 bytes por bloque y cada bloque almacena 6000 bytes de datos y emplea 300 + 6000, o 6300 bytes de espacio de la pista, tomando en cuenta la sobrecarga de datos de control. El número de bloques que pueden entrar en una pista se puede expresar como:

20000/6300 = 3 De modo que se pueden almacenar 3 bloques, o 180

registros, por pista. (Nótese que se tiene que redondear hacia abajo el resultado, debido a que un bloque no puede distribuirse en 2 pistas).

Dispositivos de almacenamiento DISCOS MAGNÉTICOS

SOBRECARGA POR DATOS USADOS PARA CONTROL

Está claro que un factor de bloque mayor puede dar paso a un uso más eficiente al almacenamiento. Cuando los bloques son grandes se requieren menos para contener un archivo, de tal forma que es menor el espacio consumido por los 300 bytes de sobrecarga que acompañan a cada bloque.

¿Se puede concluir de este ejemplo que los factores de bloque grandes siempre conducen a una utilización más eficiente del almacenamiento? No necesariamente, recuerde el problema de la fragmentación interna.

Dispositivos de almacenamiento DISCOS MAGNÉTICOS

COSTO DE ACCESO A UN DISCOLos factores que intervienen en la suma total del

tiempo necesario para acceder a un archivo que se encuentra en un disco fijo se puede dividir en 3 operaciones físicas distintas:Tiempo de desplazamiento: Considere que si las

posiciones de inicio y fin para cada acceso son aleatorias, el desplazamiento promedio atraviesa una tercera parte del número total de pistas

Retraso por rotaciónTiempo de transferencia

Dispositivos de almacenamiento DISCOS MAGNÉTICOS

COSTO DE ACCESO A UN DISCOTiempo de desplazamiento: Es el tiempo requerido

para mover el brazo de acceso hasta el cilindro adecuado. Depende de la distancia que tenga que recorrer el brazo. Si se accede en forma secuencial al archivo y éste está

comprimido en varios cilindros consecutivos, el desplazamiento se realiza sólo después de que todas las pistas del cilindro han sido procesadas, y aun así la cabeza de lectura/escritura necesitará moverse a lo ancho de una pista tan sólo.

Si por el contrario, se accede en forma aleatoria a sectores de 2 archivos que están almacenados en los extremos opuestos de un disco, el desplazamiento resulta muy caro.

Dispositivos de almacenamiento DISCOS MAGNÉTICOS

COSTO DE ACCESO A UN DISCOTiempo de desplazamiento: Implica varias operaciones

un tanto lentas. Entre las más importantes se consideran: El tiempo inicial de arranque (s) El tiempo que toma recorrer los cilindros que se deben cruzar

una vez que el brazo de acceso adquiere su velocidad normal. Si (n) indica el número de cilindros por atravesar, entonces

las contribuciones de esos 2 valores pueden aproximarse por medio de una función lineal de la forma:

f(n) = m*n + s donde m es una constante que depende de la unidad de

disco en cuestión.

Dispositivos de almacenamiento DISCOS MAGNÉTICOS

COSTO DE ACCESO A UN DISCOSuponga que 2 fabricantes le han proporcionado

las siguientes funciones asociadas a los tiempos de desplazamiento:f(n) = 0.3n + 20 [mseg]f(n) = 0.1n + 3 [mseg]

Se observa claramente quela segunda arranca más rápidoy atraviesa las pistas más velozmente.

Dispositivos de almacenamiento DISCOS MAGNÉTICOS

COSTO DE ACCESO A UN DISCORetraso por rotación: Se refiere al tiempo que

transcurre para que en el disco que gira el sector que se desea quede bajo la cabeza de lectura/escritura.Por lo general, los discos giran a una velocidad

aproximada de 3600 rpm, lo que significa una revolución cada 16.7 mseg.

En promedio, el retraso por rotación es la mitad de una revolución, o cerca de 8.3 mseg.

Dispositivos de almacenamiento DISCOS MAGNÉTICOS

COSTO DE ACCESO A UN DISCOTiempo de transferencia: Una vez que los datos

que se desean están bajo la cabeza de lectura/escritura, se pueden transferir. Viene dado por la expresión:F= (# de bytes por transferir)/(# de bytes por

pista)Tiempo de transferencia = F * Tiempo de rotación

Dispositivos de almacenamiento DISCOS MAGNÉTICOS

ORGANIZACIÓN DE DATOSNo se requieren direcciones para identificar la

ubicación de los datos porque el acceso en la cinta es secuencial.

La posición lógica de un byte dentro del archivo corresponde directamente con su posición física relativa al inicio del archivo.

Una cinta común puede tener 9 pistas y el último de ellos ser utilizado para la paridad.Paridad par: número par de unosParidad impar: número impar de unos

Dispositivos de almacenamiento CINTAS MAGNÉTICAS

ESTIMACIÓN DE REQUERIMIENTOS DE LONGITUD DE UNA CINTA

Sean los parámetros:b: Longitud física de un bloque de datosg: Longitud de un hueco entre bloquesn: Número de bloques de datos

El requerimiento de espacio (s) para almacenar el archivo es:

s = n*(b + g)

Dispositivos de almacenamiento CINTAS MAGNÉTICAS

ESTIMACIÓN DE TIEMPOS DE TRANSMISIÓNSean los parámetros:

Densidad de la cinta: Usualmente viene dada en bpi (bits por pulgada, por sus siglas en inglés)

Velocidad de la cinta: Usualmente viene dada en ips (pulgadas por segundo, por sus siglas en inglés)

Tamaño del hueco entre bloquesSe puede calcular:

Tasa nominal: en base a los datos del fabricanteTasa efectiva: en base a la densidad de grabado

efectiva

Dispositivos de almacenamiento CINTAS MAGNÉTICAS

ÍndicesUn índice para un archivo es como un

índice en un libro.

Es más pequeño que el libro.

Las palabras están en orden de búsqueda.

Si buscamos un tópico específico primero buscamos en el índice, encontramos las páginas y finalmente vamos a las páginas reales en el libro.

Definición formal de índices“Un índice se define para un atributo de

una relación. Se guarda para cada valor de este atributo las direcciones de todos los bloques que contienen tuplas con ese valor para dicho atributo.”

Un índice es una estructura de datos que facilita el proceso de respuesta a una consulta minimizando el número de accesos al disco.

Los valores en un índice se mantienen “con cierto orden” de modo que se puede buscar rápidamente.

Clasificación de los índicesEn base al número de datos relacionados

pueden ser:Densos y Escasos

En base al tipo de organización:Indices primarios eIndices secundarios

Indices densosExiste un registro de índice para cada

valor de la llave de búsqueda El registro contiene el valor de la llave y un puntero al registro.

Se accede directamente al elemento que se busca y a través del puntero recuperamos los datos asociados.

Indices escasosUna llave va asociada a un bloque de

información

Registros sólo para algunos valores claves.

Se busca en base al registro más cercano y luego se realiza la búsqueda secuencial.

Finalmente se recupera la información asociada al dato buscado.

Indices densos vs escasosBúsqueda en densos es más rápida que la

búsqueda en los escasos.

En dispersos se utiliza menos espacio para almacenamiento de índices y ventajas en inserciones y borrados

Compromiso del programador: equilibrio

Índices primariosSe basan principalmente en archivos

ordenados secuencialmente.

Se denomina índice primario cuando el archivo de datos asociado se encuentra ordenado en base a la llave de búsqueda.

Indices secundariosMantienen una organización externa

asociado a otros datos.

Permite hacer referencia a una misma estructura.

Un índice mantiene la llave de búsqueda y el otro índice la organización del archivo.

Indices secundarios (cont...)Crea un índice adicional que puede ser

seleccionado dependiendo del criterio de búsqueda utilizado.

Aceleran la búsqueda en base a campos que no sean la clave primaria, pero dificultan la actualización y el mantenimiento del índice agregando un tiempo adicional de procesamiento.

Buckets en índices secundariosSe busca reducir el número de lecturas

para las consultas.

El índice mantiene sólo un puntero correspondiente a cada llave apuntando hacia el bucket que contiene los punteros a todos los registros de búsqueda.

Se maneja como una estructura de bloques de información.

Mejora a los índicesSe emplea indexación de múltiples niveles:

Se realiza para evitar la lectura de múltiples segmentos de índice.

El índice externo se mantiene en memoria principal.

La búsqueda puede hacerse con menos acceso a memoria secundaria.

Se puede repetir el esquema en varios niveles.

Los índices en todos los niveles deben ser actualizados en la inserción o borrado de un registro en el archivo.

Indexación vs DispersiónPara consultas de recuperación de

información con un valor específico resulta mejor el uso de dispersión, pues no depende del tamaño del archivo.

Los índices pueden tomar un tiempo logarítmico con respecto al tamaño total de la BD.

Indexación vs dispersión (cont...)Para consultas de recorridos de rango

(desde un valor X hasta un valor Y), el índice tiene mejores resultados pues es fácil ubicar los puntos de partida y final.

El uso de dispersión falla al tener un rango muy grande pues debe calcular constantemente el valor de ubicación de la llave.

¿Cómo y cuando seleccionar un índice?Analizar las consultas más habituales, en

la práctica.

Determinar cuáles son las más costosas en cuanto a tiempo e identificar los atributos de la consulta.

Cuidado con la cantidad: muchos índices significan mucho tiempo adicional en inserciones y eliminaciones.

Evaluación de los índicesNo existe una técnica definida como la

mejor, todos los índices deben ser evaluados en base a estos criterios:Tipo de acceso.- encontrar un registro

específico con una llave particular o se utiliza un rango.

Tiempo de acceso.- El tiempo que requiere para encontrar un elemento específico. 

Tiempo de inserción.- El tiempo que se necesita para agregar un nuevo item al archivo de datos. Así como el tiempo de actualización del índice.

Evaluación de los índices (cont...)

Tiempo de eliminación.- El tiempo requerido para eliminar un registro, incluyendo el tiempo de búsqueda.

Espacio adicional.- Espacio extra requerido para el mantenimiento del índice.