FICHEROS Y BASES DE DATOS

 

 

                   TEMA 1   ASPECTOS BÁSICOS DE LOS FICHEROS

 

1.1   Jerarquía de memoria

 

            Memoria Primaria

 

- La primera idea es almacenar la información en el medio más rápido posible, para asegurar

  una rápida gestión.

- El coste de acceso a memoria primaria, o memoria RAM, es fijo y reducido.

- Pero la utilización de este tipo de memoria presenta diferentes problemas:

            - Suele ser un medio bastante caro, por lo que se suele limitar su capacidad.

            - La información se pierde al producirse un fallo de corriente eléctrica.

 

            Memoria Secundaria

 

- Estas limitaciones aconsejan, la utilización de la memoria secundaria.

- Sus propiedades son las siguientes:

            - Presenta un coste por byte mucho menor que la memoria RAM.

            - Preserva su contenido al producirse un fallo de corriente eléctrica.

            - Es bastante más lenta que la RAM y además el coste de acceso no es fijo.

 

            Definición de Ficheros

 

- La información en memoria secundaria se almacena en ficheros, que se define como una

  Colección de Información Relacionada.

- Debido al alto coste temporal del acceso a la memoria secundaria, se desea:

            - Maximizar la información recuperada.

            - Minimizar el número de accesos.

 

            Manejo de Buffers

 

- Un buffer se define como un conjunto de bytes, que son leídos o escritos desde un

  dispositivo de almacenamiento, en la memoria primaria.

- La utilización de esta técnica permite reducir el número de accesos a memoria secundaria.

 

1.2   Ficheros lógicos y ficheros físicos

 

- Desde un punto de vista físico, un fichero se define como un conjunto de bytes que se

  almacenan en memoria secundaria.

- Desde el punto de vista de una aplicación, un fichero es su conexión con el mundo exterior,

  posibilitándole el envío y la recepción de información.

-De este modo se definen el Fichero Físico y el Fichero Lógico.

- La conexión entre ambos es realizada por el sistema operativo.

 

 

 

1.3   Acceso a los datos situados en ficheros

 

            Administrador de Ficheros

 

- El administrador de ficheros es la parte del sistema operativo que se encarga de la gestión de

  los ficheros.

- Su primera tarea es comprobar que existe una conexión entre el fichero lógico y un fichero

  físico determinado.

- Seguidamente se define en que parte del fichero se desea realizar la operación, y si esta se

  encuentra en un buffer de memoria.

 

            Procesador de Entrada/Salida

 

- El procesador de entrada/salida se encarga de controlar el tráfico de información desde y

  hacia la memoria primaria.

 

            Número de Buffers y Velocidad de Acceso

 

- El manejo de buffers por parte del administrador de ficheros permite reducir el número de

  accesos a memoria secundaria.

- Pero una cuestión fundamental es el número de buffers a utilizar.

- En realidad  se utilizan varios buffers que se manejan de modo indistinto para lecturas y

  escrituras.

- Si todos los buffers están ocupados, se debe vaciar uno de ellos para posibilitar una lectura.

- Normalmente se utiliza el algoritmo LRU, es decir, se vacía el buffer menos recientemente

  utilizado.

 

1.4   Coste de acceso a dispositivos de almacenamiento

 

            Tipos de Dispositivos

 

- Según el modo en el que se accede a un dato dentro del medio de almacenamiento:

            - Los Dispositivos de Acceso en Serie, como las cintas magnéticas.

            - Los Dispositivos de Acceso Directo, como los discos magnéticos.

- Los primeros se utilizan para almacenar información que deba ser leída o escrita de modo

  global.

- Mientras que los segundos se utilizan en el manejo de ficheros cuyo criterio de acceso es

  más aleatorio.

 

1.4.1   Coste de acceso a discos

 

            Organización de un Disco

 

- Un disco se presenta como un conjunto de Platos, cada uno de los cuales presenta al menos

  una Superficie Magnética sobre la que se almacena información.

- Cada superficie se divide en Pistas, y éstas a su vez en Sectores.

- Las operaciones sobre la superficie se realiza a través del Cabezal de Lectura/Escritura.

- El movimiento del cabezal para alcanzar una pista concreta se denomina Desplazamiento.

- Cuando un disco presenta varios platos se denomina Paquete de Discos.

- La capacidad de los sectores suele ser constante en todo el disco, por lo que las pistas

  interiores presentan mayor densidad de grabación.

- El acceso a un dato en disco, lee o escribe la información de un sector sobre un buffer.

 

            Organización por Sectores

 

- Un usuario asume que los ficheros aparecen en sectores continuos dentro del disco.

- Pero no es así, ya que no es posible leer sectores contiguos, porque se requiere un cierto

  tiempo para procesar la información inicialmente leída.

- Por tanto, si se almacenaran de este modo, sólo se podría leer un sector en cada giro.

- Para evitar este problema, se suelen intercalar los sectores lógicamente contiguos entre otros

  sectores.

- Otra alternativa es el acceso consecutivo de un conjunto de sectores, denominado Cúmulo.

- La secuencia lógica de los cúmulos en el fichero aparece en la FAT.

- Para reducir el coste de acceso, es necesario minimizar el coste de los desplazamientos.

- Un registro puede aparecer en un único sector, lo que puede producir Fragmentación interna.

 

            Organización por Bloques

 

- Las pistas de los discos también pueden estar organizados por bloques.

- Su tamaño puede ser definido por el usuario, y su valor puede ser fijo o variable.

- Un bloque puede descomponerse en una serie de subbloques:

            - Subbloque Contador, que incluye el número de bytes del bloque asociado.

            - Subbloque Clave, que incluye la clave del último registro del bloque.

            - Subbloque de Datos, en el que aparece la información.

 

            Overhead de las Organizaciones

 

- Tanto los sectores como los bloques produce cierto overhead de almacenamiento, que

   reduce la capacidad del disco.

- Parte de este overhead se produce cuando se formatea el disco.

- En las organizaciones por sectores, debe de incluir en cada sector la siguiente información:

            - Dirección del Sector y de la Pista.

            - Estado del Sector, útil o dañado.

            - Espacios y Marcas de Sincronización.

- El usuario no tiene la posibilidad de manejar esta información. En las organizaciones por

  bloques, parte de esta información sí puede ser definida por el programador.

 

            Cálculo del Coste de Acceso a un Disco

 

- El coste del acceso a un disco se calcula a partir de la suma de tres valores:

            - Tiempo de Desplazamiento, para situar el cabezal sobre el cilindro adecuado.

              Se obtiene como suma del Tiempo Inicial de Arranque del Cabezal, s, y el producto

              del coste de atravesar un cilindro, m, y el número de cilindros a atravesar, n.

                                               f(n) = s + m*n

            - Retraso por Rotación, que incluye el tiempo necesario para situar el cabezal en la

              pista. Depende de la velocidad de giro del disco y de la posición del cabezal.

            - Tiempo de Transferencia, en el que se realiza de modo efectivo la operación.

              Depende del número de bytes a transmitir y de la velocidad de giro.

 

   Tiempo Transferencia = (nº bytes a transmitir / nº bytes en la pista) * Tiempo Rotación

 

1.4.2   Coste de Acceso a Cintas

 

            Organización de las Cintas

 

- Una cinta suele estar compuesta por una serie de pistas paralelas.

- Los datos se agrupan en bloques cuyo tamaño es variable.

- Una cinta se caracteriza por los parámetros:

            - Densidad de la Cinta, medido en número de bits por pulgada.

            - Velocidad de la Cinta, medido en pulgadas por segundo.

            - Tamaño del Hueco entre Bloques.

 

            Cálculo del Tamaño de una Cinta

 

- Para calcular el tamaño necesario de la cinta para almacenar una información se considera:

            - La longitud Física de un Bloque de Datos.

                     b = (Tamaño del Bloque) / (Densidad de la Cinta)

            - La longitud de un hueco entre bloques, g.

            - El número de Bloque, n.

                        s = n * (b+g)

 

            Cálculo del Acceso a una Cinta

 

- El Coste Nominal de Transmisión de Datos se define como:

                        Densidad de Cinta (bpi) * Velocidad de Cinta (ips)

- Pero no se tiene en cuenta el espacio ocupado por los huecos entre bloques, para ello es

   necesario definir la densidad de grabado efectivo,

       Número de Bytes por Bloque / Número pulgadas necesarias para almacenar bloque

 

 

                  TEMA 2   ESTRUCTURA DE UN FICHERO

 

 

2.1   Introducción

 

- Los bytes que constituyen el fichero aparecen agrupados para formar unidades de inform.

- En un fichero aparecen un conjunto de entidades caracterizadas por una serie de atributos.

- Las entidades se asocian a Registros, y los atributos a Campos.

- La cuestión se centra en como se puede localizar un determinado atributo de una entidad

  dentro del fichero.

- Una alternativa es conocer de antemano la posición de inicio de cada una de las informac.

- Otra posibilidad es marcar de algún modo el principio y el fin de cada información.

 

 

 

 

 

2.2   Organización: Campos y Registros

 

            Definición y Tipos de Campos

 

- Campo: menor unidad de información con significado lógico en un fichero.

- Alternativas para localizar los campos en un fichero:

1º) Campos de Tamaño Fijo.

            - Cada campo ocupa en disco el mismo número de bytes. Para datos con longitud muy

              variable, puede producir un derroche, bastante importante, de la capacidad del disco.

2º) Comenzar un Campo con un indicador de longitud.

            Este indicador incluye el número de bytes del dato incluido en el campo.

3º) Colocar un delimitador al final del campo.

            Se elige un carácter especial que se escribe a continuación de los bytes del campo.

 

            Definición y Tipos de Registros

 

- Registro: conjunto de campos que permanecen juntos cuando se observa el fichero con un

  mayor nivel de abstracción.

- Para poder agrupar los campos de un registro, resulta necesario determinar los límites de un

  registro, apareciendo diferentes opciones:

1º) Registros de tamaño fijo, a nivel de bytes.

            Los campos de longitud fija se suelen reunir para formar registros de tamaño fijo.

2º) Registros de tamaño fijo, a nivel de campos.

3º) Comenzar cada registro con un indicador de longitud.

4º) Definir un fichero índice.

            Se utiliza un fichero índice cuyos registros indican el byte de inicio de los registros del

            fichero original.

5º) Colocar un delimitador al final de los registros.

 

            Elección de la Estructura

 

- Existen diferentes aspectos que influyen en la elección de la estructura de un fichero: el

  lenguaje de programación, el tipo de operaciones que se implemente sobre el fichero.

 

2.3   Acceso a la Información

 

            Modos de Acceso

 

- La recuperación de la información puede ser de dos tipos:

            - Global, que recupera toda la información.

            - Selectiva, en donde se desea recuperar una parte de la información del fichero.

- Mediante la utilización de la primera opción, el coste de los dos tipos de recuperación es

  equivalente, O(n).

- La segunda opción debe conocer la posición de un registro en el fichero.

- La recuperación selectiva con esta opción requiere el manejo de registros de tamaño fijo,

  obteniendo un coste O(1).

 

 

 

            Definición de Agrupamientos

 

- El agrupamiento pretende almacenar lo más próximamente posible los registros que, de

  modo habitual, se acceden conjuntamente.

- El agrupamiento se puede realizar dentro de un fichero o entre ficheros

 

2.4   Actualización de la Información

 

- Cuando se realizan diferentes operaciones de eliminación e inserción de información, puede 

  aparecer espacio no utilizado en el fichero.    

 

            Compactado de la Información

 

- Esta opción es la más sencilla, siendo útil tanto para registros de tamaño fijo como variable.

- Puede no ser una solución eficiente para fichero con un alto grado de actualización.

 

            Lista de Registros Disponibles

 

- El borrado de registros debe de asegurar que el registro quede perfectamente marcado

  (elegir un carácter que se escriba al principio del registro) y que se puedan reutilizar estos

  registros, lo que se puede realizar de diferentes formas:

            - Acceso Secuencial al fichero (coste alto, no se suele utilizar).

            - Enlazar los registros borrados mediante una Lista.

 

            Lista en Registros de Longitud Fija

 

- El carácter que marca el registro como borrado, aparece al principio del registro.

- En este tipo de registros, la lista se forma a partir del número relativo de registro, grabado a

  continuación del carácter de borrado.

 

            Lista en Registros de Longitud Variable

 

- La lista debe de contener el tamaño de cada uno de los registros que la componen.

- El carácter de borrado aparece como primer carácter del primer campo del registro, es decir,

  a continuación del tamaño del registro.

- El enlace entre los registros de la lista se realiza mediante la utilización de la posición física

  de los registros.

- Dicha información aparece a continuación del carácter de borrado.

 

            Fragmentación Interna y Externa

 

- La Fragmentación se define como el espacio asignado a un fichero en memoria secundaria

  que no puede ser utilizado para almacenar información.

- La fragmentación puede ser de dos tipos:

            Interna, si el espacio aparece asignado a un registro.

            Externa, si el espacio aparece entre el asignado a dos registros.

- El primer tipo aparece cuando se utilizan registros de longitud fija para almacenar datos de

  tamaño variable.

 

            Reducción de la Fragmentación Externa

 

- La solución más sencilla es la Compactación de los ficheros, aunque es una solución muy

   costosa.

- La solución más interesante es la utilización de Estrategias de Colocación que seleccionen el

   Hueco más adecuado en la lista.

 

            Estrategias de Colocación

 

- La estrategia más sencilla es la del Primer Ajuste, que toma el primer espacio en el que

   quepa el nuevo registro, aunque no resuelve la problemática de la fragmentación externa.

- Una solución es ordenar los espacios en orden de tamaño ascendente, de modo que en la

   búsqueda se obtenga el espacio de tamaño más similar.

- Esta estrategia del Mejor Ajuste, puede tener un coste de inserción y borrado de la lista muy

   alto, y además los espacios libres pueden ser demasiado pequeños para su reutilización.

- La ordenación descendiente reduce el coste del borrado, y además el tamaño del espacio

   libre resultante puede ser reutilizado.

- Esta opción da lugar a la estrategia del Peor Ajuste.

 

            Conclusiones

 

- Si la frecuencia de las operaciones de actualización es baja, la estrategia del primer ajuste es

   suficiente.

- Cuando el problema se relaciona con la fragmentación interna, no debe ser utilizada la

   estrategia del peor ajuste.

- Si aparece un problema de fragmentación externa, no debe utilizarse la estrategia del mejor

   ajuste.

 

 

      TEMA 3   ESTRUCTURAS DE ALMACENAMIENTO BÁSICAS

 

 

3.1   Búsqueda de Información

 

            Definición de Clave

 

- Normalmente se desea acceder a los registros que contienen cierta información en un campo

- Este método de búsqueda de información se denomina Acceso por Clave.

- Los valores en este campo deben de cumplir una serie de normas de almacenamiento que

   aseguren su localización, tales como:

            - Las cadenas de caracteres deben estar en mayúsculas, y sólo debe aparecer un

              espacio en blanco entre palabras.

            - No deben aparecer espacios en blanco ni en los campos numéricos ni en los de fecha.

- En estos casos se dice que la clave aparece en Forma Canónica.

 

            Búsqueda Secuencial y Búsqueda Binaria

 

- El método de acceso más sencillo es la búsqueda secuencial, pero su coste es O(n).

- Un método alternativo es la Búsqueda Binaria, cuyo coste es O(log n).

- Este método requiere que los registros sean de tamaño fijo y que estén ordenados por el

   valor del campo clave asociado al proceso de búsqueda.

 

            Ordenación de un Fichero

 

- La idea principal va a ser leer completa, o parcialmente, todos los registros, y

   posteriormente realizar la ordenación en memoria RAM.

 

            Ordenación en Memoria

 

- La primera idea es leer todos los registros en un vector de cadena de caracteres que se puede

   ordenar en memoria.

- Pero el orden de este vector de cadenas puede ser diferente al definido por la clave.

- Para evitar este problema, se crea un segundo vector de caracteres, el índice, en el que

   aparece la clave de los registros y un puntero a la posición del registro en el anterior vector.

- Es posible reducir el coste si se define un tercer vector que contiene únicamente los

   punteros antes mencionados.

 

            Conclusiones

 

- La ordenación en memoria sólo es útil cuando el fichero es lo suficientemente pequeño

   como para poder almacenarse en memoria.

- Todos estos hechos aconsejan definir una técnica que:

            - Reduzca el coste de acceso, a uno o dos accesos a disco, para cualquier clave.

            - La búsqueda de información no requiera ordenar los registros del fichero.

            - Las operaciones de actualización se realicen de modo eficiente.

 

3.2   Definición y Manejo de Índices

 

            Concepto de Fichero Índice

 

- Los Ficheros Índices se definen como un fichero cuyos registros son de tamaño fijo, en el

   que se almacena la clave del registro y un puntero a este registro.

- Su utilización presenta una serie de ventajas:

            - Permite el uso de la búsqueda binaria tanto para ficheros de registros de tamaño fijo

              como para los de tamaño variable.

            - El proceso de ordenación se restringe al fichero índice.

            - Es posible definir diferentes ficheros índice, cada uno de los cuales se asocia a una

              clave de búsqueda.

- Pero también presenta inconvenientes:

            - Las operaciones de actualización requieren la actualización de más de un fichero.

            - El orden establecido en los ficheros índices debe de mantenerse.

            - Si el fichero índice es demasiado grande para almacenarse en memoria, estas

              operaciones pueden ser muy costosas.

 

            Tipos de Índices

- Una primera clasificación es la siguiente:

            - Índice Denso, si contiene una referencia a todos los registros del fichero.

            - Índice no Denso, si sólo contiene referencia a un subconjunto de registros.

- Otra posible clasificación es la siguiente:

            - Índice Primario, si contiene la clave primaria del fichero.

            - Índice Secundario, si contiene otra clave.

 

            Control contra Fallos del Sistema

 

- Si no se produjera la actualización del índice por una fallo del sistema, este no reflejaría el

   estado real del fichero y por tanto debería de reestablecerse.

- Para detectar esta posibilidad, en el registro de cabecera del fichero índice se introduce una

   bandera que indique esta situación:

            - La lectura del fichero, debería marcar el fichero como leído y no escrito.

            - Por su parte, la escritura debería modificar el valor de esta bandera.

- La lectura debería controlar el estado de esta bandera, reconstruyendo el fichero índice si

   ésta indicara que ha sido leído y no reescrito.

 

3.3   Índices Multinivel. Arboles B y B+

 

            Índices Multinivel

 

- Cuando un fichero índice es demasiado grande para almacenarse en memoria RAM, su

   gestión puede resultar muy costosa.

- Estos problemas también surgen si no es posible almacenar en memoria todos los ficheros

   índice de un fichero.

- La solución a estos problemas es la definición de un índice no denso sobre el fichero índice

   en cuestión.

- De este modo se define un índice multinivel, compuesto por un conjunto de índices no

   densos que actúan sobre un índice que puede ser denso o no denso.

 

            Propiedades de los Arboles B

 

- Se define el orden de un árbol B como el número máximo de hijos de una página.

- Por su parte la hoja de un árbol B como el nivel más bajo de la estructura.

- Así un árbol B de orden m cumple que:

            - Una página puede referenciar m páginas hijo como máximo.

            - Toda página, except