PRESENTACIÓN UNIDAD III MÉTODOS Y ORDENAMIENTO DE ARCHIVOS

Metodos y Ordenamiento de Archivos

Organización de archivos Elaborado Por: Jose David Aguirre

Docente: Miriam Lizzette Morales

ÍNDICE

Clic al icono para ir a la seccion.

Formas o métodos de Organizar archivo

Ordenamiento de Archivo

Métodos de Organización de los archivos

Ordenamiento de un archivo en memoria.

Ordenamiento Interno y Búsqueda Binaria

gracias

1. Métodos de Organización de los archivos

La organización del archivo se refiere a la organización de los datos de un archivo en registros, bloques y estructuras de acceso; esto incluye la forma en que los registros y los bloques se colocan en el medio de almacenamiento y se interconectan. Existen diferentes métodos para organizar los registros de un archivo en el disco. Hay varias técnicas generales, como el ordenamiento, la dispersión, la indización, que sirven para crear métodos de acceso. Por ejemplo, el tipo más simple y básico de organización es el de registros no ordenados. En él los registros se colocan en el archivo en el orden en que se insertan, y los registros nuevos se insertan al final del archivo.

1.1 El sistema operativo y la gestión de archivos

Sobre la estructura de periféricos de almacenamiento disponibles en el ordenador, el sistema operativo construye dos abstracciones. La primera es la creación de archivos, ello aislará al usuario de los problemas físicos de almacenamiento. Así, cuando deseemos referirnos a un conjunto de información del mismo tipo, como una unidad de almacenamiento única, bastará con crear un archivo dándole el nombre que considere oportuno. La segunda abstracción es lo que se denomina directorio. Los directorios son conjuntos de archivos agrupados de acuerdo con un libre criterio (teniendo en cuenta los usuarios que lo han creado, o el contenido de los archivos, etc.).

2. Formas o métodos de Organizar archivos

2.1 Organización Secuencial.

En los archivos de datos con organización secuencial los registros de datos se graban en el archivo uno detrás de otro, sin dejar huecos. La grabación de dichos registros se lleva a cabo exactamente en el mismo orden en que fueron introducidos por el capturista y tienen la característica que existe un campo en cada registro que es único (campo llave) y que se utiliza para identificar cada registro.

Registros grabados en forma secuencial (Uno detrás de otro)

+ info

Características de los archivos secuenciales

1. La escritura de nuevos registros siempre se hace al final del archivo. 2. Para leer una zona concreta del archivo hay que avanzar siempre, si la zona está antes de la zona actual de lectura, será necesario “rebobinar” o regresar el puntero de lectura del archivo. 3. Los archivos sólo se pueden abrir para lectura o para escritura, nunca de los dos modos a la vez.

2.2 ISAM (Método de acceso secuencial Indexado)

En esta organización se dispone de una tabla de índices adicional; entenderemos como índice, una referencia que permite obtener de forma automática la ubicación de la zona del archivo físico donde se encuentra el registro buscado. Este permite localizar un registro por medio de su clave sin recorrer previamente todos los que le preceden. Un diccionario sería un ejemplo de archivo secuencial indexado, ya que en cada página tenemos dos niveles, el superior que nos dice cuál es la letra inicial de la palabra y el inferior la cabecera de cada página, de forma que en un ordenador, guardaríamos en la tabla de índices las letras y las cabeceras, que nos dicen en que página ir a buscar la palabra deseada. La organización secuencial indexada implica un mantenimiento de las tablas de índices y una previsión inicial de la cantidad máxima de registros que va a contener.

Búsqueda secuencial

Manejar usando una lista

Elegir representantes de los bloques

Formación de bloques

Acceso secuencial indexado

Se utiliza para el acceso a un archivo de forma muy rápida, la manera es la siguiente

Las características más relevantes de un archivo indexado, son las siguientes

3. Solamente se puede grabar en un soporte direccionables. Ej.: disco magnético. Si esto no fuera así no podría emplear el acceso directo.

2. Permiten utilizar el modo de acceso secuencial y el modo de acceso directo para leer la información guardada en sus registros.

1. El diseño del registro tiene que tener un campo, o combinación de campos, que permita identificar cada registro de forma única, es decir, que no pueda haber dos registros que tengan la misma información en él. A este campo se le llama campo clave y es el que va a servir de índice.

Ventajas de archivos secuenciales indexados.

vs

DESVENTAJAS DE ARCHIVOS SECUENCIALES

Ventajas de archivos secuenciales

1. Ocupa más espacio en el disco que los ficheros secuénciales, debido al uso del área de índices. 2. Tiene tendencia a que aumente el tiempo medio de acceso a los registros, cuando se producen muchas altas nuevas con claves que hay que intercalar entre las existentes, ya que aumenta el área de overflow. 3. Solo se puede utilizar soportes direccionables.

1. Permite el acceso secuencial. 2. Permite el acceso directo a los registros. 3. Se pueden actualizar los registros en el mismo fichero, sin necesidad de crear un fichero nuevo de copia en el proceso de actualización.

Estructura de la organización secuencia indexado.

Este tipo de organización se utiliza cuando existe la necesidad tanto de acceder a los registros secuencialmente, por algún valor de llave, como de acceder los individualmente. Un archivo secuencial indexado puede tener acceso porque manejan un archivo secuencial y un archivo relativo o de acceso directo. El tipo de sus registros contiene un campo clave identificador. Los registros están situados en un soporte direccionable por el orden de los valores indicados por la clave.

2.3 Organización Directa

En esta organización, la ubicación del registro en el soporte físico, se obtiene directamente a partir de funciones que la obtienen a partir del valor de la clave, mediante un algoritmo de transformación (hashing) de ésta. Un archivo para que pueda estar dotado de una organización directa tiene que cumplir dos condiciones: a) que sus registros sean de longitud fija y b) su propio tamaño tiene que estar prefijado, lo que determina la distribución de la información, al tiempo que limita la cantidad de registros que podrá contener.

+ info

2.4 Operaciones Fundamentales de Archivos

Los archivos informáticos son el medio de que disponemos para almacenar información no volátil en un dispositivo de almacenamiento. Los Sistemas de archivos de que disponen los sistemas operativos disponen de mecanismos para que un usuario pueda manipular los archivos (seleccionar, editar, ejecutar, borrar). Desde el punto de vista de un programador un archivo es un medio para poder leer datos de entrada para su programa o donde poder guardar los resultados de su ejecución. Todo lenguaje de programación debe disponer de algún mecanismo para que el programador pueda manipular archivos desde un programa.

A continuación se describen las seis operaciones básicas sobre archivos

04

02

03

01

05

Reposicionarse dentro de un archivo

Leer un archivo

Crear un archivo

Escribir un archivo

Borrar un archivo

2.5 Comandos para la gestión de archivos en Windows

Comando: MOVE

Comando: REN o RENAME

Comando: DEL

Comando: ERASE

2.5 Comandos para la gestión de archivos en Windows

Comando: FC

Comando: UNDELETE

Comando: XCOPY

Comando: DOSKEY

3. Ordenamiento de Archivos

Ordenamiento significa reagrupar o reorganizar un conjunto de datos u objetos en una secuencia especifica. La búsqueda binaria funciona correctamente sólo si el arreglo está ordenado según el mismo criterio con el que se realiza la búsqueda. El objetivo de estudiar los algoritmos de ordenamiento es doble. Primero, porque permite ejemplificar la importancia del estudio de la eficiencia de los algoritmos, mostrando que no es intuitivo predecir cuanto tiempo de ejecución toman. Y segundo, porque los computadores pasan típicamente 50% de su tiempo ordenando (de ahí que los españoles y franceses prefieren usar la palabra ordenador en vez de computador). Parece lógico entonces conocer cuáles son los algoritmos que se usan para ordenar.

Los algoritmos de ordenamiento se pueden clasificar en las siguientes maneras

Algoritmos de ordenamiento externo: en un lugar externo como un disco duro.

Algoritmos de ordenamiento interno: en la memoria del ordenador.

POR EL TIEMPO QUE TARDAN EN REALIZAR LA ORDENACIÓN

• Burbuja.
• Quicksort.
• ShellSort.
• Radix

• Ordenación natural
• Ordenación no natural
• Por estabilidad

• Intercalación
• Mezcla Directa
• Mezcla Natura

4. Ordenamiento Interno y búsqueda Binaria

Cuando hacemos una búsqueda de algún registro, ésta se hace principalmente a través de las llaves primarias.

Se pueden realizar búsquedas secuenciales o de acceso directo.

Es necesario poder hacer búsquedas de registros en los archivos, siguiendo algún criterio o patrón.

Las búsquedas secuenciales son demasiado lentas ya que tienen que recorrer todo o casi todo el archivo; aun cuando se encuentre algún resultado podríamos saber de antemano que existe la posibilidad de encontrar más registros que cumplan con el criterio de búsqueda, de ahí que se deba continuar recorriendo todo el archivo.

Por otro lado las búsquedas por acceso directo son extremadamente rápidas, ya que podemos ir al “offset” deseado dentro del archivo, desafortunadamente esto requiere un método o fórmula para saber ubicar donde se encuentra un registro en el archivo.

5. Ordenamiento de un archivo en memoria.

Como mencionábamos el ordenar un archivo es muy lento ya que se requerirían muchas “pasadas” por los mismos registros varias veces para poder hacer el ordenamiento; sin olvidar que tenemos: posicionar, leer, posicionar, escribir y esto de repite muchas veces.Una solución es lo que se conoce como “¡nternal sorting” u “ordenamiento interno”, el cual consiste en leer todo el archivo en memoria, secuencialmente, ordenarlo en la memoria primaria y entonces volver a bajarlo a disco. Esto teóricamente es lo ideal ya que el tiempo que toma hacerlo es demasiado corto.

DESAFORTUNADAMENTE PARA NUESTRO FIN (BÚSQUEDA BINARIA) TIENE SUS INCONVENIENTES

La Búsqueda Binaria requiere más de 1 o 2 accesos para encontrar en el archivo

El Ordenamiento Interno sólo funciona para archivos pequeños

Mantener el archivo ordenado es demasiado caro

- Si el archivo es demasiado grande no tendremos la suficiente memoria RAM para tener todo el archivo - Es importante notar que cuando la memoria RAM se acaba no nos marcará un error, se empezará a utilizar memoria virtual, la cual al estar basada en disco nos conduce al mismo problema.

- Para archivos grandes, ej 1,000 registros el promedio de accesos es de 9.5 y para uno de 100,000 sería de 16. - Recordemos que nuestra meta cuando hablamos de archivos es tratar de ir lo menos posible al disco, así que lo anterior no es alentador.

- Si tenemos el proceso de agregar nuevos registros es demasiado frecuente - Podemos mantener parte del archivo y parte sin ordenar, pero en esa parte se necesitará una búsqueda secuencial.

"Dime y lo olvido, enséñame y lo recuerdo, involúcrame y lo aprendo"

Benjamín Franklin

¡GRACIAS!