Capitulo 5

5 TEMA 5. ORGANIZACIÓN FISICA DE UNA BASE DE DATOS

5 TEMA 5. ORGANIZACIÓN FISICA DE UNA BASE DE DATOS...................... 1

5.1 Organización de archivos ................................................................................. 2 5.1.1 Dispositivos de almacenamiento secundario............................................ 2 5.1.2 Acceso a la Base de Datos........................................................................ 4

5.2 Ficheros secuenciales ....................................................................................... 5 5.2.1 Ficheros secuenciales física y lógicamente .............................................. 6 5.2.2 Ordenación de ficheros secuenciales. Fusión. .......................................... 6

5.3 Ficheros de acceso aleatorio. Hashing.............................................................. 8 5.3.2 Acceso aleatorio ....................................................................................... 9 5.3.3 Funciones de hashing ............................................................................. 10 5.3.4 Tratamiento de colisiones....................................................................... 11

5.4 Ficheros indexados ......................................................................................... 12 5.4.1 Organización secuencial indexada (ISAM)............................................ 13 5.4.2 Almacenamiento masivo virtual. VSAM. .............................................. 16

5.5 Arboles B........................................................................................................ 17 5.5.1 Propiedades de los árboles B de orden n ................................................ 18 5.5.2 Capacidad de un árbol B......................................................................... 19 5.5.3 Operaciones sobre un árbol B................................................................. 19

5.6 Árboles B+...................................................................................................... 20 5.7 Árboles B*...................................................................................................... 21

Tema 5: Organización física de una base de datos 1

5.1 Organización de archivos

Las bases de datos, debido a su tamaño, se almacenan en dispositivos de almacenamiento secundario de mucha mayor capacidad que la memoria principal, pero que por el contrario son mucho más lentos (varios órdenes de magnitud). Los principales dispositivos de almacenamiento secundario o masivo son los discos, los tambores y las cintas, y se basan todos ellos en las propiedades de polarización magnética de ciertos elementos.

Una base de datos contiene información sobre objetos y hechos de la realidad. Los objetos representados poseen propiedades o atributos que los definen e identifican. Una instancia de un objeto real se representa por un registro en la base de datos. Las propiedades del objeto se representan a través de campos del registro. Un fichero es una colección de todas las instancias almacenadas de un mismo objeto.

5.1.1 Dispositivos de almacenamiento secundario

Un dispositivo de almacenamiento es de acceso directo si es posible acceder a sus registros en cualquier orden, al azar, tanto en escritura como en lectura. Por el contrario, un dispositivo es de acceso secuencial si sólo es posible acceder a un registro tras haber accedido a todos los anteriores. Los discos y los tambores son dispositivos de acceso directo, mientras que las cintas son de acceso secuencial.

Los discos son los dispositivos más utilizados. Los discos se presentan en unidades separadas o formando una pila de discos con movimiento solidario. Esta estructura multiplica la capacidad de almacenamiento, manteniendo los mismos rendimientos ya que cada cara de cada disco posee una cabeza de lectura/escritura propia.


En los discos se distinguen los siguientes elementos:

• Pista: contiene datos que pueden ser escritos o leídos sin necesidad de que cambie la posición de la cabeza. Tienen forma de anillos circulares.

• Cilindro: en dispositivos con múltiples discos, es el grupo de pistas que pueden ser accedidas sin necesidad de cambiar la posición del mecanismo de acceso.

• Sector: las pistas se dividen en sectores. Un sector es un bloque de datos que se lee o escribe en una única operación de lectura/escritura. También reciben el nombre de registros físicos, que no deben confundirse con los registros de la base de datos. El tamaño de los sectores suele ser mayor que el de los registros de la base de datos, y por lo tanto, en un mismo registro físico se almacenan varios registros lógicos.

Registro de datos

Zona entre registros

Pista

Registro físico

Sobre los discos se pueden almacenar ficheros con organización secuencial, aunque el disco tiene estructura bidimensional (cilindro, superficie son las coordenadas). Para ello, se puede ver el disco como una estructura lineal, donde el orden de recorrido viene dado por (cilindro, superficie) {(1,1), (1,2), …, (1,n), (2,1), (2,2), …, (m,n)}. De esta forma, la cabeza de lectura/escritura no se mueve mientras se leen o escriben las distintas superficies de un cilindro, optimizando los tiempos de acceso.

Los factores que afectan directamente a la velocidad con la que los datos se transfieren de y desde el disco son los siguientes:

• Tiempo de posicionamiento (P) (seek time), es el tiempo necesario para mover la cabeza de lectura/escritura desde su posición actual a la nueva dirección del cilindro.


• Tiempo de activación de la cabeza, es el tiempo necesario para activar electrónicamente la cabeza que se encuentra sobre la superficie cuando ocurre la transferencia de datos. Es despreciable frente a otros tiempos.

• Retraso de rotación (R), o tiempo de latencia, es la cantidad de tiempo que necesita el bloque seleccionado para rotar la cabeza, de forma que la transferencia de datos pueda comenzar.

• Velocidad de transferencia (D), es la cantidad de tiempo necesario para transferir los datos desde el disco hacia o desde la memoria principal.

En conclusión, el tiempo de transferencia de datos previsto que se estima para transferir un bloque de datos de tamaño L bytes es:

T = P + R / 2 + L / D

Algunos sistemas operativos permiten olvidarse de la estructura física de los dispositivos de almacenamiento, gestionando directamente las operaciones de entrada/salida, mientras que para el programador la memoria principal tiene capacidad ilimitada. Para ello se utilizan técnicas de paginación o memoria virtual.

El conocimiento del rendimiento de las operaciones de lectura/escritura en disco nos permitirán valorar adecuadamente los rendimientos de las técnicas de organización de ficheros que serán estudiadas en los siguientes capítulos.

5.1.2 Acceso a la Base de Datos

Podemos estudiar la gestión de dispositivos de almacenamiento secundario como una pila de capas especializadas que controlan ciertos aspectos de los procesos de almacenamiento y recuperación de información.

SGBD Registro

solicitado Petición de

registro

Petición de página

Operación E/S

B

Figura: Estructura f

Tema 5: Organización física de una

Gestor de ficheros

Página solicitada

Gestor de Disco

Datos del disco

ase de datos almacenada

uncional por capas del nivel interno

base de datos 4

El SGBD decide el registro que necesita y se lo solicita al gestor de ficheros. También se pueden hacer peticiones de grupos de registros almacenados contiguamente. Para el SGBD la base de datos consiste en una colección de registros almacenados. Los detalles sobre el almacenamiento de los datos están ocultos en los niveles inferiores.

Los ficheros poseen un identificador único que puede ser un nombre o un número. El gestor de ficheros trata a los ficheros como una colección de páginas. La página es la unidad de entrada/salida que se transfiere entre disco y memoria principal en una operación de entrada/salida (tamaños típicos de páginas son de 1K a 4K). Las páginas poseen un identificador unívoco (también las hemos llamado registro físico).

El gestor de ficheros decide en qué página está localizado el registro buscado por el SGBD, y se la solicita al gestor de disco. Un gestor de ficheros aparece en todos los sistemas operativos. Es posible, sin embargo, que los requisitos de la base de datos no sean cubiertos totalmente por él, y sea necesario completarlo o sustituirlo por un gestor de ficheros especializado para la base de datos.

Finalmente, el gestor de disco determina la posición física de la página en el disco y realiza las operaciones necesarias para almacenarla o recuperarla.

Como ya hemos dicho, el rendimiento de los dispositivos de almacenamiento masivo es varios órdenes de magnitud peor que el de la memoria principal (10.000 a 100.000 veces más lento). Así pues, uno de los principales objetivos de un sistema de bases de datos es minimizar el número de accesos a disco. En los siguientes capítulos veremos diversas técnicas que nos permitirán alcanzar, aunque sólo sea parcialmente, este objetivo.

5.2 Ficheros secuenciales

Un fichero secuencial está organizado físicamente de tal forma que cada registro es adyacente al siguiente registro del mismo fichero. No existe la posibilidad de acceder directamente a los registros y se accede a ellos en el orden en que fueron escritos en el fichero. Para localizar un registro es necesario examinar cada registro hasta encontrar el deseado.

Los ficheros en dispositivos de acceso secuencial como las cintas o las tarjetas perforadas tienen organización secuencial. Sin embargo, también es posible organizar ficheros en forma secuencial sobre dispositivos de acceso directo.

Para acceder a un fichero con organización secuencial:

Mientras condición Leer registro en posición actual Procesar registro Adelantar a la siguiente posición

Las características principales de los archivos secuenciales son:

• No se necesitan métodos elaborados para determinar la posición de un registro.


• Es una organización eficiente si se realiza un tratamiento sobre todos los registros.

La organización secuencial es conveniente para el procesamiento exhaustivo de todos los registros de un fichero (p. ej. cálculo de nóminas, listados completos de empleados, actualización de parámetros, recuento de registros, cálculo de medias, varianzas, etc.

5.2.1 Ficheros secuenciales física y lógicamente

Los ejemplos que hemos dado corresponden a ficheros con organización físicamente secuencial: los registros están almacenados de forma contigua.

Para estos ficheros se cumple:

• No se necesita calcular una dirección

• Se necesita un mínimo movimiento físico para moverse de un registro al siguiente

• Existen ciertas ventajas en el bloqueo de transacciones

Otras veces es conveniente para el procesamiento tratar los registros de un fichero como si estuvieran almacenados secuencialmente, aunque en realidad no lo estén. Para ello se necesita que el fichero esté organizado lógicamente en forma secuencial, aunque los registros estén dispersos en la unidad de almacenamiento. Para organizar un fichero como lógicamente secuencial es necesario que cada registro indique la posición del siguiente registro mediante un puntero. En este caso, el acceso a un registro se realizará del siguiente modo:

Mientras condición Leer registro en posición del puntero Procesar registro Obtener posición del siguiente registro y adelantar el puntero

5.2.2 Ordenación de ficheros secuenciales. Fusión.

Los métodos de búsqueda y ordenación clásicos son:

• Búsqueda binaria • Ordenación por selección • Ordenación por inserción • Ordenación por intercambio • Ordenación rápida (quicksort) • Ordenación por el método de la burbuja • …

Han sido diseñados para el ordenamiento de información contenida en memoria principal rápida. Los ficheros de datos se almacenan en memoria secundaria, y en la mayoría de los casos son demasiado grandes para ser volcados en memoria principal. Se necesitan entonces nuevos medios para buscar y ordenar información en ficheros. A estos métodos se les llaman búsquedas y ordenaciones externas.


Los métodos de ordenación externa se basan en ordenar en memoria principal y por métodos clásicos pequeños fragmentos de fichero externo. Posteriormente se combinan los fragmentos ordenados para obtener el ordenamiento completo del fichero. El proceso por el que se combinan fragmentos ordenados para formar un conjunto mayor ordenado se denomina fusión. De modo más formal, fusión es la combinación de dos o más ficheros ordenados para formar un solo fichero ordenado.

El procedimiento de ordenación consiste en dividir el fichero a ordenar en n (n>=2) partes. Se repite la división de cada una de las partes obtenidas en n nuevas partes hasta que el tamaño sea suficientemente pequeño para poder ubicarse en memoria principal. En este momento se ordenan por alguno de los métodos de ordenación clásicos y se combinan mediante fusión siguiendo el camino inverso al seguido en la descomposición. La ordenación-fusión es pues recursiva, y su rendimiento del orden O(n log n).

5.2.2.1 Fusión 2-vías

Sean dos ficheros ordenados en orden creciente. Para unirlos, cogemos el primer registro de cada uno de los ficheros. Grabamos en el fichero de salida el registro con clave menor. Seleccionamos el siguiente registro del fichero de entrada al que pertenecía este registro con menor clave. Procedemos de esta forma hasta que uno de los dos ficheros de entrada se vacía. En ese momento, volcamos el resto del otro fichero de entrada en el de salida.

35 33 32 20 19 17

28 26 25 23 15 12

35 33 32 20 19 17

15 12

28 26 25 23

35 33 32

20 19 17 15 12

28 26 25 23

5.2.2.2 Fusión natural n-vías

Sea un fichero desordenado. Tomamos bloques de tamaño k que se ordenan en memoria principal y que se guardan alternativamente en dos ficheros temporales F1 y F2.


Cogemos el primer lote de tamaño k de cada uno de los ficheros y lo fundimos sobre otro fichero temporal F3. Se procede de esta forma con cada par de lotes hasta que F1 y F2 quedan vacíos. F3 contiene entonces lotes de tamaño 2k ordenados. Estos lotes se distribuyen como anteriormente entre F1 y F2 y se comienza de nuevo el proceso de fusión de bloques de tamaño 2k. El proceso continua hasta que F3 contiene el fichero completo ordenado. Este proceso se conoce como fusión natural 2-vías.

kk

2k

2k 2k

4k

Figura. Fusión de 2-vías

En una ordenación n-vías, los registros se distribuyen por lotes en n ficheros temporales diferentes y posteriormente se realiza la fusión entre los n ficheros.

5.3 Ficheros de acceso aleatorio. Hashing.

Un fichero es de acceso aleatorio o directo si se puede acceder a sus registros en un orden arbitrario. No es necesario leer los registros anteriores para acceder al registro que se desea.

El identificador de un registro se llama clave. La clave puede ser un campo o una combinación de campos del registro. La clave permite identificar unívocamente el registro.

Los ficheros aleatorios requieren una organización de la información que permita recuperar cualquier registro deseado. La organización incluye la forma en que se agrupan los registros en el fichero y los pasos necesarios para localizar uno de ellos en particular.

Un método de acceso selectivo permite a partir de un identificador de un registro determinar la posición exacta (dirección) del registro.


5.3.1.1 Organización relativa o directa. Fichero directo.

Los ficheros directos están compuestos por registros de longitud fija. Los registros se almacenan secuencialmente en el fichero y la clave de acceso a cada registro es el número de orden del registro en el fichero.

El uso de direcciones relativas elimina la necesidad de indicar direcciones físicas dependientes del dispositivo. Si i es la posición relativa del registro buscado en el fichero y n el tamaño de cada registro, la posición del registro i-ésimo será

Dirección = dirección fichero + (i-1) * n

5.3.1.2 Búsqueda en directorio u Organización indexada

Si los registros no tienen tamaño fijo, se puede construir una estructura de acceso utilizando un índice que contenga la clave y la dirección de cada uno de los registros del fichero. Los índices pueden organizarse de forma que se mejore el acceso a la información. Los índices pueden almacenarse junto con el fichero de datos o en un fichero separado. En el próximo capítulo se estudian en detalle los ficheros indexados.

5.3.1.3 Organización aleatoria

Un fichero aleatorio es un fichero en el que los registros están colocados en paquetes cuya dirección se calcula con ayuda de una función definida sobre las claves del registro. Para acceder a un registro se necesita calcular la dirección del bloque que lo contiene y después buscarlo dentro del bloque.

5.3.2 Acceso aleatorio

Las técnicas de hashing o de almacenamiento disperso consisten en generar un número índice a partir de operaciones aritméticas sobre la clave de un registro. El índice calculado indica la posición del registro en el fichero.

El hashing requiere la definición de una función f definida para las claves de los registros del fichero y que devuelve las direcciones absolutas o relativas donde se almacena el registro. Esta función recibe el nombre de función de hash. La función de hash debe ser una función simple y fácil de calcular.

H : C D

Los elementos direccionados por la función de hash pueden almacenar uno o varios registros. Estos elementos reciben el nombre de cubos o celdas. Cuando el cubo tiene un tamaño mayor que 1 el proceso de búsqueda utilizando funciones hash se complementa con una búsqueda secuencial para encontrar el registro en el cubo.

El conjunto de direcciones sobre el que aplica la función de hash puede ser menos que el número de registros del fichero, por lo que a claves distintas la función hash les asignará la misma dirección. En estos casos se requiere un método de resolución de colisiones, capaz de encontrar una dirección alternativa cuando la aplicación de la función hash sobre dos o más claves distintas devuelve la misma dirección.


Por tanto, el hashing tiene dos componentes principales: el cálculo de la dirección a partir de la clave y la resolución de las colisiones.

5.3.3 Funciones de hashing

La propiedad principal de la función de hash es que distribuya por igual las claves entre las direcciones disponibles. Para ello es importante que la función disperse aleatoriamente, aunque uniformemente, las claves a través de las direcciones disponibles. De esta forma se consigue que una concentración en los valores de la clave no se traslade a una concentración en el almacenamiento al aplicar la función de hash.

Las funciones de hash más importantes son cuatro: truncamiento, plegado, multiplicación y división.

5.3.3.1 Truncamiento

Un número se trunca cuando se le quitan algunos dígitos del comienzo o del final. Podemos construir una función de hash eliminando los primeros k o los últimos m dígitos de una clave de n dígitos, o ambos (n > k+m).

Supongamos que la clave es un número decimal de 8 dígitos. Podemos construir una función de hash eliminando los 2 primeros y los 2 últimos dígitos de la clave. Por ejemplo:

f (12345678) = 3456

A todos los números que tengan los mismos dígitos en sus cuatro cifras centrales les corresponderá la misma dirección según la tabla de hash.

5.3.3.2 Plegado

El plegado consiste en dividir un número en dos o más partes y luego sumarlas. Siguiendo con el ejemplo anterior:

f (12345678) = 1234 + 5678 = 6912

Si como resultado de la suma apareciese un dígito más en el resultado, se puede conservar o eliminar por truncamiento.

5.3.3.3 Multiplicación

Consiste en dividir la clave y multiplicar las partes resultantes de la división. Si el resultado es demasiado grande, puede truncarse.

f (12345678) = 1234 * 5678 = 70006652

La multiplicación esparce aleatoriamente las claves, evitando las colisiones entre claves próximas. Sin embargo, el comportamiento de la función multiplicación como función hash depende de la naturaleza de las claves. Por ejemplo, si las claves terminan frecuentemente en 000 o 001 la multiplicación no esparce adecuadamente las claves.


Una variante de esta función de hash es la elevación al cuadrado. Se seleccionan dígitos consecutivos de la clave y se elevan al cuadrado.

5.3.3.4 División, Resto

El método hash más sencillo y efectivo consiste en dividir la clave entre el tamaño de la tabla. El resto de la división entera es la dirección relativa. Nunca es necesario el truncamiento con el método de la división.

Si el tamaño de la tabla es 200:

f (1145) = 1145 mod 200 = 145

En general f (N) = N mod T

La elección de T es importante para el correcto funcionamiento de la función de hash. T debe ser un número primo apenas menor que el número de direcciones.

5.3.4 Tratamiento de colisiones

Como hemos visto las funciones hash pueden transformar claves diferentes en una misma dirección. Este fenómeno recibe el nombre de colisión. El tratamiento de colisiones consiste en encontrar una dirección libre de almacenamiento para todos los registros a los cuales la función de hash les hace corresponder la misma dirección.

Como dijimos con anterioridad, llamaremos cubos o celdas a los elementos direccionados por la función hash. Los bloques pueden almacenar uno o varios registros.

5.3.4.1 Direccionamiento abierto

Las técnicas de direccionamiento abierto tratan de encontrar en la misma tabla una posición libre en caso de colisión. Estas técnicas se usan sobre ficheros con tamaño de bloque grande (>20). Se pueden aplicar varias técnicas:

• Sondeo lineal. Si la dirección asignada está ocupada, el registro se aloja en la dirección siguiente libre más próxima. El sondeo lineal tiende a concentrar los registros alrededor de la primera dirección ocupada. La dirección siguiente a la primera ocupada tiene en la segunda inserción el doble de posibilidades de ser ocupada: se elige por la función hash o por desbordamiento de la primera dirección. Este efecto recibe el nombre de aglomeración primaria.

• Sondeo aleatorio. Genera la dirección de desborde a través de una función del tipo (r+m) mod t, siendo m y t números primos y r la dirección hash inicialmente calculada. Este método de sondeo provoca aglomeración secundaria. Esto significa que cuando a dos claves distintas les corresponde la misma dirección hash, este método les hace corresponder las mismas cadenas de desborde.

• Hashing doble. Se resuelven las colisiones generando una nueva dirección hash con una función distinta a la primera. El hashing doble reduce la


aglomeración secundaria al tener en cuenta el valor de la clave en el cálculo de una segunda dirección de almacenamiento.

Todos los métodos de direccionamiento directo sufren el problema de coalescencia, que consiste en que las secuencias de desborde de diferentes direcciones se entremezclen, haciéndose costoso encontrar direcciones libres. Son métodos muy ineficientes cuando la capacidad de los cubos es pequeña, pero dan buenos resultados para cubos grandes.

5.3.4.2 Encadenamiento

Los métodos de encadenamiento de desbordes utilizan una estructura ligada para enlazar las direcciones principales o primarias con las áreas de desborde asociadas.

R1, R2, R3, R4

Area de desborde

Dirección de cadena

08

05

01 R3

R4

R2

R1Ruta de Hashing

5.3.4.3 Hashing abierto

Si un bloque se llena, se le asigna un bloque de desbordamiento. Si este bloque también se desborda, se le asigna un nuevo bloque de desbordamiento. Todos los bloques de enlazan para indicar los caminos de búsqueda de registros. En esta estructura se suelen reservar bloques de desbordamiento dentro del fichero a intervalos regulares.

5.4 Ficheros indexados

El principio fundamental de las organizaciones y métodos de acceso indexados es el de asociar a la clave de un registro su dirección relativa dentro del fichero mediante una ‘tabla de contenido’ del fichero, llamado índice. El índice contiene las claves de todos los registros asociadas a la dirección relativa de cada uno de ellos. La tabla de índices puede almacenarse en el mismo fichero o en un fichero separado.

El fichero indexado puede contener las claves de todos los registros o solamente un subconjunto de ellas. Se llama densidad del índice al cociente resultante de dividir el


número de claves contenidas en el índice entre el número de registros del fichero. Si el índice contiene las claves de todos los registros del fichero, decimos que el índice es denso, y si la densidad del índice es menor que la unidad, decimos que el índice es no denso.

Si el índice es no denso, los registros se almacenan ordenadamente en bloques conteniendo el índice, la clave mayor contenida en el bloque y la dirección del bloque para cada bloque del fichero.

Los índices pueden ser considerados como ficheros de claves, y por tanto es posible a su vez crear índices sobre los propios índices. Un índice de este tipo se llama índice jerarquizado o anidado. Un índice anidado de dos niveles es un índice clasificado, dividido en paquetes que a su vez tienen un índice, siendo la clave de cada entrada de este último la mayor del paquete. Un índice anidado de n niveles es un índice anidado de n-1 niveles que a su vez posee un índice de 1 nivel.

Los índices anidados forman un árbol de búsqueda al que podemos dotar de las características que optimicen las búsquedas. Veremos estas estructuras en próximos apartados.

5.4.1 Organización secuencial indexada (ISAM)

ISAM (Indexed Sequential Access Method) es un método para la organización secuencial indexada de ficheros desarrollado e utilizado por IBM en sus sistemas. Esta organización ha sido ya sustituida por el método de acceso a memoria virtual (VSAM) que será estudiado más adelante.

Los ficheros secuenciales indexados se organizan por bloques de registros donde los índices apuntan a cada bloque (por tanto, de índice no denso). Para localizar un registro en el fichero, se accede a través de un índice al bloque que contiene el registro, y mediante una búsqueda secuencial se localiza el registro en el bloque.

Este tipo de organización de ficheros es muy utilizada por que mantiene un buen equilibrio entre el tamaño de la tabla de índices y el tiempo de acceso a los registros.

Un fichero ISAM consta de tres zonas lógicas:

• Área primaria de datos, donde se almacenan los registros

• Área de desbordamiento, donde se almacenan los registros cuando se llena el área primaria de datos

• Área de índice, donde se almacenan los índices

El ISAM es una estructura orientada hacia el dispositivo físico de almacenamiento. Para las explicaciones supondremos que el dispositivo consiste en un volumen con 10 superficies y donde cada cilindro contiene 10 pistas numeradas del 0 al 9.


Pista 0 Pista 0 Pista de índices

Pista de datos

Pistas de desbordamiento

Zona de desbordamiento independiente

Cilindro 1Cilindro 0

5.4.1.1 Área primaria de datos

Para almacenar el fichero se reserva inicialmente cierta zona de memoria de almacenamiento a base de bloques de 1 cilindro.

En cada cilindro se reservan pistas exclusivamente para la indexación. Los datos se escriben secuencialmente, según el orden del índice, en el resto de las pistas. La última o últimas pistas se reservan como área de desbordamiento y no se utilizan para almacenar registros durante la primera escritura.

Pistas de índices P1:21 P2:39 P3:58 P4:82

P5.1:22 *:39 *:58 P5.2:97 Pistas de datos 12 15 17 19 20 21

23 28 32 39 45 58 61 63 71 77 79 82

Pistas de desbordamiento 22:# 94:3 97:#

Los registros pueden ser de longitud fija o variable. Si los registros son de longitud variable, un campo de cada registro debe indicar su longitud.

5.4.1.2 El índice de pista

El índice se almacena en la primera pista del cilindro y contiene dos entradas por cada pista: la primera entrada contiene el valor de la clave mayor almacenada en la pista y la dirección a la pista correspondiente, y la segunda, la clave mayor en la zona de desbordamiento (si hay alguna) y el puntero a la posición en el área de desbordamiento correspondiente a esa pista. Mientras no existan datos en el área de desbordamiento, el segundo registro contiene un valor especial para indicar que no existen datos en la pista de desbordamiento.

Para buscar un registro, se busca en el índice la menor clave mayor que la del registro buscado. La dirección asociada a esta clave indica la pista donde se puede encontrar el


registro, bien sea una pista de datos o de desbordamiento. Se accede a la pista correspondiente y se busca secuencialmente el registro. Si el registro no se encuentra en esa pista es que no existe.

5.4.1.3 Inserción de registros

Para insertar un nuevo registro se busca primero en el fichero para comprobar que no existe ya, y localizar al mismo tiempo la posición que le corresponde. Habiendo localizado la posición del nuevo registro en la pista, se desplazan los registros con clave mayor para dejar una posición vacía. Si la pista está completa, el registro mayor será desplazado fuera de la pista para la inserción del nuevo registro y se coloca en el área de desbordamiento.

La clave máxima del índice correspondiente a la pista se debe actualizar porque la hasta ahora clave máxima se ha movido a la pista de desbordamiento. La posición de desbordamiento del índice debe también actualizarse contemplando la clave del registro insertado en el área de desbordamiento. Adicionalmente, si el nuevo registro se inserta en el último lugar de la pista disponible, también se debe actualizar la pista de índices y asignar el valor de la clave del nuevo registro como valor máximo nuevo en la pista.

Los registros se encadenan en la pista de desbordamiento. Las entradas en la pista de desbordamiento contienen un puntero a la siguiente entrada correspondiente a su pista. Los registros se almacenan en el orden de llegada, aunque la lista encadenada de la pista de desbordamiento es ordenada.

5.4.1.4 Área independiente de desbordamiento

En ficheros grandes se reserva una zona de desbordamiento fuera del área primaria de datos, para poder ser utilizada en el caso en que se llenen las pistas de desbordamiento. Esta zona es utilizada por todos los cilindros del fichero.

Los registros que no caben en el área de desbordamiento se graban en la primera posición libre del área independiente de desbordamiento. Se actualiza la lista encadenada correspondiente a la zona de desbordamiento para incluir este registro. Los punteros de esta lista pueden hacer referencia tanto a las pistas de desbordamiento como al área independiente de desbordamiento.

La utilización de esta zona deteriora el rendimiento del sistema, que tiene que efectuar un movimiento de la cabeza lectora para cambiar de área.

Cuando el área de desbordamiento se hace excesivamente grande o se llena, se debe reorganizar el fichero. Para ello se reserva el espacio suficiente y se rescriben todos los registros en el área primaria de almacenamiento.

5.4.1.5 Eliminación de registros

Al eliminar un registro no se recupera el espacio ocupado por este. El registro se marca como borrado y no se tiene en consideración durante las búsquedas. Cuando durante una inserción el registro borrado sale del almacenamiento primario, o durante una reorganización del fichero, estos registros se eliminan definitivamente.


5.4.1.6 Índice de cilindros

Cuando un fichero ocupa varios cilindros se mantiene un índice parecido al índice de pistas que mantiene las claves máximas almacenadas en cada cilindro y la dirección de cada cilindro.

5.4.1.7 Índice maestro

En aquellos ficheros donde el índice de cilindros llega a ser muy grande, se utiliza un índice maestro para facilitar el acceso indexando el propio índice de los cilindros.

5.4.1.8 Análisis del método ISAM

Las ventajas del método vienen del hecho de que el fichero está ordenado, lo que facilita el acceso secuencial en orden creciente y los tiempos de acceso son buenos siempre que el fichero no esté desbordado.

Los inconvenientes son varios. La gestión de desbordamiento es compleja y degrada las prestaciones hasta hacer necesaria una reorganización periódica de los ficheros. Por otra parte, el método de acceso depende de las características físicas del soporte (pistas, cilindros, etc.).

Las prestaciones dependen de los desbordamientos. Si una pista incluye d registros en la zona de desbordamiento, serán necesarios aproximadamente 3+(d/2) E/S mientras que una escritura requerirá 2+(d/2)+4 E/S para encontrar la posición del registro, escribirlo y actualizar los encadenamientos.

5.4.2 Almacenamiento masivo virtual. VSAM.

El método VSAM (IBM) para el almacenamiento de ficheros indexados es independiente del dispositivo físico utilizado, lo que permite la utilización de una misma aplicación sobre diversos soportes. Se utiliza en el sistema IBM OS/VS.

Existen tres tipos de organización de ficheros en VASM:

• KSDS (Key Sequenced Data Set).

• ESDS (Entry Sequenced Data Set).

• RRDS (Relative Record Data Set).

El ESDS y el RRDS son respectivamente las implementaciones VSAM de las organizaciones secuencial y relativa. Sin embargo, la estructura más utilizada es la KSDS, que analizaremos a continuación.

5.4.2.1 Zona de datos

En VSAM los registros se agrupan y almacenan por bloques que reciben el nombre de intervalos de control. Los intervalos de control tienen el tamaño necesario para poder leerlos y escribirlos en una sola operación de acceso al dispositivo de almacenamiento. Los intervalos de control se agrupan a su vez en áreas de control. Tanto las áreas como los intervalos de control contienen espacios vacíos para la inserción de nuevos registros.


La proporción de espacio disponible para nuevas inserciones se especifica al crear un fichero.

Los intervalos en el área de control están indexados, conteniendo el índice y la clave mayor en cada intervalo y la dirección de comienzo del intervalo. Además, los registros se ordenan secuencialmente según el orden definido dentro de cada intervalo de control.

Zona de índices

23

1715

13

129

7

5 1

Intervalo de control

La inserción de registros sigue el siguiente algoritmo. Primero se determina mediante los índices el intervalo que debe contener el registro

• Si el intervalo no está lleno, se almacena el registro en el lugar que le corresponde según el orden establecido para la clave

• Si el intervalo está lleno, se divide su contenido en dos partes manteniendo el orden

• Si existe un intervalo libre dentro del área de control, se utiliza para almacenar uno de los medios intervalos

• Si no existe ningún intervalo libre en el área, se asigna un área vacía al fichero y se escinde el área completa en dos partes, manteniendo el orden. Se asignan los intervalos con claves más altas a la nueva área

5.4.2.2 Zona de índices

Cuando crecen el número de áreas y de intervalos, se pueden utilizar índices multinivel. El primer nivel (índice de intervalos) contiene la clave mayor y la dirección de todos los intervalos de un área. El índice de áreas contiene la clave mayor y la dirección de cada área del fichero. Si el índice de áreas es demasiado grande también puede indexarse por grupos, y a este índice se le llama índice maestro.

5.5 Arboles B

Los árboles B y sus variantes, árbol B+ y árbol B*, constituyen las estructuras más utilizadas para el mantenimiento y acceso a índices en los sistemas de bases de datos. Los nodos del árbol B contienen claves y direcciones a sus registros correspondientes en el fichero.

Los árboles B son árboles de ordenación equilibrados que combinan algoritmos de búsqueda cuasi-óptimos con una buena gestión del soporte de almacenamiento externo.


Como se sabe, un árbol está equilibrado si y sólo si para cada uno de sus nodos, las alturas de sus subárboles difieren como máximo en 1 unidad. A estos árboles se les llama árboles equilibrados.

El árbol B se organiza sobre el disco de forma que se minimizan el número de operaciones de entrada/salida. Como se ha visto, éstas son las operaciones más costosas en tiempo de ejecución. Puesto que en una operación de acceso a memoria secundaria se pueden leer y escribir varios nodos a la vez sin esfuerzo adicional, la técnica consiste en dividir el árbol en subárboles del tamaño necesario para almacenarse en una operación de E/S. Estos subárboles se llaman páginas.

En el árbol del ejemplo se necesitan sólo 2 operaciones de E/S para recorrer un árbol de 4 niveles. En caso de no utilizarse esta organización serían necesarias hasta 4 operaciones E/S.

5.5.1 Propiedades de los árboles B de orden n

1. La raíz tiene al menos dos descendientes o el árbol es una hoja

2. Ningún nodo tiene más de n descendientes

3. Cada nodo que no es raíz ni hoja tiene al menos n/2 descendientes

4. Todos los nodos hoja están en el mismo nivel

5. Un nodo que no es hoja con k descendientes tiene k-1 claves

** 89*60

29 * 45 * * 96 * 105 * * 75 * 81* *

27 23 4231 56 54 6663 7978 8883 9492 102 99 112 122


5.5.2 Capacidad de un árbol B

Sabemos por las propiedades de estos árboles que el número máximo de nodos y claves en un árbol B de orden m y altura k es:

Número de nodos máximo: p = 1+m+m2+m3+…+mk-1 = = ∑−

=

1

0

k

i

im11

−−

mmk

Número de claves máximo: n = 1(m-1)+m(m-1)+m2(m-1)+…+mk-1 (m-1) = mk-1

Pero también sabemos que 1−

=m

np

Luego combinando ambas fórmulas obtenemos que 11

−−

mmk

= 1−m

n , y por tanto, el

resultado que buscamos es:

)1(log += nk m

Por tanto, dado un árbol b de orden m y con capacidad para n claves, podemos averiguar la altura que tendrá dicho árbol; o dicho de otro modo, podremos conocer los pasos máximos necesarios (E/S) para obtener la dirección del registro en una búsqueda.

Nota: El caso más complejo, sin embargo, es calcular el número menor de nodos en un árbol de orden m para una altura dada de k

5.5.3 Operaciones sobre un árbol B

Las operaciones básicas sobre un árbol B son las siguientes:

• Búsqueda de una clave • Inserción de una clave nueva • Eliminación de una clave

5.5.3.1 Búsqueda de una clave

La búsqueda de una clave se realiza del mismo modo que en los árboles de búsqueda binarios. La única diferencia es que en cada nodo del árbol B existen varias claves, y habrá que determinar cuál de los punteros adyacentes a una clave en un nodo se utiliza para pasar al nodo hijo, en caso de que sea necesario.

El proceso consiste en iniciar la búsqueda en el nodo raíz. Llamaremos Q a la clave que estamos buscando. Se recorre el nodo buscando la primera clave con valor mayor que Q. Si esta clave existe y es igual a Q finaliza el proceso. Si la clave existe, pero es distinta de Q, se repite el proceso en el nodo hijo apuntado por el puntero de la izquierda de la clave. Si la clave no existe, se continúa el proceso en el nodo hijo apuntado por el puntero de la derecha de la última clave del nodo. El proceso finalizará cuando se encuentre el valor buscado o se recorra completamente un nodo hoja.


5.5.3.2 Inserción de una clave nueva

La inserción de una clave se realiza desde las hojas y en sentido ascendente en el árbol. Para insertar una nueva clave hay que localizar en primer lugar la posición en el árbol en el que la clave debería insertarse. Por tanto, lo primero que hay que hacer es una búsqueda en él árbol. En caso de que la clave no se encuentre en el árbol, se procede a su inserción.

Una vez determinado el punto de inserción en el nodo hoja correspondiente se procede del siguiente modo:

• Si el nodo hoja no está completo (es decir, si no tiene m-1 claves para un nodo de orden m), se inserta la clave en el lugar correspondiente.

• Si el nodo hoja está completo, entonces se inserta en el lugar que corresponde y se divide el nodo en dos nodos distintos con la mitad de las claves en cada uno de ellos, y se promociona la menor de las claves del nodo derecho resultante de la división al nodo padre.

• Si el nodo padre no está completo, la inserción ha finalizado. Sin embargo, si el nodo padre estuviese completo, habría que repetir el paso anterior hasta llegar a un nodo que no estuviese completo.

• En el peor de los casos, es posible que haya que promocionar claves hasta llegar al nodo raíz, en cuyo caso el nodo raíz se separaría en dos nodos distintos, y se promocionaría una clave a un nodo superior, que habría que crear y sería el nuevo nodo raíz.

5.5.3.3 Eliminación de una clave

Al igual que la inserción, la eliminación de una clave en un nodo puede resultar en situaciones no permitidas para un árbol B (p. ej. que el número de claves en el nodo en el que se realiza la eliminación quede con menos de m/2 claves si el árbol es de orden m). Hay que seguir, por tanto, un procedimiento general para evitar que estos problemas se produzcan:

• Si el nodo en el que se va a realizar la eliminación contiene después de la operación de borrado al menos m/2 hijos (m/2 – 1 claves) el proceso termina.

• Si por el contrario no se produce la situación anterior, entonces es necesario reestructurar el árbol para que siga manteniendo su estructura de árbol B. Para ello se trabaja de dos modos: el primero trata de crear un único nodo tomando el nodo del que se elimina la clave y un nodo hermano, y luego se re-estrucutra el padre; el segundo crea dos nodos tomando el nodo del que se elimina la clave y un nodo hermano, y re-estructurando tanto los dos nuevos nodos como el nodo padre.

5.6 Árboles B+

Los árboles B+ son variantes de la estructura de árbol B que se utiliza frecuentemente en bases de datos, como en los ficheros VASM de IBM. Al igual que en los árboles B,


el árbol B+ está formado por un nodo raíz y diversos nodos llenos hasta la mitad al menos. Sin embargo, los árboles B+ presentan dos características añadidas:

• Los nodos hoja se encadenan según el orden de las claves formando una organización secuencial

• Los nodos interiores no contienen direcciones a los registros del fichero (hay duplicación de las claves, y las direcciones a los registros del fichero se encuentran siempre en los nodos hoja).

Como consecuencia de estas características, los árboles B+ permiten el procesamiento secuencial de los registros y contienen para un mismo orden y profundidad que un árbol B más claves.

5.7 Árboles B*

Los árboles B* son variaciones de los árboles B que permiten mejorar el proceso de inserción de claves. Los árboles B* de orden n tienen las siguientes propiedades:

• La raíz es una hoja o tiene un mínimo de dos y un máximo de 2*[(2n-1)/3]+1 descendientes.

• Ningún nodo tiene más de n descendientes

• Cada nodo que no es raíz y hoja tiene al menos [(2n-1)/3] descendientes

• Todos los nodos hoja están en el mismo nivel

• Un nodo no terminal con k descendientes contiene k-1 claves. Una hoja contiene al menos [(2n-1)/3]-1 valores


Technology

Capitulo 5