unidad iii organizacion de archivos relativos

Manejo de Archivos

Introduccin a la Organizacin de Archivos RelativosUna forma efectiva de organizar un archivo cundo existe la necesidad de acceder individualmente a registros directamente, es la organizacin relativa. En un archivo relativo, existe una relacin predecible entre la llave usada para identificar un registro en particular y su localizacin dentro del archivo. Sin embargo es importante comprender que el ordenamiento lgico de los registros no necesita tener una relacin con su secuencia fsica. Los registros no necesariamente aparecen fsicamente ordenados de acuerdo con el valor de sus llaves. Entonces Cmo encontrar el n-simo registro? Cuando un archivo se establece, debe definirse una relacin que ser utilizada para obtener un valor de llave a una direccin fsica. Esta relacin R es una funcin de mapeo. Cuando se debe guardar un registro en un archivo relativo, la funcin de mapeo R se usa para traducir el valor de llave del registro a una direccin que indica donde deber almacenarse el registro. Cuando es necesario recuperar el registro con un valor de llave particular, la funcin R es aplicada a ese valor de la llave, traducindolo a una direccin donde se encuentra el registro. En contraste con los archivos secuencialmente organizados, no es necesario acceder los registros del archivo en orden serial. En lugar de esto, una ocurrencia particular de un registro se puede acceder directamente. Los archivos relativos se almacenan en dispositivos de almacenamiento de acceso directo como los discos magnticos. Los archivos relativos se usan normalmente en procesos interactivos. Una ventaja que puede reconocerse en esta organizacin es la habilidad para accesar a registros directamente. Un registro puede recuperarse, modificarse, o hasta borrarse sin afectar a otros registros en el archivo.

Direccionamiento de datosExisten dos tcnicas bsicas para direccionar la ubicacin de los registros almacenados en el disco: Unidad III: Organizacin de Archivos Relativos 1

Manejo de Archivos

Mtodo del cilindro: La direccin del registro es su nmero de cilindro, numero de superficie y numero de registro. Mtodo de sector: Cada pista del paquete esta dividida en sectores, cada sector es un rea de almacenamiento para un numero fijo de caracteres. Una direccin de registro es solamente su nmero de sector. Dado un nmero de sector, el controlador del disco puede determinar que pista deber acceder y donde reside el registro direccionado sobre tal pista.

Tcnicas de DireccionamientoExiste 3 tcnicas fundamentales utilizadas para las funciones de mapeo R, donde R es el valor de la llave o direccin. 1. Mapeo directo 2. Bsqueda en el directorio 3. Por clculo

Tcnica de mapeo directoLa tcnica ms simple para traducir una llave a una direccin de almacenamiento es el mapeo directo. El mapeo directo no es ampliamente usado.

Direccionamiento absolutoEl valor de llave suministrado por el usuario o por el programa del usuario es igual a la direccin real del registro. Cuando el registro es almacenado en el archivo, la localidad del registro debe de ser determinado por el usuario. Cuando se recupere el registro, su localizacin absoluta debe ser conocida y suministrada por el usuario.

Ventajas1. La funcin de mapeo R es muy sencilla. 2. Dado un valor de llave de un registro no requiere de tiempo y de proceso para determinar la localidad del registro en el almacenamiento secundario

Unidad III: Organizacin de Archivos Relativos

2

Manejo de Archivos

Desventajas1. Las consideraciones lgicas y fsicas no son independientes del direccionamiento absoluto; el usuario debe conocer como estn almacenados fsicamente los registros. 2. Las direcciones absolutas dependen de los dispositivos. Si fuera conveniente actualizar o cambiar el dispositivo, los valores de las llaves tambin cambiaran. 3. Las direcciones absolutas dependen del espacio direccionable. Si fuera necesario reorganizar el archivo relativo sin cambiar de dispositivo, los valores de las llaves deberan cambiarse.

Direccionamiento relativoOtro mtodo sencillo de instrumentacin de R (valor de la lave ) = direccin relativa. Una direccin relativa de un registro puede suministrarse al programa de canal para su traduccin a una direccin absoluta. La direccin relativa de un registro es el nmero ordinal del registro dentro del archivo.

VentajasLas ventajas del esquema del direccionamiento relativo son dos: 1. La funcin de mapeo R es muy sencilla. 2. Dado el valor de una llave de registro, esencialmente no se requiere tiempo de proceso para determinar la localidad del registro en el almacenamiento secundario.

Desventajas1. Las direcciones relativas no dependen tanto del dispositivo como las direcciones absolutas, sin embargo ambas, tanto las direcciones absolutas, como las direcciones relativas dependen del espacio para direcciones. 2. Algunos tipos de valores naturales de llave no son apropiados para usarse como direcciones relativas. Por ejemplo, aunque pudiesen convertirse a un equivalente numrico los valores de nombre del empleado no son buenos para usarse como direccin relativa; ni tampoco lo son muchos valores de llave numrico naturales.


3

Manejo de Archivos

Tcnicas de Bsqueda en DirectorioEste enfoque utilizado de manera muy frecuente toma ventaja de los beneficios del mapeo directo. La idea bsica es la de tener una tabla o directorio de valores de llave: pares de direcciones (o pares de direcciones relativas). En su forma ms sencilla el directorio se instrumenta como un arreglo de valores de llaves ordenadas para facilitar la bsqueda; alternativamente el directorio podra estructurarse como un rbol de bsqueda binario. Para encontrar un registro en un archivo relativo, se localiza su valor de llave en el directorio, y, despus la direccin indicada se utiliza para encontrar el registro almacenado.

Ventajas1. La direccin de un registro puede determinarse una vez que se encuentra el valor de la llave en el directorio, prcticamente sin ningn procesamiento. 2. Las llaves pueden representarse mediante formas comprensibles puesto que son traducidas internamente a direcciones. 3. La independencia lgica y fsica se alcanza, por que los valores de llave son independientes del espacio de direcciones. Si el archivo se reorganiza o cambia de dispositivo, las entradas de direcciones en el directorio debern cambiarse pero los valores de las llaves no.

Desventajas1. Es necesaria una estructura adicional para contener el directorio. 2. Para archivos relativos muy grandes el directorio ser tambin muy grande lo que puede impactar en su eficiencia al realizar bsquedas.

Tcnicas de Clculo de DireccionesLa idea bsica del calculo de direcciones es realizar un clculo sobre el valor de la llave, cuyo resultado sea una direccin relativa. Una de las desventajas del direccionamiento relativo es que se debe asignar espacio para acomodar el rango completo de valores de llave, independientemente de cuantos sean usados realmente.


4

Manejo de Archivos Consideremos una compaa de 2000 trabajadores, que desea utilizar los nmeros del seguro social como llave de acceso a los registros de un archivo de empleados, con organizacin relativa. La funcin de calculo de direccin aconsejable para este ejemplo debera mapear el conjunto dominio de valores (de 1 hasta 999999999) en aproximadamente 2000 direcciones. Un problema potencial encontrado en este proceso, es que tal funcin no puede ser uno a uno; las direcciones calculadas pueden no ser todas nicas. Esta situacin, donde R(K1)=R(K2) pero K1 K2 es llamada colisin y K1 Y K2 se conocen como sinnimos. Por lo tanto, el objetivo primordial de la funcin hash (clculo aplicado al valor de la llave para obtener una direccin) es el de generar relativamente pocas colisiones. Un conjunto de sinnimos es algunas veces llamado una clase de equivalencia. Una buena funcin hash tiene pocas clases de equivalencia y pequeas, adems de no ser demasiado compleja computacionalmente. El hashing se debe utilizar en conjuncin con la bsqueda en directorio , los beneficios de evitar el reclculo y la solucin de colisiones para los registros anteriores tienen como desventaja el costo de almacenamiento y mantenimiento del directorio. Tambin dependiendo de los patrones de organizacin de directorios y de los patrones de colisin, la bsqueda en directorio y el hashing juntos pueden conducir a mayores tiempos de bsqueda que lo que hara el hashing solo. El desempeo de la tcnica de hashing puede medirse mediante sus requerimientos de procesamiento y las necesidades de E/S para almacenar o recuperar registros. La eficiencia de una funcin hash particular depende de: 1. La distribucin de los valores de llave que realmente se usan . 2. El numero de valores de llave que realmente estn en uso con respecto al tamao del espacio de las direcciones. 3. El numero de registros que pueden almacenarse en una direccin dada sin causar una colisin (por ahora suponemos que es 1). 4. La tcnica utilizada para resolver el problema de las colisiones.


5

Manejo de Archivos

Hashing por Residuo de la DivisinLa idea bsica de este mtodo es la de dividir el valor de la llave entre un nmero apropiado, y despus de utilizar el residuo de la divisin como direccin relativa para el registro. Por ejemplo sea div el divisor, sea llave la llave y direc la direccin resultante. La funcin: R(valor de llave) puede codificarse en lenguaje C como: direc = llave % div; El residuo est definido como el resultado de restar el producto del cociente por el divisor del dividendo. En todos los casos, la direccin debe declararse como entero. Mientras que el clculo de la direccin relativa, conocidos tanto la llave como el divisor, es directo, la eleccin del divisor apropiado puede no ser realmente tan simple. Existen varios factores que deben considerarse para la seleccionar al divisor. Primero el rango de valores que resulta de la operacin llave % div, va desde 0 hasta div -1. Entonces el valor del divisor determina el tamao del espacio de direccin relativa. Si se sabe que nuestro archivo relativo va contener por lo menos n registros, entonces tendremos que hacer que div > n, suponiendo que solamente un registro puede ser almacenado en una direccin relativa dada. Segundo, el divisor debe seleccionarse de forma que la probabilidad de colisin sea minimizada. Algunas investigaciones han demostrado que los divisores pares se comportan pobremente; algunas investigaciones sugieren que los divisores debieran ser nmeros primos, sin embargo otras sugieren que los divisores no primos trabajan tan bien como los primos, siempre y cuando los divisores no primos no contengan nmeros primos pequeos como factores. Sugieren que seleccionar un nmero que no contenga ningn factor primo menor de 20 es probablemente suficiente para asegurar un buen desempeo. No es suficiente escoger un divisor que no introduzca una distribucin sesgada de direcciones. Adems se ha demostrado que independientemente de que tan bueno sea el divisor, cuando el espacio de direcciones de un archivo relativo esta completamente lleno, la probabilidad de colisin crece dramticamente. La saturacin de un archivo relativo se mide mediante su factor de carga: Unidad III: Organizacin de Archivos Relativos 6 direccin

Manejo de Archivos

Factor de carga = # registro en el archivo / mx. # de registros que puede contener el archivo

Todas las funciones hash comienzan a trabajar pobremente cuando el archivo esta casi lleno. Un factor de carga de 0.7 o 0.8 es casi lo mximo que puede tolerarse para un desempeo razonable. Por ejemplo considere el diseo de un archivo relativo que contendr alrededor de 4000 registros. El espacio de direcciones deber acomodar al menos 5 000 registros para una carga de un 80%. Un nmero aproximadamente 5 000 que no contiene actores primos menores a 20 es 5 003. La siguiente tabla ilustra la utilizacin de este divisor con un conjunto pequeo de valores de llave. valor de la llave 123456789 987654321 123456790 555555555 000000472 100064183 200120472 200120473 117400000 27000400 2762 2086 2763 2424 0473 4184 0473 0474 4606 3613 colisin colisin direccin relativa

Hashing por Medio del CuadradoEn esta tcnica la llave es elevada al cuadrado, despus algunos dgitos especificados se extraen de la mitad del resultado para constituir la direccin relativa. Si se desea una direccin relativa de n dgitos, entonces los dgitos se truncan en ambos extremos de la llave elevada al cuadrado, tomando los n dgitos intermedios. Las mismas posiciones de n-dgitos deben extraerse para cada llave. La tabla muestra el uso de esta tcnica para las mismas llaves del mtodo anterior, ntese que para acomodar 4000 registros se requieren 4 dgitos para cada direccin relativa, por lo que los dgitos 7-10 (contando desde la derecha) se extrajeron para formar cada direccin.


7

Manejo de Archivos

valor de la llave 123456789 987654321 123456790 555555555 000000472 100064183 200120472 200120473 117400000 27000400

llave al cuadrado 15241578750190521 975461055789971041 15241578997104100 308641974691358025 00000000000222784 10012860719457489 10012860719457489 40048203313502784 40048203713743729 13782760000000000

direccin relativa 8750 5789 8997 4691 0000 colisin 0719 3313 3713 0000 colisin 1600

El espacio de direccin resultante tiene lugar para acomodar 10 000 registros, dando un factor de carga de 0.4. Utilizando la funcin hashing del medio del cuadrado, el tamao del archivo resultante es de 10n, donde n es el nmero de dgitos extrados de los valores de la llave elevada al cuadrado.

Hashing por PliegueEn esta tcnica el valor de la llave es particionado en varias de las partes, cada una de las cuales (excepto la ltima) tiene el mismo nmero de dgitos que tiene la direccin relativa objetivo. Estas particiones son despus plegadas una sobre otra y sumadas. El resultado con el dgito de mayor orden truncado, si es necesario, es la direccin relativa. Por ejemplo, considere el valor de llave 123456789, y suponga que la direccin relativa objetiva tendr 4 dgitos. El valor de la llave es particionado en partes de 4 dgitos. 0001 2345 6789

Despus se pliegan uno sobre otro para dar: 1000 2345 9876


8

Manejo de Archivos Y sumados dan: 13221

El dgito de mayor orden (el que est ms a la izquierda) es truncado para dar la direccin relativa 3221. Las direcciones relativas resultantes cuando el mtodo de pliegue es aplicado a nuestro conjunto de valores de llave.

Valor de la llave 123456789 987654321 123456790 555555555 000000472 100064183 200120472 200120473 117400000 27000400

Direccion relativa 3221 8999 4321 6110 2740 4820 4752 5752 2740 2740 **colisin** **colisin** **colisin**

Igual que para el mtodo del medio del cuadrado, el tamao del espacio de direcciones relativas es una potencia de 10.

Comparacin entre las funciones hashEl mtodo del residuo ha demostrado tener los mejores resultados a comparacin de los otros 2 mtodos en la mayora de los casos. El mtodo del cuadrado medio proporciona buenos resultados con archivos que tengan bajos factores de carga, sin embargo en algunas ocasiones como en archivos densamente poblados produce demasiadas colisiones.


9

Manejo de Archivos El mtodo de pliegue puede ser la ms fcil de calcular sobre todo si se utilizan patrones de bits en lugar de nmeros decimales, sin embargo produce resultados bastante errticos (y colisiones) a menos que la longitud de la llave sea aproximadamente igual a la longitud de la direccin.

Ventajas1. Se pueden usar los valores naturales de las llaves puesto que se traducen internamente a direcciones. 2. Se logra la independencia lgica y fsica pues los valores de las llaves son independientes del espacio de direcciones.

Desventajas1. El tiempo de procesamiento requerido para la aplicacin de la funcin hash. 2. El tiempo de procesamiento y los accesos de E/S requeridos para solucionar las colisiones.

Mtodos para el Problema de ColisionesDado que una funcin hashing mapea un espacio relativamente grande de valores de llave en un espacio de direcciones relativamente pequeo, es seguro que se producirn colisiones. Considere los dos valores de llave K1 y K2 los cuales son sinnimos con la funcin hash R. Si K1 es primero almacenado en el archivo y su direccin es R (K), entonces se dice que K1 esta almacenando en su direccin de origen. Existen dos mtodos bsicos para determinar dnde debe almacenarse K2: Direccionamiento abierto: otra direccin distinta de la de origen es encontrada para K2 dentro del archivo relativo. Separacin de desborde: alguna direccin es encontrada para K2 fuera del rea principal del archivo relativo en un rea especial. de desborde, que es utilizada exclusivamente para almacenar registros que no pueden ser asignados a su direccin de origen.

Entre las tcnicas para manejar colisiones se analizarn dos de las ms comunes:


10

Manejo de Archivos Sondeo lineal, que es una tcnica de direccionamiento abierto Doble hashing, que puede ser aplicado como cualquier direccionamiento abierto o tcnica de separacin de desborde.

Sondeo LinealEs un proceso de bsqueda secuencial desde la direccin de origen para encontrar la siguiente localidad vaca. Esta tcnica es tambin conocida como mtodo de desbordamiento consecutivo. El sondeo lineal puede usarse con cualquier tcnica de hashing. La aplicacin del sondeo lineal deber hacerse en tal forma que la nueva direccin no caiga fuera del lmite del archivo. Si el sondeo lineal se usa para resolver colisiones cuando se almacenan los registros, tambin se deber usar cuando se recuperan los registros, a menos que el esquema de bsqueda en directorio se utilice en conjuncin con el hashing.

Doble HashingEl cual aplica una segunda funcin hash para combinar la llave original y el resultado del primer hash. El segundo hash puede ser el mismo archivo relativo, o un archivo relativo de sobre flujo independiente. En l segundo caso, donde solo un registro de cada clase de equivalencia aparece en el archivo principal y los sinnimos aparecen en el archivo de sobreflujo, el mtodo de desborde es utilizado. La ventaja del mtodo de separacin de desborde es que evita una situacin que puede ocurrir con el mtodo de direccionamiento abierto, en el cual un registro que no est almacenado en su direccin de origen desplaza a otro registro, el que despus buscar esa direccin de origen. El costo del mtodo de separacin de desborde es el tener que mantener al archivo separado.

Mtodos para mejorar la resolucin de colisiones.Encadenamiento de SinnimosUna buena manera de mejorar la eficiencia de un archivo relativo que utiliza el clculo de direcciones, sin directorio auxiliar para guiar la recuperacin de registros, es el encadenamiento de sinnimos. El encadenamiento de sinnimos puede emplearse con cualquier tcnica de solucin de colisiones. Mantener una lista ligada de registros con la misma direccin de origen no reduce el nmero de colisiones pero reduce los tiempos de


11

Manejo de Archivos acceso para recuperar los registros que no se encuentran en su direccin de origen. Slo los sinnimos de la llave objetivo son accesados. El encadenamiento de sinnimos se puede usar cuando se utiliza el mtodo de direccionamiento abierto o cuando se utiliza el mtodo de separacin de desborde. Esto es, la lista ligada que empieza en una direccin de origen puede tener su siguiente nodo en el mismo archivo, o en un archivo separado. El encadenamiento de sinnimos casi siempre trabaja mejor que la solucin de colisiones sin encadenamiento de sinnimos, a menos que se use el mtodo de bsqueda en el directorio para registrar donde estn realmente almacenados los registros.

Direccionamientos por CubetasOtro enfoque, en este se asignan bloques de espacio (o "cubetas"), que puedan acomodar ocurrencias mltiples de registros, en lugar de asignar celdas individuales a registros. Cuando una cubeta es desbordada, alguna nueva localizacin deber ser encontrada para el registro. Los mtodos para el problema de sobrecupo de las cubetas son bsicamente los mismos que los mtodos para manejar las colisiones con el direccionamiento de un registro por celda o ranura. Cada cubeta principal generalmente tendr un apuntador a una cadena de registros, en el rea de sobrecupo, que tendran que haber sido almacenados en la cubeta principal, pero que terminaron, en su lugar, en una cubeta de sobrecupo. Una cubeta de sobrecupo podra acomodar registros que fueran direccionados hacia diferentes cubetas principales. Los registros almacenados en una cubeta pueden ser manejados en una de dos formas: 1) pueden insertarse en el mismo orden de como llegan a la cubeta; 2) pueden mantenerse en orden segn el valor de sus llaves. De igual modo que los registros en el rea de la cubeta deben ser guardados ordenadamente, de acuerdo con su llave dentro de la cubeta, asimismo debern mantenerse en orden los registros de una cadena de sinnimos de acuerdo al valor de su llave. El uso del direccionamiento por cubetas es comn. El tamao de la cubeta puede determinarse por el tamao de una pista o de un sector de un disco o por el tamao natural de paginacin del sistema. Generalmente, el tamao de la cubeta debera ser igual al tamao del blocaje de registros para el archivo. Una ventaja importante al utilizar cubetas, que pueden contener mltiples registros es que se pueden acomodar registros de longitud variable. Con direccionamiento de cubetas y registros de longitud variable, el proceso de encontrar espacio disponible en una cubeta para


12

Manejo de Archivos un nuevo registro es ms complicado que la simple bsqueda secuencial de la prmer ranura abierta. El espacio encontrado debe ser suficientemente grande para acomodar al nuevo registro. Normalmente, el espacio es manejado en estas circunstancias manteniendo una lista ligada de huecos en la cubeta. Los huecos pueden estar dispersos entre los registros reales a causa de las supresiones. La cadena de huecos se examinar cuando se solicita espacio libre.


13

Manejo de Archivos

BibliografaS. Loomis Mary E., Estructura de datos y organizacin de archivos, 2. ed, Prentice Hall Hispanoamericana, Mexico, 1991.


14

Manejo de Archivos

Operaciones en los archivos relativosCreacinUn archivo debe ser creado en modo de acceso directo. Una vez creado se pueden agregar registros usando una tcnica de clculo de direccin para el mapeo de llave a direccin.

ActualizacinLa actualizacin (aadir registros, modificar datos de los registros y borrar lgicamente) se realiza en modo de acceso directo; se localiza el registro y, despus de realizar las modificaciones, se reescribe el registro.

RecuperacinLos registros sern recuperados en modo de acceso directo, usando la funcin de clculo de direccin.

Condiciones inesperadas (o que es lo que el programa debe validar) Lectura secuencial despus del final del archivo Lectura directa Inexistencia de registro en la direccin relativa sealada La direccin relativa especifica esta afuera del lmite del archivo Escritura secuencial. Rebasamiento del lmite del espacio en el dispositivo. Escritura directa Un registro ya existe en la direccin especificada La direccin relativa especificada esta afuera del lmite del archivo Re escritura directa Inexistencia de registro en la direccin especifica. La direccin relativa especfica cae fuera del limite del archivo


15

Manejo de Archivos

BibliografaS. Loomis Mary E., Estructura de datos y organizacin de archivos, 2. ed, Prentice Hall Hispanoamericana, Mexico, 1991.


16

unidad iii organizacion de archivos relativos

Documents