VII ORGANIZACIÓN FÍSICA DE LAS BASES DE DATOS

1. INTRODUCCIÓN

2. CONCEPTOS BÁSICOS

3. FICHEROS

4. IMPLEMENTACION DE BASES DE DATOS RELACIONALES

Las bases de datos, independientemente del modelo de datos que se

haya usado para su diseño, se almacenan físicamente como ficheros de

registros, los cuales se almacenan normalmente en discos magnéticos.

Durante este tema presentaremos cómo se organiza la base de datos en

su espacio de almacenamiento, y cuáles son las técnicas que se usan

para acceder a estos datos de la forma más eficaz y rápida posible.

125

VII1. introducción

La colección de datos que constituye una base de datos debe estar

almacenada en un medio de almacenamiento del ordenador. De esta

manera, el SGBD será capaz de recuperar, actualizar y procesar dichos datos

siempre que sea necesario. Los medios de almacenamiento en un ordenador

forman una jerarquía llamada jerarquía de almacenamiento o jerarquía de

memoria que contiene dos categorías principales:

• el almacenamiento primario: que incluye la memoria principal y la

memoria caché, medios de almacenamiento muy rápidos aunque

con capacidad limitada.

• el almacenamiento secundario: que incluye discos magnéticos,

discos ópticos, cintas, etc., todos ellos medios de almacenamiento

de grandes capacidades, aunque con un acceso mucho más lento.

Si bien el nivel de almacenamiento primario se caracteriza por ser más caro y

rápido que el secundario, podemos decir que dentro de cada uno de estos

niveles hay subniveles atendiendo también a estos criterios de coste y

velocidad.

Así, en el nivel de almacenamiento primario destacamos los subniveles:

• memoria caché: es la capa más cara de la jerarquía y se trata de

una memoria RAM estática, usada por la CPU para aumentar la

velocidad de ejecución de las máquinas. Volátil.

• memoria DRAM (RAM dinámica) o memoria principal: usada por la

CPU para mantener los programas y los datos. Más lenta que la

RAM estática aunque más barata. Volátil.

• memoria flash: memoria no volátil situada en el último subnivel,

dentro del nivel primario.

En el nivel de almacenamiento secundario se destaca:

• los discos magnéticos: siendo los más rápidos de este nivel.

• los discos CD-ROM (Compact Disk Read Only Memory) y su

versión reescribible CD-RW: basados en tecnología óptica con

lectura láser.

• las cintas: en el nivel más barato.

En cualquier caso, tanto el nivel de almacenamiento primario como el

secundario se usan para almacenar bases de datos. La memoria principal,

siempre que tenga capacidad suficiente, puede ser usada para albergar datos

(o parte de ellos), manteniendo siempre una copia de respaldo en memoria

secundaria para evitar los problemas que podría ocasionar la volatilidad de la

primera.

Sin embargo, en la gran mayoría de las ocasiones, el tamaño de la base de

datos impide su almacenamiento en una memoria primaria, y se mantiene en

almacenamiento secundario utilizando la memoria primaria para cargar

índices que aumentan la velocidad de acceso a los datos.

Dentro de la jerarquía del almacenamiento secundario, el principal soporte

usado hasta el momento para el almacenamiento de las bases de datos es el

disco magnético, y aunque puede que en el futuro los CD-ROM, DVD y otras

tecnologías usurpen el espacio que actualmente ocupa el disco magnético,

por el momento nos centraremos en este último como la principal fuente de

almacenamiento para bases de datos. Así en este tema nos centraremos en

el estudio y comprensión de las propiedades y características de los discos

magnéticos y la forma en que se pueden organizar los ficheros de datos en el

disco con el fin de obtener bases de datos con un rendimiento adecuado.

Las técnicas usadas para el almacenamiento de grandes cantidades de

información en disco deben ser conocidas tanto por los diseñadores como por

los administradores de bases de datos, así como, evidentemente por los

diseñadores e implementadores del SGBD.

VII2. conceptos básicos

Para comenzar con el estudio de las técnicas usadas en el almacenamiento

de datos en los discos magnéticos, es necesario recordar algunas de las

características principales que tienen estos medios. Comenzaremos por

repasar el hardware de los discos.

EL DISCO MAGNÉTICO

El disco magnético sirve para almacenar grandes cantidades de datos.

Aunque originalmente se construían de una sola cara, con el tiempo se

construyeron discos de dos caras, capaces de albergar información en las

dos superficies, e incluso formando paquetes de discos donde los datos se

organizan en varias superficies. La información almacenada en un disco se

encuentra en círculos concéntricos de pequeña anchura que se denomina

pista y que varían de diámetro conforme se alejan o se acercan al eje del

disco. En los paquetes de discos, todas las pistas de cada disco que tienen el

mismo diámetro se organizan formando un cilindro. El concepto de cilindro

es importante para el almacenamiento de una base de datos, ya que los datos

que se encuentran en mismo cilindro se pueden leer con mayor rapidez que si

se encuentran en varios cilindros, debido a que las cabezas lectoras del disco

son capaces de leer simultáneamente los datos de todas las pistas de un

mismo cilindro.

Puesto que un pista puede contener gran cantidad de información, ésta se

puede organizar a su vez en unidades menores llamadas sectores.

Finalmente, en la fase de formateo del disco, el sistema operativo realiza la

división de la pista en unidades de igual tamaño llamadas bloques de disco

o páginas.

El mecanismo hardware que se encarga de escribir o leer los bloques es la

cabeza de lectura/escritura del disco que se maneja gracias a un brazo

mecánico. Esta estructura junto con el disco, y el motor del disco, forman la

unidad de disco.

Además, el controlador de disco (situado generalmente en la unidad de

disco) controla y hace de interfaz entre ésta y el ordenador. El controlador

acepta instrucciones de E/S de alto nivel y realiza las acciones oportunas

para colocar el brazo y dar la orden de lectura o escritura. Una vez conocida

la dirección del bloque a la que se desea acceder, el controlador de disco

necesita un tiempo (entre 8 y 14 mseg) para colocar la cabeza sobre la pista

correcta. Este tiempo se conoce como tiempo de búsqueda. Una vez situada

la cabeza sobre la pista, es necesario que el disco gire hasta situar el inicio

del bloque bajo la cabeza generándose otro retardo llamado retado

rotacional o latencia. Por último deberá transcurrir un tiempo adicional para

la trasferencia de los datos, conocido como tiempo de transferencia de

bloque. Para mejorar la eficiencia en la transferencia de bloques, se suelen

transferir varios bloques consecutivos de la misma pista, e incluso del mismo

cilindro.

Figura 1. Partes principales del disco magnético

Resumiendo, el tiempo necesario para localizar y transferir un bloque es la

suma de:

tiempo de búsqueda + latencia + tiempo de transferencia de bloque

Este tiempo suele variar entre 12 y 60 mseg dependiendo del fabricante. Es

por tanto crucial la elección de un buen disco duro como uno de los factores

de éxito en la implantación de una base de datos.

TECNOLOGÍA RAID

Pese a que la tecnología en el desarrollo de dispositivos de almacenamiento

secundario (especialmente discos duros) ha evolucionado espectacularmente,

las prestaciones que se pueden alcanzar con una única unidad de disco

resultan insuficientes para el almacenamiento eficiente de grandes cantidades

de datos. Es por este motivo por el que se ha desarrollado la tecnología

conocida con el nombre de RAID (Redundant Array of Inexpensive Disk).

La idea original de RAID fue la de igualar los rendimientos de los discos a los

de los procesadores y memorias principales. Mientras la capacidad de la RAM

se cuadruplica cada dos o tres años, los tiempos de acceso a disco apenas

mejoran un 10% al año, y los tiempos de transferencia menos de un 20%.

Como solución RAID plantea crear un array de pequeños discos

independientes que actúan como un único disco lógico de alto rendimiento.

Además, se utiliza una estrategia de almacenamiento conocida como data

striping (franjeo de datos) que se basa en el paralelismo. Según esta técnica

un mismo fichero se distribuye entre varios discos para que su lectura

completa se realice simultáneamente desde todos los discos. El acceso en

paralelo a todos los discos es mucho más rápido que un acceso secuencial a

uno de ellos. De ahí que las lecturas y escrituras de los datos resulten mucho

más rápidas.

RAID tiene como objetivo principal mejorar el rendimiento de los discos

magnéticos, aunque sin olvidar un aspecto fundamental que es la fiabilidad.

Para un array de n discos, la posibilidad de fallo es n veces mayor que para

un único disco. El mantenimiento de una única copia de los datos en este tipo

de estructura conllevaría una importantísima pérdida de fiabilidad. La solución

es introducir redundancia de datos.

Una técnica que permite la redundancia es lo que se conoce como mirroring

o shadowing, también conocido en español como espejo. Según esta

técnica, los datos se escriben físicamente en dos discos diferentes de forma

redundante. Al leer los datos, éstos se recuperan del disco que tenga menos

carga de peticiones, o que sea más rápido. Si un disco falla, se usa el otro

hasta que se repare el primero.

ORGANIZACIÓN Y NIVELES RAID

Hay diferentes organizaciones RAID atendiendo a la forma de hacer el franjeo

de los datos y a la forma de acceder a los datos redundantes. Estas

organizaciones se jerarquizan en 7 niveles: desde RAID nivel 0 hasta RAID

nivel 6.

• RAID 0 no tiene redundancia de datos. De todas las organizaciones

RAID, ésta tiene el mejor rendimiento en escritura ya que no tiene que

duplicar modificaciones. Sin embargo, el rendimiento en lectura es

menor.

• RAID 1 ya plantea la redundancia de datos mediante discos espejo. El

rendimiento en lectura es mayor que en RAID 0 debido a que la

petición de lectura se aplica al disco que sea más rápido en cada

momento.

• RAID 2 optimiza el almacenamiento de información redundante al

almacenar los códigos de detección de error (bits de paridad) una

única vez (no una para cada copia como ocurre en RAID 1) comunes.

De esta manera, un ejemplo concreto de 4 discos, sólo necesitaría 3

discos espejo (en lugar de los 4 que necesita RAID 1).

• RAID 3 a RAID 6 optimizan RAID 2 con diferentes estrategias para

detección de errores que minimizan el número de discos necesarios

aumentando el rendimiento del sistema sin perder fiabilidad.

•

•

Como conclusión para este apartado podríamos concluir que el disco

magnético es una de las fuentes de almacenamiento secundario más

extendidas para el almacenamiento de bases de datos. Sin embargo, la

organización física de las bases de datos

129

evolución tecnológica del disco magnético no ha sido tan espectacular como

lo ha sido la evolución tecnológica de la memoria RAM o de los procesadores.

Por este motivo ha sido necesario la introducción de técnicas de

almacenamiento redundante que han conseguido mejorar los rendimientos de

estos dispositivos. En concreto, la organización RAID es una de las más

extendidas en los servidores que tienen como principal misión el

almacenamiento de grandes bases de datos.

Una vez sentados los fundamentos del “hardware” que se usa para la

implementación de las bases de datos, introduciremos algunos conceptos

sobre cómo se almacena físicamente un fichero.

VII3. ficheros

El fichero es la organización básica de almacenamiento en disco, y por tanto

es la organización empleada para la implementación de una base de datos.

Para introducir el concepto de fichero es necesario introducir previamente el

concepto de registro.

VII3.1. registro

Un registro es una colección de valores o elementos de datos relacionados

donde cada valor está formado por uno o más bytes y corresponde a un

determinado campo del registro.

Por regla general, cada registro representa a una entidad, y cada valor de

campo en ese registro representa a un atributo de esa entidad. La lista de

nombres asociados a cada campo y los tipos de datos que se almacenan en

ellos constituyen lo que se llama el formato del registro.

Actualmente las bases de datos también incluyen grandes objetos que no

pueden ser estructurados en campos como imágenes, secuencias de video,

secuencias de audio, o incluso texto libre. Estos objetos se conocen como

BLOB (Binary Large OBjects) y por lo general se almacenan aparte de su

registro, en un área de bloques de disco, y se incluye un puntero desde el

registro al BLOB.

VII3.2. fichero

Un fichero se define como una secuencia de registros.

Si todos los registros de un fichero tienen la misma longitud se les conoce

como registros de longitud fija. Sin embargo, si cada registro tiene una

longitud diferente hablaremos de registros de longitud variable. Esto nos

proporciona diferentes organizaciones para el almacenamiento de los

registros:

a) almacenamiento de registros de longitud fija: el registro tiene una

longitud conocida y cada campo ocupa una posición conocida

dentro del registro. Para acceder a alguno de ellos únicamente es

BD1 2006-2007

130

necesario conocer su posición de inicio y de fin del campo en el

registro.

1 10 15 20 33

Campo Posición inicio Posición fin

NOMBRE 1 9

CÓDIGO 10 14

DEPARTAMENTO 15 19

DIRECCIÓN 20 33

b) almacenamiento de registros de longitud variable formados por

campos de longitud fija y campos de longitud variable: se utilizan

caracteres especiales para delimitar el final de un campo de longitud

variable, y se usan las longitudes conocidas de los campos de

longitud fija para conocer sus límites.

1 n n+6 n+10

Campo Posición inicio Posición fin

NOMBRE 1 n-1

Carácter fin 􀁊 N n

CÓDIGO n+1 n+5

DEPARTAMENTO n+6 n+10

DIRECCIÓN n+11 m-1

Carácter fin 􀁊 M m

c) almacenamiento de registros de longitud variable formados por

campos de longitud variable y algunos de ellos opcionales: La

existencia de campos optativos obliga a almacenar junto con cada

campo el nombre del campo. Así se introducen tres tipos de

caracteres especiales separadores: separador del nombre del

campo, indicador de fin de campo e indicador de fin de registro.

Carácter separador de nombre de campo

Carácter indicador fin de campo

Carácter indicador fin de registro

Los ficheros constituyen la unidad básica en el almacenamiento físico de las

bases de datos. A nivel práctico, podemos considerar que cada tabla de un

esquema lógico definida sobre el modelo relacional se convertirá en un

fichero (o conjunto de ficheros) que será manejado por el sistema operativo

desde el SGBD.

A L B E R T O A L B 0 1 A DMONMA Y OR, 2 4 - 3 D

A L B E R T O A L B 0 1 A DMONMA Y OR, 2 4 - 3 D

n o m b r e B A L E RT O d i r e c c i o n M A Y O R , 2 4 - 3 D

organización física de las bases de datos

131

VII3.3. operaciones con ficheros

Las operaciones que se realizan con los ficheros se pueden clasificar en

operaciones de recuperación y operaciones de actualización, encargadas

de leer y de escribir datos respectivamente. En cualquiera de los dos casos

es necesario realizar una selección previa del registro con el que se quiere

trabajar mediante una condición de selección o filtro que especifica los

criterios que debe satisfacer el registro o registros con los que se va a operar.

Quien se encarga de acceder físicamente a los ficheros, y por tanto, quien

ejecuta las operaciones de recuperación y actualización de ficheros es el

sistema operativo. Sin embargo, la condición de búsqueda debe establecerse

desde fuera del sistema operativo. Cuando se trabaja con una base de datos,

el encargado de establecer esa condición de selección es el propio SGBD.

Una condición de selección simple puede ser una comparación de igualdad

de un valor para un campo, por ejemplo, dni=’22233334’.

Sin embargo, en bases de datos es frecuente realizar selecciones con

múltiples condiciones (ya conocemos la complejidad selectiva que puede

llegar a tener una sentencia SELECT de SQL). En este caso, el SGBD debe

descomponer la selección en sus múltiples condiciones para acceder al

registro adecuado. Por ejemplo, si un usuario solicita “empresas de Murcia

que tienen más de tres empleados”, su pregunta la traducirá a una consulta

SQL como:

SELECT * FROM empresas WHERE ciudad=’murcia’ AND empleados>3

Esta consulta se introduce en el SGBD. Sin embargo, el sistema operativo no

podrá interpretar SQL. Por este motivo, el SGBD tendrá que traducir esta a

consulta una operación de recuperación que deberá obtener el registro (o

registros) que cumpla las dos siguientes condiciones de selección:

a) campo ciudad del fichero empresas = ‘murcia’

b) campo empleados del fichero empresas > 3

Cuando hay varios registros que satisfacen la condición de selección,

inicialmente el sistema operativo únicamente le devuelve al SGBD el primer

registro que cumple con esa selección, aunque le proporciona un puntero al

siguiente para que el SGBD pueda ir recorriendo la cadena de registros

seleccionada.

Para realizar esta búsqueda, la mayoría de los SGBD disponen de las

siguientes instrucciones implementadas a través del sistema operativo:

Abrir: prepara un fichero para su lectura o escritura. Si se puede, carga en

memoria principal los bloques del disco que contienen al fichero, si no puede

(por falta de memoria) cargará una parte del fichero (al menos la cabecera).

Además sitúa el puntero al principio del fichero para iniciar la operación.

Volver al principio: pone el puntero de un fichero abierto en el principio.

Buscar: localiza el primer registro que satisface una condición de búsqueda,

y transfiere ese bloque de disco a memoria principal (si no está ya).

Leer: copia el contenido del registro en una variable del programa.

Buscar siguiente: busca el siguiente registro que satisface la condición de

búsqueda especificada en la última operación buscar efectuada. Carga el

bloque en memoria (si no lo tiene ya).

Eliminar: elimina el registro actual del fichero y actualiza el fichero en el

disco.

Modificar: modifica valores de algunos campos del registro y actualiza el

fichero en el disco.

BD1 2006-2007

132

Insertar: inserta un nuevo registro en el fichero localizando el bloque donde

se debe insertar, trasfiriéndolo a memoria principal, insertándolo, y volviendo

a escribir el bloque en el disco.

Cerrar: finaliza el acceso al fichero liberando la memoria principal ocupada

por él.

VII3.4. organizaciones de ficheros usadas para

bases de datos

En el almacenamiento de los datos, la organización interna del fichero tiene

también su importancia. La organización de los ficheros debe facilitar la

localización de los registros, especialmente en las búsquedas que se realizan

sobre determinados campos. Por ejemplo, si deseo buscar un cliente por su

dni, el fichero que contiene a los clientes de la base de datos debería estar

ordenado físicamente por este valor o definir un índice sobre este campo. Sin

embargo, si sobre el mismo fichero deseo buscar los clientes que residen en

una misma ciudad, se necesitaría agrupar físicamente los datos por el campo

ciudad para obtener una respuesta eficiente. A priori, esta organización no es

compatible con la anterior, sin embargo, vamos a estudiar a continuación

diversos tipos de organización que pueden ser útiles para hacer compatibles

dichas organizaciones.

Ficheros de montículo (heap)

Los ficheros de montículo o heap constituyen el tipo más simple de

organización. Los registros se colocan en el mismo orden en el que se

insertan. Esta organización simplifica algunas de las operaciones aunque

otras se hacen más complejas.

VII3.4.1.1. Inserción

Cada registro nuevo se inserta al final del fichero de la siguiente forma:

a) se consulta en la cabecera del fichero la dirección física del último

bloque de disco para ese fichero,

b) se copia el bloque a memoria principal,

c) se añade el nuevo registro,

d) se reescribe el bloque en el disco,

e) se actualiza la cabecera del fichero con la dirección del último

bloque de disco (si hace falta).

La operación se realiza de forma sencilla y eficiente.

organización física de las bases de datos

133

VII3.4.1.2. Búsqueda

Por el contrario, en este tipo de organización la búsqueda de un determinado

registro de acuerdo a una condición de búsqueda se realiza comprobando

registro a registro, lo que supone físicamente una lectura bloque a bloque del

disco. En un fichero de n bloques, se requiere realizar n/2 comprobaciones

por término medio.

VII3.4.1.3. Borrado

Para eliminar un registro hay que:

a) buscar el bloque de disco donde se encuentra el registro,

b) copiar el bloque a memoria principal,

c) eliminar el registro,

d) rescribir el bloque en disco.

Solamente el primero de los pasos (la búsqueda) ya tiene complejidad

suficiente para hacer la operación poco eficiente. Además, será necesario

pasar un proceso periódico de reorganización del fichero ya que los huecos

que quedan libres por las eliminaciones nunca se rellenan por lo que se

desperdicia espacio.

VII3.4.1.4. Actualización

La actualización de un registro se realiza según los siguientes pasos:

a) buscar el bloque de disco donde se encuentra el registro,

b) copiar el bloque a memoria principal,

c) modificar el registro,

d) rescribir el bloque en disco.

El proceso de nuevo se complica en el primer paso, pero también tiene una

complicación añadida cuando se usan registros de longitud variable. Si un

registro se modifica ampliando su longitud puede que ya no tenga espacio

suficiente en su bloque para poder albergarlo. En ese caso, la operación de

actualización se convertiría en dos operaciones: borrado del registro antiguo +

inserción de uno nuevo al final del fichero.

VII3.4.1.5. Lectura

La lectura del fichero según un determinado criterio (por ejemplo, por orden

alfabético del nombre, o por orden de dni) requiere hacer una copia del

fichero según este orden, o bien, si el tamaño es excesivo utilizar ficheros de

índices externos.

BD1 2006-2007

134

Ficheros ordenados (o secuenciales)

Los ficheros ordenados se caracterizan por tener un orden físico según los

valores de uno de sus campos, llamado campo de ordenación. Si el campo

de ordenación tiene además propiedades de identificador (es decir, siempre

tiene valor y no se repite) se conoce como clave de ordenación del fichero.

Figura 3. Fichero secuencial

Los ficheros ordenados plantean ciertas ventajas sobre los ficheros de

montículo:

a) la lectura de registros en el orden físico almacenado es

extraordinariamente eficiente,

b) los accesos a registros en orden consecutivo no requiere cambiar

de bloque en la mayoría de los casos, por lo que no se efectúan

muchos accesos a disco,

c) las condiciones de búsqueda que afectan a valores de un campo

clave de ordenación son muy eficientes cuando se emplean

organización física de las bases de datos

135

estrategias de búsquedas binarias. Una búsqueda binaria accede

normalmente a log2(n) bloques, encuentre o no el registro que

busca entre n bloques.

Sin embargo, sigue planteando algunas desventajas. Analicemos una a una

las diferentes operaciones.

VII3.4.1.6. Inserción

La inserción es una operación costosa ya que se debe conservar el orden

físico de los registros. Se debe:

a) encontrar la posición para el nuevo registro en el fichero según el

campo de ordenación,

b) abrir espacio en el bloque correspondiente, desplazando el resto de

los registros.

Esta última fase de la operación es especialmente dura, ya que significa que

se tiene que leer y volver a escribir una media de n/2 bloques para un fichero

de n bloques.

VII3.4.1.7. Búsqueda

La búsqueda por un campo de ordenación ya sabemos que es

extremadamente eficiente, sin embargo la búsqueda por cualquier otro tipo de

campo se convierte en una tarea de búsqueda lineal como lo era en el fichero

de montículo.

VII3.4.1.8. Borrado

El borrado se realiza exactamente igual que en el fichero de montículo. Sigue

siendo una operación costosa. La única diferencia estriba en que la búsqueda

del registro a borrar será más eficiente si se busca por el campo de

ordenación.

VII3.4.1.9. Actualización

La actualización se realiza de la misma manera que en los ficheros de

montículo. Sólo un par de diferencias:

a) el proceso de búsqueda es más eficiente,

b) si lo que se ha modificado es el valor del campo de ordenación,

entonces se convierte en una operación de borrado + inserción del

registro en su nueva ubicación, con la complejidad que ello conlleva.

BD1 2006-2007

136

VII3.4.1.10. Lectura

La lectura secuencial del fichero ordenado es muy eficiente siempre que se

siga el campo de ordenación. En cualquier otro caso es igual que la lectura de

un fichero de montículo.

Ficheros de direccionamiento calculado (hashing)

Los ficheros de direccionamiento calculado, también conocidos como

dispersos o hashing, proporcionan un acceso muy rápido a los registros bajo

ciertas condiciones de búsqueda. La condición de búsqueda se realiza sobre

un único campo del registro conocido como campo de direccionamiento

calculado. Este campo también se llama clave de direccionamiento

calculado. El funcionamiento de esta organización se basa en establecer una

función h llamada función de direccionamiento calculado, que una vez

aplicada sobre el valor del campo de direccionamiento calculado de un

registro produciría la dirección del bloque de disco en el que se almacena el

registro. Una vez obtenido el bloque se copia a memoria principal y se realiza

la búsqueda del registro dentro del bloque.

Una función de direccionamiento calculado muy común para campos de

direccionamiento calculado con valor numérico es:

h(K) = K mod M

donde K es el valor del campo, y M es el número total de bloques de disco

donde se almacenan los registros.

Así por ejemplo, si se van a usar 20 bloques, y el campo de direccionamiento

calculado DNI tiene valor = 21987239, la función h devuelve

h(21987239)= 21987239 mod 20 = 19

Esto indicaría que el registro correspondiente al valor de dni 21987239 se

almacena en el bloque número 19. A partir de ahí ya sólo resta conocer la

dirección física de ese bloque y copiarlo a memoria principal.

Figura 4. Localización física de los bloques calculados en disco

Los ficheros basados en el direccionamiento calculado plantean muchas

ventajas respecto a los de montículo o a los ordenados.

a) Las búsquedas se realizan de manera rápida en cualquiera de los

campos de búsqueda.

organización física de las bases de datos

137

b) Los datos se insertan en el disco de forma dispersa, lo cual permite

fácilmente las operaciones de borrado, inserción y actualización, sin

necesidad de reorganizar el fichero.

VII3.5. estructuras de índices para ficheros

En el apartado anterior hemos podido comprobar que hay diferentes

organizaciones primarias para almacenar la información: organización de

montículo (no ordenada), organización ordenada, y organización de

direccionamiento calculado (dispersa o hashing).

Sin embargo, estas estructuras pueden no ser suficientes para las

necesidades de una base de datos. En muchos casos es necesario hacer uso

de unas estructuras de acceso auxiliares llamadas índices que se emplean

para aumentar la velocidad de recuperación de registros bajo ciertas

condiciones de búsqueda.

Los índices proporcionan caminos alternativos para acceder a los registros sin

que se vea afectada la posición física que los registros ocupan dentro del

disco.

Los campos de un registro que se utilizan para construir un índice se

denominan campos de indexación.

Cualquier campo del registro puede ser un campo de indexación, y un mismo

fichero puede incluir múltiples índices (es decir más de un campo de

indexación por registro).

El funcionamiento del índice es el siguiente: cuando se produce una condición

de búsqueda que afecta a un campo de indexación, en lugar de acceder

directamente al fichero de datos para iniciar la búsqueda (según la

organización propia del fichero de datos: montículo, ordenada o

direccionamiento calculado), se accede previamente a un fichero (llamado

índice o fichero de índice) donde se encuentran los valores del campo de

indexación correspondiente ordenados según la organización propia del

fichero de índice, junto con un puntero que señala físicamente al bloque de

disco que alberga a ese registro en el fichero de datos. El acceso al registro

ya es una tarea trivial según hemos visto.

El uso de índices permite:

a) realizar búsquedas eficientes en ficheros de datos organizados en

montículo (sin índices recordemos que se trataba de una lenta

búsqueda bloque a bloque)

b) acceder de forma eficiente mediante condiciones de búsqueda que

afectan a cualquier campo en un fichero ordenado (recordemos que

esta organización sólo se accedía de forma eficiente cuando la

búsqueda se realizaba sobre el campo de ordenación, y éste era

único para un determinado fichero).

c) acceder de forma eficiente mediante condiciones de búsqueda que

afectan a cualquier campo en un fichero con direccionamiento

calculado (éste accede de forma eficiente cuando la búsqueda se

refiere al campo de direccionamiento calculado, pero las búsquedas

por otros campos se tienen que realizar secuencialmente).

La implementación de los ficheros de índice se realiza mediante organización

ordenada, o mediante el empleo de estructuras de datos en árbol (árboles

binarios) que optimizan las búsquedas.

BD1 2006-2007

138

Figura 5. Funcionamiento del índice sobre un fichero con organización ordenada

VII4. implementación de bases de

datos relacionales

Las bases de datos relacionales, como cualquier otra base de datos, necesita

una estructura física de almacenamiento basada en el uso de ficheros.

Aunque los ficheros basados en direccionamiento calculado tienen un acceso

muy potente, su implementación es compleja y no siempre es rentable su

coste.

Para la implementación de tablas que tienen mucha volatibilidad, es decir, que

crecen y decrecen rápidamente, puede ser especialmente aconsejable el uso

de ficheros de direccionamiento calculado. Sin embargo, para las tablas que

tienen poca movilidad puede ser suficiente con ficheros de montículo o

ficheros ordenados.

El apoyo de ficheros de índice que permiten localizar los registros

rápidamente siguiendo cualquier condición de búsqueda, se hace

organización física de las bases de datos

139

especialmente necesario cuando se implementan las bases de datos

relacionales. Pensemos que la instrucción SELECT de SQL permite realizar

búsquedas que afectan a cualquier columna de la tabla, por lo que se traduce

físicamente en condiciones de búsqueda que afectan a cualquier campo del

registro.

En general, el uso de uno u otro tipo de organización de ficheros depende de

que el SGBD permita su uso (no todos los SGBD implementan ficheros de

direccionamiento calculado), y del criterio que tome el administrador de la

base de datos acerca de la implementación concreta de cada tabla. El uso o

no de ficheros de índice que mejoren la velocidad de búsqueda de registros

queda también a juicio del propio administrador.

Para facilitar la tarea del administrador, el SGBD suele mostrar estadísticas

de uso y tiempos de acceso a cada uno de los ficheros que implementan la

base de datos. Con estos datos, el administrador se encargará de hacer los

ajustes correspondientes (operación conocida como tunning) tomando las

oportunas decisiones respecto a la organización de los ficheros.