Apuntes de CI-5313 Base de Datos III (USB-VE)/Estructuras de Almacenamiento Secundario

Manejadores de Bases de Datos

• Manejo de integridad: módulo que se encarga de garantizar que los datos almacenados en la BD satisfagan las propiedades estructurales y dinámicas que los describen.

• Máquina de ejecución: módulo encargado de evaluar las consultas en un lenguaje declarativo. Está constituido por:
  • Parser: encargado de hacer el chequeo semántico y traducir a las estructuras internas del MBD.
  • Optimizador de consultas: en base a estadísticas sobre los datos y propiedades de los operadores usados en la consulta se encarga de identificar planes de ejecución eficientes.
  • Evaluador de consultas: encargado de evaluar el plan identificado por el optimizador.

• Manejo de concurrencia: encargado de garantizar el acceso concurrente a los datos sea equivalente al acceso secuencial de los mismos.

• Manejador de recuperación:
• Manejador de seguridad:

Niveles de abstracción

Externo (vistas) → Lógico (Esquemas relacionales, objeto-relacionales < Esquema Físico)

Jerarquía de Memorias

• MEMORIA PRINCIPAL (RAM, DRAM) → costosa, volátil y limitada
• MEMORIA SECUNDARIA (DISCOS MAGNÉTICOS Y ÓPTICOS) → económica, no-volátil/persistente, no limitada
• MEMORIA TERCIARIA (CINTAS) → backup

Dispositivos de memoria secundaria

Definiciones:

1. Boque: colección de datos. Está identificado por plato, la pista y la posición dentro de la pista.
2. Registros: conjunto de campos que representan un ente almacenado. Los registros tienen identificadores que permiten al manejador de archivos determinar el bloque (bloques) donde se encuentra almacenado el mismo.
3. Factor de bloqueo: número de registros que pueden ser almacenados en un bloque.
4. Discos magnéticos: pista → sector → bloque Costo para leer/escribir.

• Seek time: tiempo requerido para que la cabeza lectora se posicione sobre la pista.
• Rotation time: tiempos requerido para que el plato de vuelta y se coloque debajo de la cabeza lectora. En promedio se considera que es la mitad del tiempo requerido para dar una vuelta completa.
• Transfer time: tiempo para transferir (leer o escribir) el bloque.

Tipos de bloques

1. Spaned (extensibles): para economizar el espacio de almacenamiento, un registro en diversos en diversos bloques. Enlazados por medio de apuntadores.
2. Unspanned (no extensibles): todos los registros almacenados en un bloque deben estar completos.

¿Cómo determinar el factor de bloqueo? Depende del tipo de bloque y el tipo de registro.

• Bloques no extensibles y registro de longitud fija:

B: tamaño del bloque en bytes

R: tamaño del registro en bytes

$FB=piso(B/R)$

• Bloque extensible y registro de tamaño fijo:

B: tamaño del bloque en bytes

R: tamaño del registro en bytes

$FB=B/R$

• Bolques no extensibles y registros de tamaño variable: no se puede calcular el tamaño de cada bloque, se calcula el FB promedio (FBp)...

R': tamaño promedio de los registros.

$FBp=piso(B/R')$

Tipos de Archivos

Se estudiará la eficiencia en operaciones como scan (recorrido del archivo), búsqueda por igualdad, búsqueda por rango, inserción, eliminación, actualización de algunos tipos de archivos:

1. Archivos Heap
2. Archivos Ordenados
3. Indexados (B+ Tree)
4. Hash

Leyenda de símbolos usados en los costos

B → número de bloques del archivo.

D → tiempo promedio para procesar un bloque.

R → número de registros por bloque.

C → tiempo para procesar un registro que no está en memoria principal.

Heap

Los registros están almacenados en la forma en que almacenados en la forma en que fueron almacenados en el sistema.

Inserción

Se recupera el último bloque del archivo y si hay espacio se inserta el registro en dicho bloque. En caso de que no exista espacio, se solicita un nuevo bloque el cual pasa a ser el último bloque del archivo.

• Bloques no extensibles:
  • Mejor caso: 2*D + C
  • Peor caso: 3*D

• Bloques extensibles: (K = 1 ó 2, K*B es el número de bloques necesarios para almacenar el registro)
  • Mejor caso: 2*D + C
  • Peor caso: 3*D + K*B * D

Inserción

Costo único: B(C+R*D)

Búsqueda por igualdad

• Peor Caso: B(D + R*C)
• Promedio: 0.5 * B * (D + R*C) → Atributos clave

Búsqueda por Rango

Costo: B (D + R*C)

Eliminación y Actualizaciòn

Son iguales debido a que se puede considerar que una eliminación es una actualización en la que se busca el bloque donde se encuentra el registro a eliminar y se marca como eliminado. Costo: Costo(Búsqueda) + R * (D+C)