12.176 cursos gratis
8.741.359 alumnos
Facebook Twitter YouTube
Busca cursos gratis:

Capýtulo 2:

 Organizaciones de ficheros y estructuras de

III Organizaciones de ficheros y estructuras de acceso

En este capítulo se presentan los conceptos fundamentales sobre el almacenamiento físico de la base de datos en dispositivos de almacenamiento secundario, como los discos.

Introducción

Los discos son lentos pero también son maravillas de la tecnología: consiguen incorporar varios gigabytes de capacidad en un ordenador portátil. Hace algunos años, los discos con esa capacidad eran del tamaño de una pequeña lavadora. Pero comparados a otras partes del ordenador, los discos son lentos.

Acceder a memoria RAM cuesta alrededor de 120 nanosegundos, mientras que acceder al disco cuesta unos 30 milisegundos. Para darnos una idea de la diferencia de tiempos (30 mseg / 120 nseg = 250.000), vamos a hacer un símil: buscar algo en memoria RAM sería como buscar algo en el índice de un libro, para lo que empleamos unos 20 segundos. Buscar algo en disco sería como pedir a la biblioteca que localicen un libro y que el libro llegue después de unos 58 días.

Sin embargo, los discos proporcionan gran capacidad a un coste mucho menor que la memoria RAM y además, mantienen la información aun estando apagados, son no volátiles.

Es fundamental y necesario un buen diseño de la estructura de los ficheros para que nuestras aplicaciones tengan acceso a toda la capacidad del disco sin que tengan que esperar mucho tiempo por los datos. El objetivo es minimizar el número de accesos a disco y maximizar la probabilidad de que la información que el usuario va a necesitar en breve ya esté en memoria RAM.

Los objetivos en el diseño de estructuras de ficheros son los siguientes:

·        Obtener la información con un solo acceso a disco. Siguiendo con el símil, no tener que esperar varias veces los 58 días que cuesta obtener el libro. Esto sería el caso ideal.

·        Si no se pueden obtener los datos en un solo acceso, hacen falta estructuras que permitan encontrar la información con el mínimo número de accesos posible (dos o tres como mucho). Los algoritmos rápidos de búsqueda no son suficientes: la búsqueda binaria encuentra un registro entre 5.000 con un máximo de 16 comparaciones; 16 accesos son demasiados cuando se accede a disco.

·        Hace falta que la estructura del fichero permita agrupar la información de modo que se puedan obtener todos los datos que se necesitan de una sola vez.

Todo esto no es difícil si los ficheros nunca cambian, pero con ficheros que crecen y disminuyen en tamaño a medida que la información se añade o se borra, es mucho más complejo.

Las organizaciones de ficheros han ido evolucionando con el tiempo. En un principio, los ficheros estaban en cinta, con lo que el acceso era secuencial y por lo tanto el coste de acceso aumentaba conforme el fichero crecía en tamaño. Ya que los ficheros de gran tamaño no se podían manejar secuencialmente, la aparición de los discos hizo que se comenzaran a utilizar los índices.

Un índice es un fichero pequeño con una lista de claves y punteros donde la búsqueda es más rápida. Si se conoce el valor de la clave, el acceso es directo.

Cuando los índices son demasiado grandes y cambian con frecuencia, son difíciles de gestionar, ya que son ficheros ordenados en los que la búsqueda se realiza de forma secuencial (búsqueda lineal). Es entonces cuando surge la idea de utilizar estructuras en forma de árbol como una posible solución. Esto ocurría a principios de los años sesenta.

Desafortunadamente, los árboles crecen de un modo muy desigual, con lo que en muchas ocasiones todavía hay que hacer muchos accesos a disco para obtener la información. En 1963 se crean los árboles AVL (árbol binario autoajustable), que están equilibrados en altura: entre dos subárboles de la misma raíz sólo puede haber una diferencia en altura de un nivel. Estos árboles son muy buenos como estructuras de datos en memoria RAM, pero muy malos para ficheros en disco, ya que requieren muchos accesos: al ser binarios son demasiado profundos. Incluso los árboles binarios equilibrados requieren demasiados accesos. Hacía falta un modo de tener un árbol equilibrado cuando cada nodo del árbol no era un solo registro (como en un árbol binario), sino un bloque conteniendo decenas o incluso centenas de registros.

En 1972 (casi diez años después), surgen los árboles B ( balanced: equilibrado), en los que todas las hojas están al mismo nivel. Cuesta tanto tiempo encontrarlos porque su filosofía es completamente diferente de la filosofía de los árboles AVL: crecen de abajo hacia arriba conforme se añaden registros. Los árboles B ofrecen muy buenas prestaciones pero presentan un problema: no es posible acceder secuencialmente a los registros del fichero de modo eficiente. Casi de inmediato se crea el árbol B+, añadiendo una lista enlazada en el nivel más bajo del árbol B, con lo que también se permite el acceso secuencial. Con los árboles B+ se obtiene la información en tres o cuatro accesos entre millones de registros, y las prestaciones se mantienen aunque se añadan o eliminen registros.

Más tarde, a finales de los años setenta, se empieza a utilizar la dispersión (hashing). Se había utilizado anteriormente para índices, pero no para ficheros dinámicos que cambian con frecuencia. Después de los árboles B, los investigadores se pusieron a trabajar con la dispersión dinámica extensible, que permite acceder a la información en uno o dos accesos a disco, independientemente del tamaño del fichero.

Conceptos fundamentales de organizaciones de ficheros

En los dispositivos de almacenamiento secundario, la base de datos se organiza en uno o varios ficheros. Cada fichero está formado por una serie de registros, y cada registro se divide en varios campos. Normalmente, los registros corresponden a entidades: personas, objetos, eventos, etc., siendo los campos aquellos atributos o propiedades que se desea conocer sobre las entidades: el nombre de cada persona, el color del objeto, la fecha del evento, etc.

Por ejemplo, el fichero con información sobre la plantilla de la empresa inmobiliaria estará formado por registros de empleados con los siguientes campos: número del empleado, apellido, puesto, DNI y número de la oficina a la que pertenece:

EnumApellidoPuestoDNIOnum
EL21PastorDirector39432212EO5
EG37CubedoSupervisor38766623XO3
EG14ColladoAdministrativo24391223LO3
EA9RenauSupervisor39233190FO7
EG5PratsDirector25644309XO3
EL41BaezaSupervisor39552133TO5

Cuando un usuario pide los datos del empleado EG37, el SGBD identifica el bloque de disco que contiene dichos datos y lo pide al sistema operativo. Este utilizará sus rutinas de acceso a ficheros para obtener el bloque y lo almacenará en los buffers del SGBD en memoria principal. Un bloque o página es la unidad mínima de transferencia entre disco y memoria principal. Normalmente, caben varios registros de datos en un mismo bloque. Si un registro no cabe en un solo bloque, se repartirá entre varios. Siguiendo con el ejemplo anterior, si caben tres registros de plantilla por bloque, el fichero ocupará dos bloques:

EnumApellidoPuestoDNIOnumbloque
EL21PastorDirector39432212EO5 
EG37CubedoSupervisor38766623XO31
EG14ColladoAdministrativo24391223LO3 
EA9RenauSupervisor39233190FO7 
EG5PratsDirector25644309XO32
EL41BaezaSupervisor39552133TO5 

El orden en que se colocan los registros en un fichero depende de su estructura. Los principales tipos de estructuras de ficheros son los siguientes:

·        Ficheros desordenados. En estos ficheros los registros no siguen un orden específico.

·        Ficheros ordenados. En estos ficheros los registros están ordenados por el valor de un determinado campo.

·        Ficheros dispersos. En estos ficheros los registros se almacenan en la posición del fichero que indica una función matemática al ser aplicada sobre un determinado campo.

·        Agrupamiento. Varios ficheros intercalan sus registros de modo que éstos queden agrupados por el valor de algún campo que tienen en común.

Los pasos que se deben llevar a cabo para almacenar y acceder a un registro de un fichero es lo que se denomina un método de acceso. Hay distintos métodos de acceso, algunos de los cuales sólo se pueden utilizar con determinadas estructuras de ficheros.

Dispositivos de almacenamiento secundario

El almacenamiento secundario se realiza generalmente en disco y en cinta. Normalmente los ficheros están almacenados en disco y los datos se transfieren desde el disco a la memoria principal a medida que se necesitan. El almacenamiento en disco es la forma principal de almacenamiento con acceso directo. El almacenamiento en cinta es más lento y el acceso es sólo secuencial, por lo que la función de las cintas está, básicamente, limitada a archivar datos.

Discos

La unidad física en que está contenido el medio de grabación del disco se llama controlador de disco. El controlador contiene un paquete de discos, también denominado volumen. El paquete de discos está formado por un conjunto de superficies grabables (discos) montados sobre un eje.

En operación, el eje y los discos rotan a una alta velocidad. Los datos se graban sobre las pistas, que son coronas circulares que se encuentran sobre cada superficie. Las pistas que se encuentran unas sobre otras forman cilindros.

Hay un conjunto de cabezas de lectura/escritura ubicadas al final de un brazo que se mueven como un grupo, de tal forma que éstas pueden ser posicionadas sobre todas las pistas de un mismo cilindro. De este modo, toda la información de un cilindro puede ser accedida sin tener que mover el brazo, que es la operación más lenta.

Las pistas se dividen en porciones, que son las unidades más pequeñas de espacio que se pueden direccionar, y pueden ser sectores o bloques.

·        Sectores. Son divisiones físicas y, por tanto, de tamaño fijo. Los sectores van numerados, de modo que sectores consecutivos tienen números consecutivos.

Un clusteres una cantidad fija de sectores contiguos, y constituye la unidad de espacio más pequeña que se puede asignar a un fichero. El gestor de ficheros ve un fichero como un conjunto de clusters, información que se encuentra almacenada en la FAT ( File Allocation Table). Una vez se localiza un cluster, no hay que mover las cabezas para leer todos sus sectores. El administrador del sistema es quien define cuántos sectores habrá en un cluster; cuantos más haya, menos movimientos de las cabezas hay que realizar, con lo que se mejoran las prestaciones en el acceso secuencial.

Un extentes un trozo de fichero formado por varios clusterscontiguos. Mediante ellos se pretende enfatizar más la contigüidad física de los sectores. Lo ideal (en acceso secuencial) es tener un solo extent. Cuantos más haya, más desperdigado estará el fichero y, por lo tanto, más tiempo se dedicará a mover las cabezas de lectura/escritura.

Cuando las pistas se encuentran divididas en sectores hay problemas de fragmentación interna debido a que todos los sectores son del mismo tamaño: si en un sector no cabe un múltiplo del número de registros, hay huecos. Cabe la posibilidad de partir los registros entre sectores, pero esto hará que para acceder a ciertos registros, haya que traer dos sectores en lugar de uno. Otro origen del problema de la fragmentación interna viene por el hecho de la asignación de clusters enteros a ficheros: puede que sobre espacio en un cluster, aunque no es tan malo, ya que se puede necesitar más tarde.

Al principio de cada sector hay información invisible al programador en donde figura la dirección del sector, la dirección de la pista en la que se encuentra y su condición (en buen estado o defectuoso).

·        Bloques. Son divisiones lógicas y, por lo tanto, su tamaño es variable. Este tamaño puede ser distinto para cada aplicación, y se puede fijar como un múltiplo del tamaño de registro, por lo que no hay problemas de fragmentación interna.

Los bloques contienen datos e información sobre los datos: tamaño en bytes y, en ocasiones, una clave indicando, por ejemplo, el valor de algún campo clave del último registro del bloque. Además, hay información invisible al programador al principio de cada bloque, más cantidad que con los sectores.

Comparando sectores y bloques, estos últimos ofrecen mayor flexibilidad: se ahorra tiempo y se consigue mayor eficiencia, ya que el programador determina cómo se van a organizar los datos en disco. Los bloques son superiores a los sectores cuando se desea que la localización física de los ficheros corresponda con su organización lógica. Sin embargo, el programador y/o el sistema operativo deben hacer trabajo extra para determinar la organización de los datos.

La dirección de un registro en disco, normalmente necesita información sobre el número de cilindro, la superficie y el sector o bloque.

Coste del acceso a disco

En general hay tres factores que afectan directamente a la velocidad con que los datos se transfieren entre disco y memoria principal. Cada uno de estos factores consume un tiempo y conlleva una operación física.

·        Tiempo de búsqueda (seek): es el tiempo necesario para mover el brazo con las cabezas de lectura/escritura desde su posición actual hasta el cilindro direccionado. El brazo puede estar sobre el cilindro deseado, tener que ir al siguiente cilindro o al otro extremo del disco; por lo tanto, dependiendo de la distancia a recorrer, será más o menos caro. En un sistema multiusuario este tiempo es más notable ya que cada usuario estará accediendo a un fichero distinto y lo más probable es que en cada acceso de cada usuario haya que emplear un tiempo de búsqueda que será, por término medio, el tiempo de recorrer un tercio del número de cilindros.

·        Tiempo de rotación (latencia): el disco debe girar hasta que la cabeza esté situada sobre el sector a leer o escribir. El tiempo medio es el tiempo requerido para dar media vuelta.

·        Tiempo de transferencia: es el tiempo empleado en leer o escribir los datos. Este tiempo es función del número de bytes transferidos (número de bytes transferidos / número de bytes por pista tiempo de dar una vuelta).

 

 

El disco: un cuello de botella

Las prestaciones de los discos crecen constantemente, pero todavía están muy lejos de las velocidades de las redes. Por ejemplo, un disco de 50 Kbytes por pista puede proporcionar datos a una velocidad pico de 5 Mbytes por segundo, mientras que una red local puede tener una velocidad de 100 Mbytes por segundo. Esto hace que la CPU tenga que esperar a los datos debido a la lentitud de los discos, ya que la red es lo suficientemente rápida. Hay una serie de técnicas que se utilizan para resolver este problema:

·        Multiprogramación: la CPU hace otras tareas mientras espera.

·        Stripping: el fichero se divide en trozos y se reparte entre varios discos, de modo que todos los discos puedan estar mandando datos a la vez. Esta técnica necesita que la gestión de los accesos a disco sea más sofisticada.

·        Discos RAM: se tiene memoria RAM configurada para actuar como un disco. El acceso es rápido, lo caro es la memoria RAM. Tiene el inconveniente de que la memoria RAM es volátil.

·        Caché de disco: se tiene memoria RAM configurada para tener páginas de datos (sectores o bloques) del disco. El gestor de ficheros mira primero en la caché a ver si está el sector que se desea leer o escribir, y sólo si no lo encuentra es cuando va a disco. Por el principio de localidad de las referencias, hay una gran probabilidad de que lo que se necesita esté ya en la caché al ir a buscarlo.

 Acceso a los datos

En este apartado se muestra, mediante un ejemplo, qué partes del software y del hardware están involucradas en una operación de acceso a disco. Supongamos que un programa de usuario ha solicitado escribir en el fichero texto el contenido de la variable c, cuyo tamaño es de 1 byte.

write("texto",c,1) c: `P´

1. El programa pide al sistema operativo que escriba el contenido de c en el fichero texto.

2. El sistema operativo pasa el trabajo al gestor de ficheros.

3. El gestor de ficheros comprueba que las características lógicas del fichero son coherentes con lo que se quiere hacer: el fichero está abierto para escritura, el usuario posee los permisos oportunos, etc.

4. El gestor de ficheros busca en la FAT la posición física del sector/bloque que recibirá el byte.

5. El gestor de ficheros se asegura de que el sector/bloque se encuentra en un buffer de entrada/salida en memoria RAM, y escribe el byte `P´ en la posición correspondiente en el buffer.

6. El gestor de ficheros dice al procesador de entrada/salida dónde se encuentra el byte en memoria RAM y cuál es su destino en el disco.

7. El procesador de entrada/salida espera a que el controlador esté disponible y pone el dato en el formato del disco.

8. El procesador de entrada/salida envía el dato al controlador del disco.

9. El controlador del disco indica al dispositivo que mueva la cabeza a la pista, espera hasta que el sector/bloque esté bajo ella y le manda el byte, que es escrito bit a bit.

Ficheros desordenados

En un fichero desordenado, también denominado fichero heap, los registros se colocan en el fichero en el orden en que se van insertando. Cuando llega un nuevo registro, se inserta en el último bloque del fichero; si el fichero está lleno, se le añade más espacio. Esta organización hace que la inserción sea muy eficiente. Sin embargo, cuando se trata de acceder a un registro del fichero, es necesario realizar una búsqueda lineal recorriendo todos los bloques del fichero uno tras otro, hasta encontrar el registro deseado. Esto hace que las búsquedas de registros en los ficheros desordenados sean muy lentas.

Si lo que se desea es obtener todos los registros del fichero presentándolos en un determinado orden (según el valor de alguno de sus campos), es necesario realizar una ordenación externa si el fichero completo no cabe en memoria principal: se van leyendo los registros, se escriben de forma ordenada en un fichero temporal en disco y, finalmente, se accede a este último fichero para leer los registros una vez ordenados.

Para eliminar un registro es necesario traer a memoria principal el bloque en el que se encuentra, después se marca el registro como borrado y, por último, se vuelve a escribir el bloque en el mismo lugar en que se encontraba. El espacio que ocupaba el registro borrado no se reutiliza, lo que hace que empeoren las prestaciones, por lo que, cada cierto tiempo, habrá que realizar una reorganización del fichero para recuperar este espacio.

Para modificar un registro también es necesario traerlo a memoria principal y actualizarlo. Si el registro modificado cabe en el bloque en el que se encontraba, se reescribe el bloque en su sitio. Si el registro modificado ha aumentado su tamaño de modo que no cabe en el bloque, hay que borrar el registro original y añadir el registro modificado al final del fichero.

Los ficheros desordenados son los más adecuados cuando se trata de cargar grandes cantidades de datos, ya que la inserción es muy eficiente al no tener que realizarse ningún cálculo para determinar la posición que debe ocupar el registro en el fichero.

Ficheros ordenados

En los ficheros ordenados, los registros se encuentran ordenados físicamente según el valor de uno o varios campos. A este campo o campos se les denomina campos de ordenación.

Cuando se trata de buscar un registro en un fichero ordenado, se puede utilizar una búsqueda binaria sólo cuando se busca por el campo de ordenación. Si la búsqueda se realiza a través de cualquier otro campo, se debe hacer una búsqueda lineal. Si se quiere leer el fichero ordenadamente, la operación será muy eficiente si el orden escogido es el del campo de ordenación. Si el orden de lectura es sobre cualquier otro campo, es preciso realizar una ordenación externa.

Para insertar un registro hay que encontrar su posición en el fichero según el orden establecido, hacer hueco y escribir. Si hay espacio suficiente en el bloque correspondiente, se reordena el bloque y se escribe en el fichero. Si no hay espacio en el bloque, habrá que mover algún registro al siguiente bloque. Si este último bloque no tiene espacio suficiente para estos registros, habrá que mover algunos registros al bloque siguiente, y así sucesivamente. Esto hace que la inserción de un registro pueda ser muy costosa. Una solución consiste en tener un fichero desordenado de desborde, en donde se van realizando todas las inserciones. Cada cierto tiempo, el fichero de desborde se mezcla con el fichero ordenado, de modo que así las inserciones son muy eficientes. Esto perjudica a las búsquedas, ya que si el registro no se encuentra mediante búsqueda binaria en el fichero ordenado, hay que realizar una búsqueda lineal en el fichero de desborde.

Cuando se trata de eliminar un registro, hay que encontrarlo y marcarlo como borrado. Como en los ficheros desordenados, cada cierto tiempo se debe realizar una reorganización del fichero. Para modificar un registro hay que encontrarlo y actualizarlo en caso de que quepa en el bloque en el que se encontraba. Si el registro actualizado ya no cabe en su ubicación, hay que borrarlo, hacer hueco e insertarlo. Si en la actualización se modifica el campo de ordenación, entonces es muy probable que haya que cambiar el registro de lugar para mantener el orden: habrá que borrarlo, hacer hueco e insertarlo de nuevo.

Los ficheros ordenados no se suelen utilizar como ficheros de datos en los SGBD.

 

Ficheros dispersos

En los ficheros dispersos, la dirección de cada registro se calcula aplicando cierta función sobre uno o varios de sus campos, denominados campos de dispersión. A la función se le denomina función de dispersión. Los registros de este tipo de ficheros parece que han sido distribuidos de forma aleatoria por el mismo, por lo que a estos ficheros también se les denomina ficheros aleatorios o ficheros directos. El acceso a los datos es muy rápido sólo si se busca con la condición de igualdad sobre el campo de dispersión.

La función de dispersión se debe escoger de modo que los registros queden distribuidos uniformemente en todo el fichero. La técnica más popular consiste en utilizar el resto de la división entera: se toma el valor de un campo, se divide entre un valor determinado y se utiliza el resto de la división entera para obtener la dirección en disco. Otra técnica es el plegado. Consiste en tomar distintas partes del campo de dispersión y aplicarles alguna función aritmética. Por ejemplo, si el campo de dispersión es el DNI, se pueden tomar sus dígitos por parejas y sumarlos. Si el campo tiene caracteres, se puede tomar su valor ASCII para aplicar la operación aritmética. En realidad, la función de dispersión produce un número de bloque relativo. En una tabla que se encuentra en la cabecera del fichero se convierte este número en la dirección del bloque en el disco.

El problema que presentan la mayoría de las funciones de dispersión es que no garantizan direcciones únicas, de modo que varios registros se asocian a una misma dirección de bloque. Si a un bloque se asocian más registros de los que realmente caben, se producen colisiones que hay que resolver. Los registros que se destinan a un mismo bloque se denominan sinónimos.

Hay varias técnicas para gestionar las colisiones:

· Direccionamiento abierto. Cuando se produce una colisión, el sistema hace una búsqueda lineal a partir del bloque al que iba destinado el registro para encontrar un hueco donde insertarlo. Si se llega al final del fichero sin encontrar hueco, se continúa la búsqueda desde el principio.

· Encadenamiento. En lugar de buscar un hueco libre, lo que se hace es disponer de una serie de bloques como área de desborde. Cuando se produce una colisión, el registro se sitúa en el área de desborde y mediante un puntero en el bloque colisionado, se apunta a la dirección del bloque de desborde y la posición relativa del registro dentro del bloque. Además, todos los registros que han colisionado en un mismo bloque se van encadenando mediante punteros.

· Dispersión múltiple. Esta técnica de resolución de colisiones consiste en utilizar una segunda función de dispersión cuando la primera ha producido una colisión. El objetivo es producir una nueva dirección que no provoque colisión. Normalmente, la segunda función da una dirección de bloque situada en un área de desborde.

Aunque la dispersión es el método de acceso directo más rápido a través del campo de dispersión, no es muy útil cuando también se quiere acceder al fichero a través de otro campo. Ya que la mayoría de las funciones de dispersión que se utilizan no mantienen el orden entre los registros, tampoco es útil cuando se quiere leer los registros ordenadamente.

Buscar un registro a través de un campo que no es el de dispersión es tan caro como buscar un registro en un fichero desordenado: es preciso realizar una búsqueda lineal. Para borrar un registro hay que eliminarlo del bloque en el que se encuentra. Si el bloque tiene una lista de desborde, se puede mover un registro de la lista al bloque. Si el registro a borrar está en la lista de desborde, sólo hay que eliminarlo de ella. En este caso, será necesario mantener una lista enlazada de posiciones de desborde no utilizadas. Si al actualizar un registro se modifica el campo de dispersión, es muy probable que el registro tenga que cambiar de posición, por lo que habrá que borrarlo e insertarlo de nuevo.

Otra desventaja de la dispersión es que el espacio de almacenamiento es fijo, por lo que es difícil que el fichero se expanda o se comprima dinámicamente. Si el fichero tiene bloques y en cada uno caben registros, como máximo se podrán almacenar registros. Si hay menos de registros, quedará espacio sin utilizar. Si hay más de registros, habrá muchas colisiones y esto hará que el acceso sea más lento, ya que habrá largas listas de desborde. En este caso, puede ser preferible ampliar el espacio de almacenamiento y cambiar a otra función de dispersión, lo que implica que habrá que redistribuir todos los registros (reorganizar el fichero). Ya que el espacio de almacenamiento es fijo, a este tipo de dispersión se la denomina dispersión estática.

Hay varios esquemas que tratan de remediar esta situación: la dispersión dinámica y la dispersión extensible, que almacenan una estructura de acceso además del fichero, y la dispersión lineal, que no necesita dicha estructura.

Estas técnicas aprovechan el que las funciones de dispersión dan como resultado un valor entero no negativo que, por tanto, se puede representar como un número binario. Los registros se distribuyen entre los bloques teniendo en cuenta los primeros bits de este número, que se denomina valor de dispersión.

Dispersión dinámica

Cuando se utiliza esta técnica, el número de bloques del fichero no es fijo, sino que crece y disminuye conforme es necesario. El fichero puede empezar con un solo bloque y cuando éste se llena, se toma un nuevo bloque. Los registros se distribuyen entre los dos bloques teniendo en cuenta el primer bit de sus valores de dispersión. Los que tienen un 0 van a un bloque y los que tienen un 1 van al otro. Además, se va formando un directorio con estructura de árbol binario que tiene dos tipos de nodos:

· Nodos internos, que guían la búsqueda. Tienen un puntero izquierdo correspondiente al bit 0 y un puntero derecho correspondiente al bit 1.

· Nodos hoja, conteniendo el puntero al bloque de datos.

Para hacer una búsqueda se puede almacenar el directorio en memoria, a menos que sea muy grande. Si no cabe en un bloque, habrá que distribuirlo en dos o más niveles. Cada nodo interno puede tener también un puntero al padre. Se pueden utilizar representaciones especiales de árboles binarios para reducir el espacio necesario para los tres punteros (izquierdo, derecho y padre). En general, un directorio de niveles puede necesitar hasta accesos a bloque para alcanzar un registro.

Cuando un bloque se llena, se "parte en dos" y los registros se redistribuyen según el siguiente bit de su valor de dispersión. En este caso, el directorio se expande con un nuevo nodo interno. Los niveles del árbol binario se expanden dinámicamente (nunca habrá más niveles que número de bits hay en el valor de dispersión).

Si la función de dispersión distribuye los registros uniformemente, el árbol estará equilibrado. Cuando un bloque se vacía, o si el número de registros en dos bloques vecinos cabe en un solo bloque, el directorio pierde un nodo interno y los dos nodos hoja se combinan formando uno solo. De este modo los niveles del árbol pueden disminuir dinámicamente.

Dispersión extensible

En la dispersión extensible el directorio es un vector de direcciones de bloque, donde es la profundidad global del directorio. El entero formado por los primeros bits del valor de dispersión es el índice que indica en qué entrada del vector se encuentra la dirección del bloque que contiene al registro. Puede haber varias entradas en el directorio con los primeros bits en común ( ) apuntando al mismo bloque cuando los registros que van a parar a ellas caben en dicho bloque. Cada bloque tiene una profundidad local (que se almacena con él), que especifica el número de bits que tienen en común los valores de dispersión de los registros que en él se encuentran.

El valor de puede incrementarse o disminuirse en una unidad cada vez que se necesita doblar o disminuir a la mitad el número de entradas en el vector directorio. Es necesario doblar el directorio si un bloque con profundidad local , igual a la profundidad global , se llena. El directorio se disminuye a la mitad si d'$" type="#_x0000_t75">para todos los bloques después de borrar algún registro. Como mucho, son necesarios dos accesos a bloque para llegar a cualquier registro (acceso al directorio y acceso al bloque que contiene el registro).

Comparando entre la dispersión dinámica y la extensible, en la dispersión dinámica el directorio es una estructura enlazada, mientras que en la extensible es un árbol perfecto, por lo que se puede expresar como un vector. En la dispersión dinámica el directorio crece más lentamente, mientras que en la extensible va doblando su tamaño. Sin embargo, ya que en la dispersión dinámica los nodos deben almacenar punteros a los hijos, su tamaño debe ser más grande que en la extensible (al menos el doble de grande). Por lo tanto, el directorio de la dinámica ocupará más espacio en memoria. Además, si el directorio se hace lo suficientemente grande como para necesitar memoria virtual, la dispersión extensible ofrece la ventaja de que se puede acceder al directorio con no más de un fallo de página. Ya que la dispersión dinámica utiliza una estructura enlazada para el directorio, puede que se produzca más de un fallo de página al moverse por el mismo.

Dispersión lineal

El objetivo de la dispersión lineal es que el fichero pueda crecer y disminuir sin tener que utilizar un directorio. Así se ahorra el tiempo extra que los anteriores tipos de dispersión necesitan para acceder al directorio.

Supongamos que un fichero empieza con bloques, numerados , y utiliza la función de dispersión , a la que se denomina función inicial . Cuando hay colisiones se utilizan listas de desborde, una lista para cada bloque. Además, después de una colisión, uno de los bloques del fichero se parte en dos y no es necesariamente el bloque en el que ha ocurrido la colisión. Por ejemplo, se produce la primera colisión. Se inicia una lista de desborde asociada al bloque colisionado y, además, el primer bloque del fichero, el bloque , se parte en dos bloques: el original (bloque ) y uno nuevo al final del fichero (bloque ). Los registros del bloque original se distribuyen entre los dos bloques utilizando una función de dispersión diferente . Una propiedad clave de ambas funciones y es que los registros que iban a parar al bloque con la función , irán a parar al bloque o al nuevo bloque con la función ; esto es necesario para que la dispersión lineal funcione.

Conforme se van produciendo más colisiones, se van partiendo bloques en orden lineal Cuando un bloque se parte, los registros de su lista de desborde (si la tiene) se redistribuyen en bloques del fichero utilizando la función . No se utiliza directorio, sólo es necesario un valor para determinar qué bloques se han partido. Para acceder a un registro con valor de dispersión , primero se le aplica la función a ; si , entonces hay que aplicar la función a porque el bloque ha sido partido. Al principio vale cero, indicando que la función se aplica a todos los bloques; crece linealmente conforme se van partiendo los bloques. Cuando , todos los bloques originales se han partido y, entonces, la función que se aplica a todos los bloques es . En este momento, se pone otra vez a cero y si se producen nuevas colisiones, se utilizará una nueva función . En general, se utiliza una secuencia de funciones , donde Hace falta utilizar una nueva función cuando todos los bloques , se han partido en dos (entonces se pone a cero).

Los bloques que se han partido en dos se pueden recombinar si la carga del fichero disminuye por debajo de un cierto umbral. En general, el factor de carga del fichero se puede definir como , donde es el número de registros en el fichero, es el número de registros que caben en un bloque y es el número de bloques que está ocupando el fichero. Los bloques se combinan de forma lineal y se decrementa de modo apropiado.

Agrupamiento

Hasta ahora se ha supuesto que todos los registros de un fichero son del mismo tipo. En muchas aplicaciones existen relaciones entre los registros de varios ficheros distintos. Estas relaciones se pueden representar mediante campos conectores. Por ejemplo, en el registro de un empleado aparece un campo conector cuyo valor indica el código de la oficina a la que pertenece. En el fichero de las oficinas, los registros tendrán un campo que será el código de oficina. Cuando se quiere acceder a los campos de dos registros relacionados, por ejemplo, a los datos de un empleado y los datos de su oficina, se debe acceder primero al registro del empleado y utilizar el campo conector para obtener el registro con el que se relaciona en el fichero de las oficinas. De este modo, las relaciones se están representando mediante referencias lógicas entre registros de distintos ficheros.

Otro modo de representar las relaciones es mediante referencias físicas: los registros relacionados se almacenan juntos en el mismo fichero. Esta organización es apropiada cuando se espera utilizar muy a menudo una determinada relación en el acceso a los datos, ya que implementarla físicamente puede aumentar la eficiencia del sistema al acceder a los registros relacionados. Por ejemplo, si se quisiera acceder con frecuencia a una oficina junto con los empleados que trabajan en la misma, sería conveniente poner el registro de cada oficina junto con los registros de todos sus empleados contiguos en el disco, en un mismo fichero. Ya que los registros de todos los empleados de una misma oficina se encuentran físicamente juntos, y a continuación del registro con los datos de su oficina, el campo que hace referencia a la misma en los registros de los empleados no es necesario.

Para poder distinguir los registros de un fichero en el que se ha utilizado el agrupamiento, hay que añadir un campo a cada registro en donde se indique su tipo (suele ser el primer campo).

También es posible utilizar el agrupamiento en ficheros cuyos registros son todos del mismo tipo. Por ejemplo, en un fichero de empleados se puede tener los registros de los empleados agrupados por puesto de trabajo: todos los empleados con un mismo puesto están contiguos físicamente. Del mismo modo que antes, el campo que hace referencia al puesto se puede eliminar, pero hay que incluir un registro con el nombre del puesto delante del grupo de empleados.

Cuando se utiliza el agrupamiento, se favorecen los accesos a través de la relación en la que se basa dicho agrupamiento, pero se penalizan los accesos a través de cualquier otro campo. Ya que éste es un fichero ordenado (aunque de un modo especial), tiene las mismas ventajas e inconvenientes que los ficheros ordenados.

Índices

Los índices son estructuras de acceso que se utilizan para acelerar el acceso a los registros en respuesta a ciertas condiciones de búsqueda. Algunos tipos de índices, los denominados caminos de acceso secundario, no afectan al emplazamiento físico de los registros en el disco y lo que hacen es proporcionar caminos de acceso alternativos para encontrar los registros de modo eficiente basándose en los campos de indexación. Hay otros tipos de índices que sólo se pueden construir sobre ficheros que tienen una determinada organización.

En general, todas las organizaciones de ficheros descritas en los apartados anteriores se pueden utilizar como caminos de acceso secundarios. Sin embargo, los tipos de índices que más se utilizan son los que se basan en ficheros ordenados (índices de un solo nivel) y las estructuras en forma de árbol (índices multinivel, árboles B y árboles B+). Además, los índices se pueden construir mediante dispersión u otras estructuras de datos.

Índices de un solo nivel

Los índices de un solo nivel están ordenados y son algo similar al índice de palabras de un libro en donde cada palabra viene acompañada de una lista de números de página en donde aparece la palabra. Para hacer una búsqueda se puede recurrir al índice o bien hacer una búsqueda lineal a lo largo de todo el libro.

Un índice de un solo nivel es un fichero ordenado cuyos registros tienen dos campos: el campo sobre el que se define el índice denominado campo de indexación(un campo de los registros del fichero de datos) y una dirección de bloque en disco. Los valores del índice están ordenados, de modo que se puede utilizar la búsqueda binaria. Hay varios tipos de índices de un solo nivel: índices primarios, índices de agrupamiento e índices secundarios.

 

Índices primarios

Si un fichero está ordenado por un campo clave, el índice que se define sobre este campo es un índice primario.

Un índice primario es un fichero ordenado cuyos registros son de longitud fija y tienen dos campos: el campo de ordenación del fichero de datos (hay un valor único de este campo para cada registro) y un puntero a un bloque del disco (una dirección de bloque). El campo de ordenación se suele denominar clave. Hay una entrada (registro) en el índice por cada bloque del fichero de datos. Cada entrada tiene el valor de la clave del último registro del bloque y un puntero a dicho bloque.

Un índice primario es un ejemplo de índice no denso: hay una entrada por cada bloque de disco del fichero de datos, y no una entrada por cada registro. Un índice denso contiene una entrada por cada registro del fichero de datos. El fichero en donde se encuentra el índice necesita muchos menos bloques que el fichero de datos porque hay menos entradas que registros en el fichero de datos, y porque sus registros son más pequeños que los del fichero de datos. Por lo tanto, una búsqueda binaria sobre el índice visita menos bloques del disco que una búsqueda binaria sobre el fichero de datos.

Un problema importante con los índices primarios (como con cualquier fichero ordenado) es la inserción y el borrado de registros. De hecho, es incluso más grave, ya que hacer una inserción en el fichero de datos (que es un fichero ordenado) requiere el movimiento de registros en el fichero de datos y, además, hay que tocar el índice, ya que, seguramente, el movimiento de registros en el fichero de datos cambia el último registro de algunos bloques y, por tanto, hay que actualizar el índice. Se puede utilizar un fichero de desborde desordenado para reducir este problema. Otra posibilidad es utilizar una lista enlazada de registros de desborde, como en la dispersión. Los registros de cada bloque y su lista enlazada de desborde se pueden ordenar para mejorar el tiempo de acceso. El borrado de registros se puede gestionar mediante el uso de marcas de borrado.

Sobre un fichero ordenado por clave sólo puede definirse un índice primario.

Índices de agrupamiento

Si un fichero está ordenado por un campo no clave, un índice que se define sobre este campo es un índice de agrupamiento.

Si los registros de un fichero están ordenados según un campo no clave (no hay un valor único para cada registro), a ese campo se le llama campo de agrupamiento. Se puede crear un índice distinto, un índice de agrupamiento, para acceder más rápido al fichero a través de dicho campo. Un índice de agrupamiento es, también, un fichero ordenado con dos campos: el campo de agrupamiento por el que está ordenado el fichero y un puntero a un bloque de disco, por lo que también es un índice no denso. Hay una entrada en el índice por cada valor distinto del campo de agrupamiento, y el puntero señala al primer bloque que contiene un registro con dicho valor.

Nótese que la inserción y el borrado de registros siguen dando problemas, ya que es un fichero ordenado físicamente. Esto se puede subsanar si se reserva un bloque entero para cada valor distinto. Si hacen falta más bloques para un valor, se añaden y se van enlazando. Esto hace que la inserción y el borrado sean más simples.

Sobre un fichero ordenado por un campo no clave (campo de agrupamiento) sólo se puede definir un índice de agrupamiento.

Índices secundarios

Si un fichero está desordenado, cualquier índice de un solo nivel que se defina sobre él es un índice secundario. También es un índice secundario todo aquel que se define sobre un campo de un fichero ordenado que no es el campo de ordenación.

Un índice secundario también es un fichero ordenado con dos campos: el campo de indexación (cualquier campo del fichero de datos que no es el de ordenación) y un puntero a un bloque o un puntero a un registro. Pueden definirse muchos índices secundarios sobre un mismo fichero. Un índice secundario definido sobre un campo clave (un campo con valores distintos para cada registro) necesita una entrada por cada registro. El puntero puede ser al bloque en el que se encuentra el registro, o bien, al registro en sí. Un índice de este tipo es un índice denso.

Un índice secundario es más grande que un índice primario, ya que tiene mayor número de entradas. Sin embargo, la mejora que se introduce en el tiempo de búsqueda para un registro cualquiera es mayor para el índice secundario que para el primario, ya que hay que hacer una búsqueda lineal en el fichero de datos si el índice secundario no existe. Si un índice primario no existe, se puede hacer una búsqueda binaria sobre el fichero de datos (más rápida que la lineal).

También se puede crear un índice secundario sobre un campo no clave. En este caso, puede haber varios registros con el mismo valor en el campo de indexación. Hay varios modos de implementar un índice de este tipo:

· Incluir una entrada en el índice por cada registro (varias entradas tendrán el mismo valor), por lo que será un índice denso. El algoritmo de búsqueda binaria debe ser modificado.

· Utilizar registros de longitud variable en el índice, con un campo que contiene una lista de punteros. En el índice hay una entrada por cada valor distinto del campo de indexación, junto a una lista de punteros a todos los bloques que contienen registros con dicho valor. En este caso, también hay que modificar de modo apropiado el algoritmo de búsqueda binaria.

· Utilizar registros de longitud fija en el índice, con una entrada para cada valor del campo de indexación, pero crear un nivel extra de indirección para manejar punteros múltiples. En este índice no denso cada puntero señala a un bloque de punteros a registros; cada puntero a registro de ese bloque apunta a uno de los registros del fichero de datos con el mismo valor del campo de indexación. Si los punteros a registros no caben en un solo bloque, se puede usar una lista enlazada de bloques. El acceso a través del índice requiere un acceso adicional a bloque debido al nivel extra introducido, pero los algoritmos para buscar en el índice y los de inserción de nuevos registros en el fichero de datos son bastante simples. Además, los accesos que tienen condiciones de búsqueda complicadas (sobre varios campos) se pueden realizar trabajando sobre los punteros y no sobre los registros, siempre que haya un índice secundario por cada uno de los campos implicados en la condición. Esta es la técnica más utilizada.

Nótese que un índice secundario proporciona un orden lógico de los registros según el campo de indexación. Si accedemos a los registros en el orden de las entradas del índice secundario, los obtenemos en el orden del campo de indexación. Por lo tanto, no hay que hacer una ordenación externa para leer ordenadamente según dicho campo.

Índices multinivel

Los índices que se han descrito hasta ahora son ficheros ordenados en los que una búsqueda requiere aproximadamente accesos a bloques de disco, siendo el número de bloques que tiene el índice. Es el logaritmo en base dos porque en cada paso del algoritmo se reduce a la mitad el trozo del índice en el que se va a seguir buscando. Mediante los índices multinivel se pretende reducir mucho más el trozo del índice sobre el que seguir buscando, en concreto, se quiere dividir el tamaño no entre dos, sino entre el número de registros del índice que caben en un bloque. De este modo, se reduce el espacio de búsqueda mucho más rápidamente. Si el número de registros del índice que caben en un bloque es , entonces el buscar en un índice multinivel requiere aproximadamente , que es mucho menor si 2$" type="#_x0000_t75">.

Un índice multinivel está formado por un fichero índice, al que se denomina primer nivel o nivel base del índice. Este primer nivel es un fichero ordenado con un valor distinto del campo de indexación en cada entrada. Por tanto, se puede crear un índice primario sobre el primer nivel; este índice constituye el segundo nivel del índice multinivel. Ya que el segundo nivel es un índice primario, en él se tiene una entrada por cada bloque del primer nivel. Como todas las entradas de ambos niveles tienen el mismo tamaño (son registros de tamaño fijo siempre iguales), en un bloque caben siempre el mismo número de entradas: . Si el primer nivel tiene entradas, ocupa bloques, que es el número de entradas que se necesitan en el segundo nivel. El proceso se puede repetir sobre este nivel, si es necesario. El tercer nivel, que es un índice primario sobre el segundo nivel, tiene una entrada por cada bloque del segundo nivel, por lo tanto, el número de entradas del tercer nivel será . Nótese que se necesita un tercer nivel sólo si el segundo nivel ocupa más de un bloque. Este proceso se puede repetir hasta que todas las entradas de algún nivel quepan en un solo bloque. Cada bloque reduce el número de entradas del nivel anterior por un factor de , por tanto, un índice multinivel con entradas en el primer nivel tiene aproximadamente niveles, donde .

Este esquema multinivel se puede utilizar sobre cualquier tipo de índice, sea primario, de agrupamiento o secundario, siempre que el primer nivel tenga valores distintos en el campo de indexación y entradas de tamaño fijo.

Cuando el índice del primer nivel es denso, se puede saber si existe un registro con un valor dado en el campo de indexación (test de existencia) sin tener que acceder al fichero de datos, cosa que hay que hacer siempre en un índice no denso. Por lo tanto los índices multinivel reducen el número de accesos a bloque cuando se busca un registro a partir del valor de su campo de indexación. Pero todavía siguen los problemas en inserciones y borrados sobre los índices, ya que todos ellos (todos los niveles) son ficheros ordenados. Para mantener las ventajas que presentan los índices multinivel y reducir los problemas de las inserciones y borrados, los diseñadores adoptan a menudo un índice multinivel que deja espacio en cada uno de sus bloques para insertar nuevas entradas. Esto es lo que se denomina un índice multinivel dinámico y se suele implementar mediante estructuras de datos denominadas árboles B y árboles B+.

Árboles B y árboles B+

Los árboles B y los árboles B+ son casos especiales de árboles de búsqueda. Un árbol de búsqueda es un tipo de árbol que sirve para guiar la búsqueda de un registro, dado el valor de uno de sus campos. Los índices multinivel de la sección anterior pueden considerarse como variaciones de los árboles de búsqueda. Cada bloque o nodo del índice multinivel puede tener hasta valores del campo de indexación y punteros. Los valores del campo de indexación de ca