SAl13 Ficheros. Tipos. Características. Organizaciones. 1 Introducción. Los sistemas informáticos requieren, para la manipulación de la información, que ésta se encuentre previamente almacenada en alguno de los dispositivos de almacenamiento que estos sistemas reconocen. Si esta informaciónpuede ser obtenida en tiempo de computación, bien mediante un cálculo operacional, o bien mediante la entrada desde un terminal de entrada/salida y, este proceso tiene un bajo coste computacional y, además, puede ser reproducido, esta información puede ser almacenada en la memoria central de la computadora con el conocimiento de que será perdida una vez el proceso que manipula esa información abandone la memoria central de la computadora. Pero son muy pocos los problemas en los que el dominio de la información satisface estas características. En la mayoría de los casos el volumen de información es tan elevado, o los procesos de cómputo, para obtenerla son tan costosos, que el alimentar a los procesos de manipulación de esa información con ésta en cada una de sus ejecuciones resulta algo inconcebible. Es en estos casos cuando el usuario de los sistemas informáticos requiere de los ficheros para el almacenamiento de la información que forma parte del dominio del problema que está tratando con un sistema informático. Un fichero es una agregación de datos estructurados que es vista por el sistema operativo de la computadora como un todo, como una unidad estructural sobre la cual se pueden realizar una serie de operaciones dependiendo del dispositivo fisico en el cual se encuentre y de la propia estructura interna de los datos en el mismo. El conjunto de datos que forman parte de los ficheros se agrupan en unidades denominadas registros cuya función es representar a unidades de información del problema que se está tratando. El número y estructura de los datos que forman parte de los registros es determinado en la fase de análisis y diseño lógico del problema, mientras que la disposición de los registros y los datos en los ficheros (su estructura) es determinada en el diseño fisico. Existen múltiples estructuras diferentes en las cuales puede almacenarse la información dando lugar a lo que se conoce como organizaciones de la información y, en base a esas organizaciones los procedimientos que manipulan esa información son diferentes. Este tema vamos a estudiar las organizaciones de ficheros que permiten estructurar la información correspondiente a los problemas para que pueda ser manipulada con un desempeño aceptable. Si bien Ias organizaciones pueden ser tan diferentes como las necesidades lo requieran y sería imposible atender a todas las posibles variaciones, sí se intentan cubrir aquellas organizaciones básicas en las cuales están basadas las demás. 2 Conceptos básicos. Un fichero es una agregación de datos estructurados que es vista por el sistema operativo de la computadora corno un todo, como una unidad estructural sobre la cual se pueden realizar una serie de operaciones dependiendo del dispositivo fisico en el cual se encuentre y de la propia estructura interna de los datos en el mismo. El conjunto de datos que forman parte de los ficheros se agrupan en unidades denominadas registros cuya función es representar a unidades de información del problema que se está tratando. 2.1 Almacenamiento de la información. Los datos almacenados en la memoria de una computadora pueden mantenerse en ella como máximo, mientras se le suministre alimentación eléctrica. Al ser desconectada de la alimentación, la computadora pierde todos los datos almacenados en su memoria. Debido a ello, a este tipo de almacenamiento se le denomina con el término volátil. Los dispositivos de almacenamiento de ficheros, por el contrario, mantienen la información grabada en ellos aunque no se suministre alimentación a los mismos, o a la computadora en la que se encuentran instalados. Esto es debido a la naturaleza de estos dispositivos. Por ejemplo, en los dispositivos de grabación magnética Ja información permanece aunque no exista suministro eléctrico, ya que la información queda reflejada en una superficie magnetizable mediante cambios en dicha magnetización producidos por una cabeza lectora/grabadora. Esta magnetización, una vez creada, no necesita de alimentación para mantenerse sobre la superficie. La cabeza lectora/grabadora, cuando el dispositivo vuelve a su funcionamiento, es capaz de interpretar esas diferencias en Ja magnetización de la superficie y leer así los datos almacenados. Por ello, a este tipo de almacenamiento se le denomina con el término no volátil. Otra terminología hace referencia al almacenamiento en la memoria de la computadora como almacenamiento primario, mientras que otros dispositivos que almacenan ficheros reciben el nombre de almacenamiento secundario. 2.2 El gestor de ficheros. El gestor de ficheros de un sistema operativo es la parte del mismo que se encarga de administrar todo lo relacionado con los datos en los dispositivos de almacenamiento. Cuando un programa requiere el acceso a un fichero, es el gestor de ficheros el encargado de asociar a los elementos lógicos del fichero utilizados por el programa las correspondientes localizaciones tisicas donde se encuentran los datos. El sistema operativo utiliza como unidad de transferencia de datos al disco el bloque. Un bloque puede estar formado por uno o varios sectores (físicos o hardware) para así llevar un control, por software, más eficiente de los datos almacenados en el disco. El número de sectores por bloque depende del sistema operativo e incluso, algunos sistemas operativos permiten que éste sea un parámetro que el administrador del sistema puede seleccionar en el proceso de instalación del sistema operativo. Un bloque, por tanto, es una agrupación que datos que es considerada por el sistema operativo como la unidad de transferencia de información entre los dispositivos de almacenamiento secundario y la memoria de la computadora. En sistemas de ficheros como FAT, NTFS, CDFS, los sectores son agrupados también en bloques que reciben el nombre especial de clusters. Un bloque (o cluster en algunos sistemas) es también el espacio de disco mínimo que puede reservarse para almacenar un fichero. Este concepto hace que un fichero pueda ocupar un tamaño en disco diferente dependiendo del sistema de ficheros utilizado. EI sistema operativo puede acceder directamente a los datos almacenados en un disco, pero esto supondría que las transferencias entre memoria y el disco serían muy frecuentes y haría que el manejo de ficheros tuviera un bajo desempeño debido al coste computacional de una operación de acceso al disco. En lugar de operar de esta forma, y para minimizar así la frecuencia de acceso al disco, el sistema operativo mantiene una zona en la memoria para alojar los bloques del disco de más reciente uso. Esta zona de memoria recibe el nombre de caché de disco. Cuando un programa requiere leer o escribir datos en el disco el sistema operativo accede en primer lugar a la caché de disco. Si el dato buscado se encuentra, en la caché, el sistema operativo no tiene que acceder al disco. Si el dato buscado no se encuentra en la caché, el sistema operativo accede al disco y mueve a la caché el bloque, consiguiendo así que los datos del bloque requerido se tomen siempre de la caché y que se mantengan en la caché los datos más frecuentemente utilizados. Del mismo modo, cuando el sistema debe reemplazar el bloque que en ese momento se encuentra en la caché, se escribe previamente el bloque de la caché al disco antes de reemplazarlo. 2.3 Rendimiento de la transferencia de la información. El número de registros lógicos que puede contener un registro fisico se denomina factor de bloqueo. Se puedendar las siguientes situaciones: • Registro lógico > Registro físico. En un bloque se contien en varios registros físicos por bloque; se denominan registros expandidos. • Registro lógico = Registro fisico. El factor de bloqueoes 1 y se dice que los registrosno están bloqueados. • Registro lógico < Registro físico. El factor de bloqueo es mayor que l y los registrosestán bloqueados. Un factor de bloqueo mayor que l siempre mejora el rendimiento; entonces, ¿por qué no incluir todos los registros en un solo bloque? La razón reside en que el aumentodel bloque implica el aumentode la memoria intermedia y por consiguiente se reduce el tamaño de la memoria central. 3 Tipos de archivos. En una aplicación informática se pueden utilizar archivos para realizar funciones diversas. Conocer la función que va a desempeñar un archivo concreto es fundamental a la hora de decidir como se debe organizar éste. Podemos clasificar los archivos como archivos permanentes y archivos temporales. 3.1 Archivos permanentes. Un archivo permanente contiene información relevante para una aplicación, es decir, los datos necesarios para el funcionamiento de la misma. Su vida es larga (al menos comparable a la de la aplicaciónpara la que ha sido creado) y generalmenteno puede generarsedé una formainmediataa partir de otrosarchivos. Los archivos permanentes se pueden clasificar en: • Archivos maestros. Un archivo maestro contiene el estado actual de los datos susceptibles de ser modificados en la aplicación. • Archivos constantes. Un archivo constante es aquel que contiene datos fijos para la aplicación. En él las modificaciones son infrecuentes, normalmente se accede a él sólo para consultar. • Archivos históricos. Un archivo histórico es aquel que contiene datos que fueron actuales en tiempos anteriores. Se conservan para poder reconstruir la situación actual o situaciones anteriores. En algunos casos puede estar formado simplemente por los registros borrados del archivo maestro. Un archivo histórico puede contener, por ejemplo, los clientes que se han dado de baja en una entidad bancaria. 3.2 Archivos temporales. Un archivo temporal contiene información relevante para un determinado proceso o programa, pero no para el conjunto de la aplicación. Se genera a partir de los datos de archivos permanentes o para actualizar éstos, y su vida es generalmente muy corta. Los archivos temporales se pueden clasificar en: • Archivos intermedios. Se utilizan para almacenar resultados de un programa que han de ser utilizados por otro, dentro de una misma tarea. • Archivos de maniobras. Se utilizan para almacenar datos propios de un programa que éste no puede conservar en memoria principal, por falta de espacio en ésta. • Archivos de resultados. Se utilizan para almacenar datos elaborados que van a ser transferidos a un dispositivo de salida. 4 Organización de archivos. La organización de un fichero determina el modo de estructurar Jos registros pertenecientes a un fichero en almacenamiento secundario. Los métodos de acceso nos permitirán localizar dichos registros. La elección de una determinada organización permitirá realizar distintos tipos de acceso a los registros del fichero y, viceversa, si se desea acceder a un registro o conjunto de registros de una determinada forma, se deberá elegir una organización adecuada para ello. La organización de los ficheros y los métodos de acceso repercuten fuertemente en los tiempos de respuesta. Los métodos básicos de acceso son los siguientes: Escuela de Preparación de Opositores E.P.O. v02 INFJ 3 - SAII3. Página 6 • Acceso secuencial.Para localizar un registro se necesita haber accedido al registro anterior. Puede resultar el modo de acceso más eficiente cuando se tiene que procesarel ficherocompleto (o unporcentajedelmismo). • Acceso directo.Se localiza un registropor su dirección, obtenidaa partir del valor de una clave de direccionamientoo por la posición relativa que ocupa el registroen el fichero. La elección del tipode organizacióndependede tres factores: l. Del tipo de proceso: Más concretamente del tipo de acceso requerido (secuencialo directo)y de si lasoperacionesque se realizanen el fichero son de recuperacióno de actualización. 2. De los factores que se desean optimizar: Estos factores son diversos y están muy relacionadosentre sí,pero podemos enumerarJos siguientes: espacio de almacenamiento,tiempos de respuesta, accesosa disco, etc. 3. De las característicasdel fichero: Es decir, si el fichero tiene granvolumen o no, si su crecimiento será rápido, si se eliminaránmuchosregistros, etc. En definitiva, tamaño, volatilidad y crecimiento,principalmente. 4.1 Organizacionesconsecutivas. Las organizaciones consecutivas sitúan los registros fisicamente uno a continuación de otro. Si la colocación de los registros no tiene un orden lógico, el tipo de organización se denomina consecutiva serial; si, por el contrario, tienen un orden, segúnuna clave de ordenación,se denominaconsecutivasecuencial. El método de acceso que se utiliza para localizar los registros almacenadoses el secuencial si la organización es serial; si es secuencial puede utilizarse, además, un acceso directopor posiciónrelativadel registro (búsqueda binaria o dicotómica). Es adecuada para recuperar ficheros en procesos por lotes, pues optimiza al máximo el espacio de almacenamiento, es muy fácil de programar, puede utilizar registros de longitud variable y heterogéneos, y no está limitada al tipo de soporte directo. Es conveniente utilizar este tipo de organización cuando existe una carga masiva de datos, las tablas son pequeñas,o cuando, en el proceso del fichero se accede normalmentea casi todaslas filas. Esta es la única organización de archivos susceptible de ser gestionada en un dispositivo no direccionable(soportes secuenciales tales como cintamagnética,cinta de papel o tarjeta perforada). La secuencia en que aparecen los registros en el archivo puede estar determinadapor el valor de algún campoo ser simplementetemporal. Si el archivo se encuentrasobreun soporte direccionable(disco por ejemplo) es posible almacenar junto a cada registro un puntero con la dirección del registro siguiente, según el orden lógico del archivo. Estructuralmente un archivo secuencial encadenadoes equivalentea una lista lineal deregistros. Escuela de Preparación de Opositores E.P.O. v02 TNFl3-SAI 13. Página 7 .... Alvaro · Eduardo · .',,: o· Esteban ..... Enrique ,,:. Eustaquio Si la longitud de los registros es mucho menor que el tamaño del bloque del dispositivo (factor de blocaje mayor que uno), en cada acceso a disco se podrán leer o escribir varios registros. Si en cadanodo de la cadenahay un solo registrose ralentiza el acceso, ya que la lectura de cada registro implicará un acceso al dispositivo. Para reducir el tiempo de acceso se deben almacenaren cada bloquetantos registros como sea posible,encadenandolosbloques, en lugar de encadenarlos registros. Los registros contenidosen cadabloque serán consecutivos segúnel orden lógico delarchivo. 4.2 Organizaciones direccionadas. Este tipo de organización almacena Jos registros según una relaciónestablecida entre el valor de la clave de direccionamientoy la dirección fisica del registro, siendo posible realizar un acceso directo a un registro si se conoce la clave de direccionamiento,aunquepuede impedir(o al menosdificultar)el acceso secuencial. La ubicación de un registro se determinará aplicando un algoritmo de transformacióna la clave de direccionamiento, lo que dará como resultadola dirección base donde se debería almacenar dicho registro. La direcciónbase estará comprendida dentro de un rango de valores, que representan las direcciones relativas, denominado espacio de direccionamiento, el cual se fija previamente en función del volumen de datos que hay que almacenar. La organización direccionadaresulta muy adecuada en procesos de tipo selectivo donde hay que acceder a un registro por el valor de la clave de direccionamientoo porun rango de lamisma. 4.2.1 Métodosde direccionamiento. Dentro de este tipo de organización se puede distinguir entre organizaciones direccionadasdirectasy dispersas. Direccionadas directas. La función de transformaciónen esta organizaciónes 1:1, lo que implicaqueno puede dar direcciones base repetidas: además, la clave de direccionamiento y el algoritmo de transformación deben ser tales que las direcciones obtenidashan de estar comprendidas dentro de un espacio de direccionamiento fijado de antemano.La clave de direccionamientono podrátener,por tanto, valoresrepetidos. Las ventajas de utilizar este tipo de organización es que los registros siempre están ordenados por la clave de direccionamiento, estando los registros situados en direcciones contiguas, por lo que el acceso puede ser secuencial ordenado, además de directo. Todo registro ocupa su dirección base, lo que permite que, mediante un solo acceso a memoria secundaria, localicemos un registro. El inconveniente que tiene la utilización de este tipo de organización es que las exigencias de la clave de Escuela de Preparación de Opositores E.P.O. v02 !NF13-SA!13. Página 8 direccionamientoson muy restrictivas, por lo que suele ser muy difícil encontrar una clave con estas características. Direccionadas dispersas. Las organizaciones direccionadas dispersas utilizan una función de transformación n:I, lo que significa que para distintas claves de direccionamiento podemos tener la misma dirección base, produciéndose entonces una colisión. Estos registros se denominansinónimos. Para este tipo de organizacionesdebemos tomar las siguientesdecisiones: 1. El tamaño del bloque o registro físico en el espacio de direccionamiento.Si el tamaño de bloque es uno el direccionamientoes a registro y si por el contrarioes mayor que uno,el direccionamientoes a cubo. 2. Fijar un espacio de direcciones, considerando que no puede haber una densidad de registros mayor del 80%. Donde la densidad es se define como nº registrosdelficheroI espacio de direccionamiento 3. Elegir un algoritmo de transformación que obtenga las direcciones base dentro del espacio de direccionamientoque disperse los registros de forma uniforme, a fin de minimizar los sinónimos (si el direccionamiento es a registro)u optimizar su distribuciónen elcasode direccionamientoa cubo. 4. Utilizar alguna técnica de gestión de desbordamientos. Un desbordamiento se produce cuando la dirección base de un registro o el cubo al que estaba asignado están ocupados; por tanto, debemos pensar en la nueva ubicación de este registro excedentario. Hay dos formas de resolver el problemade los sinónimos,siemprea costa de complicarlaestructuradelarchivo: • Cuando se asocia a una clave una dirección ya ocupadapor un registro distinto (esto es, por un sinónimo de esta Have), se busca en el archivo hasta encontraruna posición libredondeescribirelregistro. • Se reservauna zona de desbordamientosdonde se escribiránlos registros que no se pueden escribir en la posición que les corresponde según la transformación,a la quedenominaremoszonaprincipal. Si se utiliza el primer procedimiento, la búsqueda de una posición libre puede realizarse secuencialmente a partir de la posición asignada, o aplicando a la dirección obtenida un segundo método de direccionamiento. En cualquier caso, ambos procedimientos son lentos y degradan considerablementeel archivo. Si se utiliza zona de desbordamientos se puede gestionar ésta, bien secuencialmenteo bien encadenada a la zona principal. Esto último presenta el inconveniente de tener que reservar un puntero en cada registro, pero permite un acceso más rápido a los sinónimos, lo que en general será más importante queel espacio. 4.2.2 Algoritmosde direccionamiento. Haytres métodosbásicos de direccionamientopara los archivos de organización directa: • Directo.Se utilizacomo dirección lapropiallave. Escuela de Preparación de Opositores E.J>.O. v02 1NFJ3 - SA 113. Página 9 • Asociado. Acada llave se le asocia unadirecciónmedianteuna tabla. • Calculado o por transformaciónde llave. La dirección se obtiene realizando operacionesy transformacionescon Iallave. A continuación se describen brevemente estos tres tipos de direccionamientos para archivosde organizacióndirecta. Direccionamiento directo. El direccionamientodirecto sólo es factible cuando la clave es numérica y su rangode valoresno es mayor que el rango de direcciones en el archivo. Se utiliza como dirección lapropia clave. En algunos casos pueden quedar lagunas de direcciones sin utilizar, en lugares conocidos de antemano. En este caso se pueden ocupar dichas direccionesdesplazando las direcciones superiores. Un archivo aleatorio con direccionamiento directo está siempre ordenado. Direccionamiento asociado. El direccionamientoasociado se puedeutilizarparacualquier tipo de clave. Si se utiliza este método debe construirse una tabla en la que figurarántodas las claves y Ia direccióndondese encuentrael registrocorrespondiente. Al añadir nuevos registros las claves se colocan al final de la tabla. Esta se encontrará normalmentedesordenada. Por tanto, habrá que localizar las claves en ella por lectura secuencial, lo que ralentiza el acceso, al menos que la tabla esté residiendo en Ia memoria principal, se indexe o se ordene y se busque en ella la clave con un procedimiento rápido, tal como el de búsquedadicotómica. Direccionamiento calculado (hashing). En el direccionamiento calculado (hashing) la dirección de cada registro se obtiene, o bien evaluando una expresión que utiliza como dato la llave, o bien realizando una transformación sobre dicha clave. Se utiliza cuando la llave no es numérica o, siendo numérica, cuando puede tomar valores dentro de un conjunto demasiado grande como para poder ser utilizada directamente como dirección. Cualquiera que sea la transformaciónusada es normal que aparezcansinónimos, si bien la frecuencia con que éstos aparecerán dependerá en cada caso concreto del algoritmo de transformaciónutilizado. Si la clave no es numérica se utilizará una conversión previa para obtener un número a partir deella. Existen gran cantidadde métodos de cálculo de dirección. Aquí sólo citaremos losmásrelevantes. • División. La dirección es el resto de dividir la llave por una constante. Normalmenteesta constantees el mayorde los númerosprimos menoresque el númerodeposicionesdel archivo. · • Extracción. Consiste en utilizar como dirección un grupo de cifras de la llave, contiguaso no. Escuela de Preparación de Opositores E.P.O. v02 INF 13 - SAii 3. Página I O • Elevación al cuadrado. Se utiliza cuando la representaciónnumérica de la llave no esmuy larga. Consisteen elevar ésta al cuadradoy tomarlos dígitos centrales. • Plegamiento. Se utiliza para llaves muy largas. Se descompone la llave en trozos de cifras contiguas del mismo tamaño y se suman éstos. Sobre el número generadosepuede aplicarotro métodosi esnecesario. Siempre que deba accederse a una posición, ya sea para introducirpor primera vez un registro o para su consulta o modificación, debe aplicarse a la llave el algoritmo de transformación. 4.3 Organizacionesindexadas. Sobre las organizacionesbásicas (consecutivasy directas)es posible superponer nuevas estructuras que consiguen mejorar la eficiencia en el acceso a los registros que cumplan ciertas condiciones de búsqueda; se trata de las organizaciones indexadas. Puede ocurrir también que la estructura indexada esté unida a los datos, de forma que éstos no tenganuna organizaciónbásica previa a laconstruccióndel índice. Una estructura de índice se define sobre uno o más campos de un fichero, llamados clave de indexación; de forma que cada uno de los valores de la clave de indexaciónse asociaa la direccióndelregistroalquele correspondedichovalor. Archivo secuencial indexado Llave Direccìón 1 Almería Cáceres 1 2 Alava Logroño 4 3 Cáceres 4 Cuenca Oviedo 8 5 Huesca Zaragoza 10 6 Jaén Zonade registros Zona de índices 7 Logroño 8 Madrid 9 Oviedo 10 Zaragoza Un valor de la clave de direccionamiento con la dirección asociada constituye una entrada al indice. El acceso al registro de datos se hace por el valor de Ja clave de indexación,siendo dicha clave el criteriode búsqueda en consultasselectivas. La clave de indexación puede ser un identificador del fichero de datos (índice primario), o un conjuntode campos no identificadores(índicesecundario). Sobre un mismo fichero de datos se pueden definir varios índices, cada uno sobre una clave de indexación. Cualquier búsqueda selectiva de un registro en una organización indexada obliga a una consulta previa al indice (la cual proporciona Ja dirección del registro) y un posterior acceso directo al fichero de datos por medio de la dirección obtenida. Por tanto, para optimizar la eficiencia en los accesos, será convenientemantenerelíndice, siempreque sea posible, en memoriaprincipal. Este tipo de organización admite que no exista una entrada al índice por cada registro del fichero (índice no denso), en cuyo caso el fichero de datos tiene que estar ordenado por la clave de direccionamiento. Si existe una entrada por cada registro Escuela de Preparación de Opositores E.P.O. v02 INFJ3 - SAI13. Página 11 (índice denso) el fichero no necesita estar ordenado. Los indices no densos admiten la creación de indices sobre los indices, teniendo así estructuras indexadas a varios niveles (índices multinivel). Zona de Segunda zona registros de índices 1 A Primera zona 3 e de índices D J ;;iL: ~1 · 2 8 .'. ' - '<; [QI] I 8 5 E K F o 6 ç. 12 G 7 . '~~---- G., 5.. ..·J •. : 4 o ' ·R1 16 8 H ·._:.. ·v~ 9 I ,, H~. 10 J •.1 ..;: ,, : , 11 K ''12 L 13 M 14· N. 15 -o . e: 17 :a 16 p 18 R 19 s 20 T 21 u 22 V De entre todas Jas organizaciones basadas en indices destacan las secuencias indexadas (ISAM), que añaden a las ventajas de las secuenciales (rapidez en el acceso secuencial al fichero), la posibilidad de acceder directamente a ciertos registros (acceso directo) apoyándose en el índice. En este tipo de organizaciones se penalizan las actuaciones respecto a las de tipo secuencial, por la necesidad de actualizar el indice; además, se deterioran cuando se producen muchas actualizaciones. Las técnicas de indexación difieren a causa del tipo de índice (primario/secundario, denso/no denso), Ja estructura del índice (ordenado/desordenado, mononivel/multinivel), la organización del fichero de datos (serial/secuencial/disperso), y/o la forma de tratar los desbordamientos Los indices multinivel, pueden no tener un número fijo de niveles a fin de evitar desbordamientos y/o reorganizaciones del índice, así como de los datos, cuando se insertan registros; en este caso se fija previamente el número de entradas por cada nivel, y se va incrementando el número de niveles, cuando las inserciones obligan a ello. Surgen así distintos tipos de índices (binarios, equilibrados, etc.), basados, en general, en estructuras de tipo árbol. Entre todas las estructuras en árbol destacan la familia de árboles B. Los nodos del árbol son bloques del espacio de almacenamiento que contienen los valores de las claves de búsqueda y punteros a los nodos hijos; además han de contener, bien los datos, bien los punteros a los mismos. Se asegura una determinada. ocupación de los bloques no inferior al 50%, que se estabiliza en un promedio del 69%. El árbol B es un árbol especial de búsqueda con restricciones adicionales, que garantizan que siempre estará equilibrado y que su densidad es siempre superior a un determinado valor (el espacio de almacenamiento que se "desperdicia" nunca será Escuela de Preparación de Opositores E.P.O. v02 INF 13 - SA:I 13. Página l2 excesivo). Existen diversas variedades de árboles B (B\ B*, con la información asociada o separada de la estructura del árbol, etc.), siendo estas estructuras el fundamento de las organizaciones físicas en los sistemas relacionales. Los árboles B+ soportan, al igual que las estructuras ISAM, tanto acceso secuencial como directo, con la ventaja adicional de que crecen dinámicamente cuando lo hace la tabla, manteniendo además el orden de la clave de acceso. La utilización de índices mejora los tiempos de respuesta ante consultas que impliquen a los atributos indexados, pero disminuye el rendimiento de la base de datos, ya que se debe actualizar el índice cuando se actualizan los atributos sobre los que está definido, además de aumentar el espacio de almacenamiento. Por estas razones suele ser conveniente indexar la clave primaria (mediante un indice único) en el caso de que el producto no Jo haga, Jas claves alternativas que se utilicen frecuentemente (también mediante un índice único), y aquellas claves ajenas que se utilicen en combinaciones con otras tablas. Sin embargo, en tablas pequeñas, o en aquellas en que prácticamente se recuperan todas las filas, no suele ser conveniente, ya que es mejor una búsqueda secuencial. También se deberá tener eo cuenta a la bora de indexar el tipo de datos de los atributos afectados, ya que no es conveniente indexar datos de tipo carácter muy largos. 4.3. l Archivos de índices de árbol B+ La estructura de índice de árbol B+ es la más extendida de las estructuras de índices que mantienen su eficiencia a pesar de la inserción y borrado de datos. Un indice de árbol B+ toma la forma de un árbol equilibrado donde los caminos de la raíz a cada boja del árbol son de la misma longitud. Cada nodo que no es una boja tiene entre ÍnI21 y n hijos, donde n está fijopara cada árbol en particular. La estructura de árbol B+ implica una degradación del rendimiento al insertar y al borrar, además de un espacio extra. Este tiempo adicional es aceptable incluso en archivos con altas frecuencias de modificación, ya que se evita el coste de reorganizar el archivo. Además, puesto que Jos nodos podrian estar a lo sumo medio llenos (si tienen el mínimo número de hijos), hay algo de espacio desperdiciado. Este gasto de espacio adicional también es aceptable, dados los beneficios en el rendimiento aportados por las estructura de árbol B+. Estructura de árbol B+ Un indice de árbol B+ es un índice multinivel. Puede contener hasta n-1 claves de búsqueda K1, K2, ... , Kn.1, y n punteros P1, P2, ..., P0• Los valores de la clave de búsqueda de un nodo se mantienen ordenados; así, si i