2.- Organizaciones básicas

Gracias por tu comentario compañero Erick no mencionamos las ventajas que nos mencionas ya que no tenia conocimiento de ello pero eso nos sirve para poder mejorar nuestro trabajo en la próxima actividad.

1) Investigar los diferentes tipos de organizaciones de archivos (Organización secuencial, secuencial indexado y Directas), así como, las ventajas y desventajas de cada una de las organizaciones básicas de archivo. Hacer uso de TICs de software (Wikis, Foros, Edu-Blogs, WebQuest, EVE-A). Elaborar una tabla comparativa acerca de lo investigado, o en su defecto, debe diseñar un mapa conceptual o diagrama, que debe compartir en este Foro.


ORGANIZACIONES DE ARCHIVOS


TIPO

CONCEPTO

VENTAJAS

DESVENTAJAS
SECUENCIAL
Es la forma básica de organizar un conjunto de registros, que forman un archivo, utilizando una organización secuencial. Consiste en guardar la información en el archivo de manera lineal, es decir, línea por línea (o estructura por estructura), un dato detrás de otro, hasta llegar al fin de archivo. -Acceso eficiente a todos los datos.
-Menor uso de espacio de almacenamiento.
-Acceso lento a registros específicos.
SECUENCIAL INDEXADO
Se utiliza este tipo de organización de archivo cuando existe la necesidad tanto de acezar los registros secuencialmente, por algún valor de llave, como de acezarlos individualmente. -Los registros están organizados en una secuencia basada en un campo.
-Más rápida que la organización secuencial.
-Más eficiente que la organización directa.
-Menor eficiente que la secuencial.
-Menos rápida que la directa.
DIRECTA
consiste en guardar la información de "manera directa", es decir, no
lleva un orden especifico, pero se pueden localizar los datos haciendo uso de sus "direcciones"
(saltando registro o líneas), sin necesidad de leer completamente todos los datos
-Acceso rápido a registros específicos. -Ineficiente acceso a la totalidad o gran parte de los registros.
-Mayor uso de espacio de almacenamiento.


2) Investigar acerca las características de los métodos de búsqueda y ordenamiento (al menos dos de cada uno). Desarrollar un resumen o tabla comparativa o mapa conceptual o diagrama para representar lo investigado en forma textual o gráficamente, el cual debe compartir en este foro.


METODOS DE ORDENAMIENTO Y DE BUSQUEDAS


METODO DE ORDENAMINETO

CONCEPTO

CARACTERISTICAS
BURBUJA
Funciona revisando cada elemento de la lista que va a ser ordenada. -Es bastante sencillo
-En un código reducido se realiza el ordenamiento
-Eficaz
QUICKSORT
Este método es una mejora sustancial del método de intercambio directo y recibe su nombre por la velocidad con la que ordena los elementos del arreglo. -El método de ordenamiento Quick Sort es actualmente el más eficiente y veloz de los métodos de ordenación interna.
INSERCCION
Parecido al método de burbuja, utilizado para ordenar n elementos. -Para ordenar los elementos tomamos como numero pivote el primer número del lado izquierdo
METODO DE BUSQUEDA

CONCEPTO

CARACTERISTICAS
SECUENCIAL
Consiste en revisar cada elemento por elemento hasta encontrar el dato que estamos buscando. -La búsqueda se puede realizar en arreglos desordenados.
El método es totalmente confiable.
-El número de comparaciones es significativa si el arreglo es muy grande.
BINARIA
La búsqueda binaria utiliza un método de ´divide y vencerás´ para localizar el valor deseado. Con este método se examina primero el elemento central de la lista; si éste es el elemento buscado, entonces la búsqueda ha terminado. -Sirve únicamente para arreglos ordenados.
-Es más eficiente que el método de búsqueda secuencial, debido a que el número de comparaciones se reduce a la mitad por cada iteración del método.
BUSQUEDA UTILIZANDO EL METODO HAST
Aumenta la velocidad de búsqueda sin necesidad de tener los objetos ordenados. -Se pueden usar los valores naturales de la llave, puesto que se traducen internamente a direcciones fáciles de localizar.
-Se logra independencia lógica y física, debido a que los valores de las llaves son independientes del espacio de direcciones.

Estoy muy de acuerdo con mi compañero eulices y abel su trabajo esta muy bien relizado

Mi replica va dirigida a los compañeros JONIFER VEGA BANDERAS Y RANFERI GUADALUPE RIOS
creo que su información es un poco insípida, carece de estructura y de información así como especificar las ventajas y desventajas de cada organización, tambien resaltar cada organización y método de búsqueda, el lector se pierde entre la insipidez del texto y no sabe diferenciar donde acaba una organización y donde empieza otra, habría que ser mas estructurado y resaltar el texto para no perderse.

ATT: Alberto Quiroz Albarran

Bueno en mi opinión estoy de acuerdo con mis compañers ERIK LAZARO TORRES, RICARDO SUAZO BUENAS, Y ENRIQUE GOICOCHEA PINEDA, sin embargo creo que les falto mencionar algunas ventajas mas sobre los tipos de organizaciones básicas, ya que creo que faltan muchas mas, por ejemplo en la secuencial les falto entre sus ventajas:
-Se gravan consecutivamente cuando el archivo se crea.
- se debe acceder consecutivamente cuando se leen dichos registros.
- Todos los dispositivos de memoria soportan este tipo de organización.

RANFERI GUADALUPE RIOS

mi participación de reconocimiento es para el compañero eulises quien dio una explicación clara y concentra en la extensión de las dos preguntas las cuales decidió responder, de acuerdo a lo dicho por el estoy en total acuerdo y ademas una manera clara de la cual puede conocer el tema.

Mi replica va dirigida a mis compañeras Mercedes Guadalupe y Karla Yesenia, concuerdo con las definiciones, ventajas y desventajas que ellas explicaron en su participación, mi única opinión seria que profundizaran un poco mas el tema y nos dieran a conocer un poco mas del tema que explicaron.

Atte: Luis Angel Zapata Perez

DESDE MI PUNTO DE VISTA, TU PARTICIPACIÓN ESTA MUY CORRECTA, ES IMPORTANTE CONOCER TANTO LAS VENTAJAS Y DESVENTAJAS DE LOS TIPOS DE ORGANIZACIONES, ASÍ COMO SUS CARACTERÍSTICAS Y LAS OPERACIONES QUE SE PUEDEN REALIZAR CON CADA TIPO DE ORGANIZACIÓN, ESTO CON EL FIN DE CONOCER Y SABER QUE TIPO DE ORGANIZACIÓN UTILIZAR PARA OBTENER MAYOR EFICACIA A LA HORA DE IMPLANTARLO.

Los felicito por sus investigaciones, aportaciones y participaciones, sobre todo por que han sabido mantener un debate sano con comentarios muy contundentes.
Y con respecto a la programación en lenguaje Java, debemos procurar incursionar en algún lenguaje de programación, sobre todo, si es del grupo de los "libres" y que permitan el desarrollo de aplicaciones en dispositivos móviles, ya que parece ser una tendencia. Yo particular recomendaría Java por el aspecto de compatibilidad con equipos de cómputo o infraestructura disponible en nuestra región, pero si se les dificultare la estructura del lenguaje, podeís probar Python, que resulta más sencilla la implementación, aunque habría que valorar o probar con equipo de nuestro entorno.
Finalmente, los felicito nuevamente ya que aprecio han alcanzado la competencia específica de la unidad.

ATTE:

M.C. Edgar Rangel Lugo.

1) Investigar los diferentes tipos de organizaciones de archivos (Organización secuencial, secuencial indexado y Directas), así como, las ventajas y desventajas de cada una de las organizaciones básicas de archivo. Hacer uso de TICs de software (Wikis, Foros, Edu-Blogs, WebQuest, EVE-A). Elaborar una tabla comparativa acerca de lo investigado, o en su defecto, debe diseñar un mapa conceptual o diagrama, que debe compartir en este Foro.



http://archivosecuencial.blogspot.mx/2009/09/3-estructura-de-la-organizacion_29.html
http://romerovivivi.blogspot.mx/p/3-archivo-secuencial-indexado.html
https://es.slideshare.net/TiFoN87/exposicion-organizacin-directa-5411145

EquipoDinamita:
Alan Henry Alcantar Medrano.
Jose Ramon Ortiz Lopez.
Natolio Tapia Mondragon.
Agustin Vivas Pineda.
Daniel Macedonio Bedolla.
Jonathan Urieta Albarran.

2) Investigar acerca las características de los métodos de búsqueda y ordenamiento (al menos dos de cada uno). Desarrollar un resumen o tabla comparativa o mapa conceptual o diagrama para representar lo investigado en forma textual o gráficamente, el cual debe compartir en este foro.

RESUMEN:
---METODOS DE BUSQUEDA---
Los métodos de búsqueda pueden clasificarse según la ubicación de los datos sobre los que se realizara la búsqueda. Existen dos clases:
• Métodos de Búsqueda Interna
• Métodos de Búsqueda Externa.

"METODOS DE BUSQUEDA INTERNA"
Se denomina búsqueda interna cuando todos los elementos se encuentran en la memoria principal. Por ejemplo, almacenados en estructuras estáticas (arreglos) o en estructuras dinámicas (listas ligadas y arboles).
Los métodos de búsqueda mas importantes son:
• Secuencial o lineal
• Binaria
• Por transformación de claves

-BUSQUEDA SECUENCIAL
• Búsqueda secuencial consiste en revisar elemento por elemento hasta encontrar el dato buscado, o hasta llegar al final de la lista de datos disponible.
-CARACTERISTICAS
• La búsqueda se puede realizar en arreglos desordenados.
• El método es totalmente confiable.
• El numero de comparaciones es significativa si el arreglo es muy grande.
• En arreglos desordenados de N componentes puede suceder que el elemento no se encuentre, por lo tanto se harán N comparaciones al recorrer todo el arreglo
• Cantidad mínima de comparaciones es 1.
• Cantidad media de comparaciones es (1+N)/2.
• Cantidad máxima de comparaciones es N.

-BUSQUEDA BINARIA
• La búsqueda binaria utiliza un método de `divide y vencerás' para localizar el valor deseado. Con este método se examina primero el elemento central de la lista; si éste es el elemento buscado, entonces la búsqueda ha terminado.
• En caso contrario, se determinar si el elemento buscado será en la primera o la segunda mitad de la lista y a continuación se repite este proceso, utilizando el elemento central de esa sub-lista.
-CARACTERISTICAS
• Sirve únicamente para arreglos ordenados.
• Es mas eficiente que el método de búsqueda secuencial, debido a que el numero de comparaciones se reduce a la mitad por cada iteración del método.
• Cantidad mínima de comparaciones es 1.
• Cantidad media de comparaciones es (1+log₂(N))/2.
• Cantidad máxima de comparaciones es log₂(N).

-BUSQUEDA POR TRANSFORMACION DE CLAVES (HASH)
• Aumenta la velocidad de búsqueda sin necesidad de tener los objetos ordenados.
• El tiempo de búsqueda es totalmente independiente del numero de componentes del arreglo.
• La búsqueda se realiza por medio de direcciones, creadas por una función hash(H).
-FUNCIONES HASH
• Las Funciones HASH (H) mas aplicadas son:
• Función Modulo (Por división).
• Función Cuadrado.
• Función Plegamiento.
• Función Truncamiento.

"METODOS DE BUSQUEDA EXTERNA"
• Se denomina búsqueda externa cuando todos los elementos se encuentran en memoria secundaria (archivos almacenados en dispositivos tales como cintas y discos magnéticos).


---METODOS DE ORDENAMIENTO---
Debido a que las estructuras de datos son utilizadas para almacenar información, para poder recuperar esa información de manera eficiente es deseable que aquella esté ordenada. Existen varios métodos para ordenar las diferentes estructuras de datos básicas.
En general los métodos de ordenamiento no son utilizados con frecuencia, en algunos casos sólo una vez. Hay métodos muy simples de implementar que son útiles en los casos en dónde el número de elementos a ordenar no es muy grande (ej, menos de 500 elementos). Por otro lado hay métodos sofisticados, más difíciles de implementar pero que son más eficientes en cuestión de tiempo de ejecución.

-ORDENAMIENTO DE BURBUJA
La Ordenación de burbuja (Bubble Sort en inglés) es un sencillo algoritmo de ordenamiento. Funciona revisando cada elemento de la lista que va a ser ordenada con el siguiente, intercambiándolos de posición si están en el orden equivocado. Es necesario revisar varias veces toda la lista hasta que no se necesiten más intercambios, lo cual significa que la lista está ordenada. Este algoritmo obtiene su nombre de la forma con la que suben por la lista los elementos durante los intercambios, como si fueran pequeñas "burbujas". También es conocido como el método del intercambio directo. Dado que solo usa comparaciones para operar elementos, se lo considera un algoritmo de comparación, siendo el más sencillo de implementar.

-ORDENAMIENTO SHELL
El algoritmo Shell sort mejora el ordenamiento por inserción comparando elementos separados por un espacio de varias posiciones. Esto permite que un elemento haga "pasos más grandes" hacia su posición esperada. Los pasos múltiples sobre los datos se hacen con tamaños de espacio cada vez más pequeños. El último paso del Shell sort es un simple ordenamiento por inserción, pero para entonces, ya está garantizado que los datos del vector están casi ordenados.

-ORDENAMIENTO POR INSERCION
El ordenamiento por inserción (insertion sort en inglés) es una manera muy natural de ordenar para un ser humano, y puede usarse fácilmente para ordenar un mazo de cartas numeradas en forma arbitraria. Requiere O(n²) operaciones para ordenar una lista de n elementos.

-ORDENAMIENTO POR SELECCION
El ordenamiento por selección (Selection Sort en inglés) es un algoritmo de ordenamiento que requiere O(n^2) operaciones para ordenar una lista de n elementos.
Su funcionamiento es el siguiente:
Buscar el mínimo elemento de la lista
Intercambiarlo con el primero
Buscar el mínimo en el resto de la lista
Intercambiarlo con el segundo
Y en general:
Buscar el mínimo elemento entre una posición i y el final de la lista
Intercambiar el mínimo con el elemento de la posición i.

http://estdatosgrupo8a.blogspot.mx/2009/05/metodos-de-busqueda.html
http://iutprogramacion.blogspot.mx/2013/02/metodos-de-ordenamiento.html

EquipoDinamita:
Alan Henry Alcantar Medrano.
Jose Ramon Ortiz Lopez.
Natolio Tapia Mondragon.
Agustin Vivas Pineda.
Daniel Macedonio Bedolla.
Jonathan Urieta Albarran.

Investigar los diferentes tipos de organizaciones de archivos (Organización secuencial, secuencial indexado y Directas), así como, las ventajas y desventajas de cada una de las organizaciones básicas de archivo. Hacer uso de TICs de software (Wikis, Foros, Edu-Blogs, WebQuest, EVE-A). Elaborar una tabla comparativa acerca de lo investigado, o en su defecto, debe diseñar un mapa conceptual o diagrama, que debe compartir en


aqui esta la imagen y le dejamos ese link para que pueda analisarla con detalle !





2) Investigar acerca las características de los métodos de búsqueda y ordenamiento (al menos dos de cada uno). Desarrollar un resumen o tabla comparativa o mapa conceptual o diagrama para representar lo investigado en forma textual o gráficamente, el cual debe compartir en este foro.


Los registros se organizan en una secuencia basada en un campo clave presentando dos características, un índice del archivo para soportar los accesos aleatorios y un archivo de desbordamiento. El índice proporciona una capacidad de búsqueda para llagar rápidamente al registro deseado y el archivo de desbordamiento es similar al archivo de registros usado en un archivo secuencial, pero está integrado de forma que los archivos de desbordamiento se ubiquen siguiendo un puntero desde su registro predecesor.

La estructura más simple tiene como índice un archivo secuencial simple, cada registro del archivo índice tiene dos campos, un campo clave igual al del archivo principal y un puntero al archivo principal. Para encontrar un campo especifico se busca en el índice hasta encontrar el valor mayor de la clave que es iguale o precede al valor deseado de la clave, la búsqueda continua en el archivo principal a partir de la posición que indique el puntero.

Cada registro del archivo principal tiene un campo adicional que es un puntero al archivo de desbordamiento. Cuando se inserta un nuevo registro al archivo, también se añade al archivo de desbordamiento. El registro del archivo principal que precede inmediatamente al nuevo registro según la secuencia lógica se actualiza con un puntero del registro nuevo en el archivo de desbordamiento, si el registro inmediatamente anterior está también en el archivo de desbordamiento se actualizará el puntero en el registro.

Para procesar secuencialmente un archivo completo los registros del archivo principal se procesarán en secuencia hasta encontrar un puntero al archivo de desbordamiento, el acceso continúa en el archivo de desbordamiento hasta que encuentra un puntero nulo, entonces renueva el acceso donde se abandonó en el archivo principal.

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



a) 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. Un mismo fichero puede tener mas de un campo clave, pero al menos uno de ellos no admitirá valores duplicados y se le llama clave primaria. A las restantes se les llama claves alternativas.



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

El modo de acceso directo se hace conociendo el contenido del campo clave del registro que queremos localizar. Con esa información el sistema operativo puede consultar el índice y conocer la posición del registro dentro del fichero.



En el modo de acceso secuencial los registros son leídos ordenados por el contenido del campo clave, independientemente del orden en que se fueron grabando (El orden lógico no es igual al orden físico), debido a que el acceso a los datos se hace a través del índice, que para hacer más fácil la búsqueda de los registros permanece siempre ordenado por el campo clave.



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



VENTAJAS

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.



DEVENTAJAS



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.

4. Obliga a una inversión económica mayor, por la necesidad de programas y, a veces, hardware más sofisticado.

3.1 ESTRUCTURA DE LA ORGANIZACIÓN SECUENCIAL 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.

Un archivo secuencial indexado contiene



un archivo índice y un archivo de datos. Es necesario que los registros contengan un campo clave para identificarlos y que estén almacenados en un soporte direccionable según el orden que indique dicha clave. El archivo índice agilizar la búsqueda dentro del fichero. El fichero de datos se organiza, lógicamente, en bloques o páginas de varios registros.



. Cada registro del fichero índice almacena:



• El valor del campo clave del último registro de un bloque. Los bloques están constituidos por un número fijo de registros consecutivos.



• La dirección del primer registro de dicho bloque. Puede haber un área de desbordamiento. Ocupa más espacio en disco pero es más rápido. Puede almacenarse el fichero índice en memoria. Habría que calcularlo al iniciar una sesión de trabajo.



En este tipo de organización de archivos se dispone de una tabla en que aparecen ordenados secuencialmente los números de la clave del archivo y asociados a cada uno de ellos de da la dirección del registro correspondiente.



AREAS DEL ARCHIVO SECUENCIAL INDEXADO



Área de Datos: Contiene los registros secuencial, esta ordenados alfabéticamente o alfanuméricamente y no deja espacios.



Área de índice: Los niveles de índice están contenidos en una tabla, si existieran varios índices enlazados se denomina nivel de indexación



Área de Desbordamiento o Excedentes: Esta área es utilizada para realizar actualizaciones si ello es necesario



FICHEROS CON ORGANIZACIÓN SECUENCIAL INDEXADA.



Un archivo con organización secuencial indexada está formado por:



AREA DE DATOS: Es el área en la que se escriben los registros cuando el archivo es creado el en directorio del fichero.



Los ficheros con organización secuencial indexada se graban en un soporte de almacenamiento directo, en secuencia ascendente, de acuerdo con los valores de la clave y en páginas o bloques de longitud fija.



El AREA DE INDICES: es creada por el sistema al mismo tiempo que se van almacenando los datos. Contiene una tabla que asocia las claves con las direcciones de los registros en el área de datos.



Cada entrada del área de índices está formada por el valor más alto de la clave de cada grupo de registros y un puntero con la dirección del primer registro del grupo.



Un AREA DE EXCEDENTES: donde se graban los registros que no tienen sitio en el área de datos. Los nuevos registros se insertan y quedan enlazados entre sí mediante punteros conservando el orden lógico que marca la clave o índice principal.



Del tratamiento de los índices y punteros se encarga el sistema operativo por lo que no va a crear problemas al usuario cuando maneja este tipo de ficheros. El usuario sabe lo que sucede cuando solicita una consulta de un registro, pero no sabe cómo se realiza internamente esa consulta.



3.2 REPRESENTACIÓN DE INDICES



El campo clave-secundaria sobre el cual se crea un índice se llama clave inversa o clave indexada. Se dice entonces que el campo es inverso para la recuperacion por clave secundaria. La figura muestra un archivo de estudiantes y sus índices asociados: un índice valor clave y un nombre clave. Las dos claves inversas son CLASS y AGE. Cada entrada del índice valor clave consiste en un valor de clave secundaria y en un conjunto de señaladadores a los registros de datos. Un señalador



Puede contener en una dirección relativa, una dirección física o una clave principal de los registros objetos.



DIRECCION RELATIVA El campo señalador en el índice valor clave de la fig. Contiene direcciones relativas. Para ejemplificar, la primera entrada del índice indica que los registros uno, cuatro y cinco contienen el valor clave 541 en el campo CLASS. SEÑALADOR SIMBOLICO Un señalador simbólico es un identificador de registros, pero no una dirección de registro. Por ejemplo, un valor de clave primaria puede usarse como señalador simbólico porque identifica de manera única a un registro del archivo. Si se escoge al señalador simbólico como identificador de registro, la primera entrada del índice en el índice valor clave de la fig. Contendría: Valor de clave secundaria señalador de registro • 541 150, 164,172 los valores 150, 164 y 172 son los valores de las claves primarias (S-ID) de los registros 1,4 y 5, respectivamente. Estos valores de clave-primaria pueden traducirse a su dirección de registro correspondiente por medio de distribución o búsqueda de índice (Hamhung) dependiendo de la organización básica de archivo subyacente, es decir, directa o secuencial indexada.

DIRECCION FISICA El campo señalador puede contener direcciones físicas, las cuales pueden usarse para acezar registros directamente sin necesidad de traducir la dirección, como fue necesario en los casos 1) y 2). Sin embargo, la mayor desventaja del uso de las direcciones reales, es que los valores del señalador dependen entonces del dispositivo. Por ejemplo, hay que recrear un índice si los datos del archivo emigran de un disco a otro. Cada entrada en el índice nombre clave en la fig. Consiste en un nombre clave-inversa y un señalador hacia la primera entrada del índice valor-clave. Los distintos índices en una organización inversa juntos forman un directorio. ¿Cómo responde un sistema inverso de archivos a las consultas sobre las claves secundarias? Considérese la siguiente consulta en el archivo inverso de la fig. Listar los nombres de los estudiantes cuya edad sea 21 años. Puede responder rápidamente buscando en el directorio de la manera siguiente: • empezar la búsqueda con el índice nombre-clave para localizar la entrada AGE. • Analizar el índice valor-clave para encontrar el valor 21 en la clave secundaria. • Recuperar los registros objetivos del archivo de datos en las direcciones relativas 3y 7. Se dice que se tiene un índice denso cuando este incluye cada valor clave posible en un conjunto indexado. El índice valor- clave de la fig. Es denso porque todos los valores de las claves inversas están incluidos en el índice. Por ejemplo, los tres números posibles de CLASS en el archivo de datos son 541, 542, y 543. Los tres aparecen en el índice valor-clave. Se dice que una clave inversa está parcialmente indexada si solo algunos de sus valores claves están incluidos en el índice valor-clave. Los valores clave que están indexados son aquellos usados en la condiciones de búsqueda. Un índice parcialmente indexado se llama índice disperso. Para un índice con una gran cantidad de elementos, la búsqueda secuencial sobre el índice no es muy eficiente. Por esto, un índice se organiza generalmente como una estructura de varios niveles como es el caso de la estructura multinivel de índice principal para los archivos secuenciales indexados. El directorio para el archivo de datos de la fig. Esta organizado como un índice de nivel dos, en el cual el índice nombre-clave se crea para facilitar la búsqueda en el índice valor-clave. El grado de inversión se refiere al nivel de totalidad de inversión expresada por el número de campos y lo extenso de los valores de los campos invertidos. Una inversión de 0% significa que no se invirtió ningún campo clave en un registro. Por otro lado, un archivo con el 100% de inversión tiene invertido cada valor clave de cada campo de datos. En algunos sistemas operativos macro mainframe se dispone de elementos para invertir índices automáticos si se declaran las claves secundarias en un programa, por ejemplo. VSAM de IBM y AAM de Cyber, son capaces de crear índices inversos sobre la organización secuencial indexada y directa. MANEJO DE INDICES Cada vez que se inserta, borra o actualiza un registro, las entradas afectadas de un índice deben ser modificadas por el sistema para que así, el índice pueda proporcionar las trayectorias de datos correctas.



3.3 OPERACIONES SOBRE UN ARCHIVO SECUENCIAL.



Los archivos secuenciales son típicamente utilizados en aplicaciones de proceso de lotes Y son óptimos para dichas aplicaciones si se procesan todos los registros. La organización secuencias de archivos es la única que es fácil de usar tanto en disco como en cinta.



Para las aplicaciones interactivas que incluyen peticione s o actualizaciones de registros individuales, los archivos secuenciales ofrecen un rendimiento pobre.



Normalmente un archivo secuencial se almacena en bloques, en un orden secuencial



Simple de los registros. La organización física del archivo en una cinta o disco se corresponde exactamente con la ubicación lógica del archivo. En este caso, el procedimiento para ubicar los nuevos registros en un archivo de pila separado, llamado archivo de registro (log file) o archivo de transacciones. Periódicamente, se realiza una actualización por lotes que mezcla el archivo de registro con el archivo maestro para producir un nuevo archivo en secuencia correcta de claves estructura y manejo de archivos secuenciales con el fin de proporcionar una secuencia para los registros, se define una llave para cada uno.

Uno o más atributos se volverán los atributos llave para los registros en los archivos. el conjunto de valores para los atributos llave generalmente identifica el objeto descrito por el registro; es decir, el número de placa de un automóviles el nombre de une persona. Se espera poder identificar los registros en forma única con base en sus llaves. entonces los registros en el archivo se conservan en el orden de acuerdo con los atributos llave. Un atributo llave proporcionara la llave primaria de clasificación de alto orden y si este atributo no identifica en forma única al objeto, entonces puede identificarse atributos llave secundarios o inferiores hasta que el orden se determine por completo.



La lectura serial del archivo en este orden puede realizarse ahora en forma secuencial. Algunas veces se agregan campos artificiales conteniendo números de secuencia o identificación, para obtener atributos llave únicos.

La participación del archivo, analizada con la descripción de archivo de apilo ahora se realiza de forma explícita:

Se selecciona el número de identificación para que sea único para todos los registros y parta al archivo en n registros individuales. Desafortunadamente, puede resultar necesaria una computación separada para determinar el número de identificación perteneciente al dato deseado.



Con estas restricciones estructurales y mayor eficiencia en la atención en el procesamiento orientado en forma tabular, se pierde mucha flexibilidad.



No es fácil colocar las actualizaciones en un archivo secuencial. el hecho de que determine el atributo llave exclusivamente la secuencia de los registros introduce una simetría que hace que los archivos secuenciales resulten inadecuados para recuperar información general.



El procedimiento común para manejarisercion en un archivo secuencial consiste en recolectarlas en un apilo, el archivo de bitácora de transacciones, hasta que el apilo resulte demasiado grande para realizar entonces una actualización por lote. esto se hace reorganizando el archivo.



En este momento el archivo de bitácora de transacciones se clasifica desacuerdo con las mismas llaves utilizadas para el archivo principal y las modificaciones se unen en una nueva copia del archivo secuencial.



ARCHIVOS SECUENCIALES



Existen además muchas operaciones asociadas a archivos, las más elementales son:



1.- Creación de Archivo.- En este proceso se pretende solamente crear un archivo nuevo en disco, con su nombre, tipo y especialidad de almacenamiento de datos apropiado.



2.- Apertura de Archivos.- En este caso se pretende abrir un archivo ya existente en disco para procesarlo, ya sea cargar o grabar datos en sus registros, o leer algún registro en especial para mandarlo a una variable de cualquier tipo.



No confundir creación con apertura, creación es un proceso que solo se ejecuta una sola vez en la vida de un archivo, mientras que apertura, siempre se está realizando por los programas especializados en algún proceso.



3.-Cierre de archivos: Es la operación más importante en cualquier programa que maneje archivos, o se cierra el archivo como última instrucción del programa o se verá el anuncio ABORT, RETRY, FAIL.



98, /s, scandisk



4.-Altas en archivo.- En este proceso se carga una clase en memoria con sus datos pertinentes y se graba la clase en el archivo en disco.



5.-Lectura de archivo.- En este proceso, se abre el archivo y se manda el registro de disco, a una clase en memoria para su procesamiento.



6.- Consulta de archivos: En este proceso se pretende desplegar todos los registros del archivo en disco a la pantalla, ya sea consola o mejor aún, a una pagina HTML



7.-Busqueda en archivos: Una de las operaciones más comunes, consiste en que el usuario pide toda la información de algún renglón en disco, proporcionando la información de algún campo, generalmente el campo clave de la clase.



8.- Filtros.- En este proceso el usuario está interesado en algún conjunto de renglones con características comunes (condición), por ejemplo todos los alumnos de “sisJAVA TEMA s”, o todos los empleados que ganen más de $500.00 pesos, o todos los clientes que sean de “Tijuana”, etc.



9.-Modificaciones de registros o archivos: Problema muy común, donde los datos originales ya grabados se tienen que cambiar o actualizar, por ejemplo el nombre no era “Juan” es “Juana”, o la calificación no es 100 es 20, etc.



10.- Bajas de registros: también muy común este proceso, por ejemplo el alumno ya egreso, el cliente huyo, etc.



EQUIPO
MORENO MORALES GERARDO DE JESUS
DE LA LUZ SANTIAGO CASTRO

1) Investigar los diferentes tipos de organizaciones de archivos (Organización secuencial, secuencial indexado y Directas), así como, las ventajas y desventajas de cada una de las organizaciones básicas de archivo. Hacer uso de TICs de software (Wikis, Foros, Edu-Blogs, WebQuest, EVE-A). Elaborar una tabla comparativa acerca de lo investigado, o en su defecto, debe diseñar un mapa conceptual o diagrama, que debe compartir en este Foro.

Organizaciones de archivos

"Organización Secuencial"

Archivo secuencial es la forma más simple de almacenar y recuperar registros de un archivo. En un archivo secuencial, se almacenan los registros uno tras otro. El primer registro almacenado se coloca al principio del archivo. El segundo se almacena inmediatamente después (no existen posiciones sin uso), el tercero después del segundo, etc. Este orden nunca cambia en la organización secuencial.

Ventajas:

-proveen la mejor utilización de espacio y son rápidos cuando los registros son accesados secuencialmente.
-Los archivos con poca volatilidad, gran actividad y tamaño variable son altamente susceptibles de ser organizados secuencialmente.
-La ventaja más importante de la técnica de organización secuencial de archivos es la capacidad de acceso al "siguiente" registro rápidamente: Mientras que el patrón de acceso a un archivo secuencial se conforme al ordenamiento de registros en el archivo, los tiempos de acceso serán muy buenos. Sin embargo, si el patrón de acceso al programa no se conforma al patrón de ordenamiento de los registros, entonces la eficiencia del programa puede ser terrible.
-son muy sencillos de usar y aplicar.

Desventajas:

-El acceso a un registro es pobre
- la localización de un determinado registro no se puede hacer individualmente no de manera rápida, y el acceso aleatorio es impráctico.
- en los archivos secuenciales la dirección de registro está implícita y están vulnerables a fallas del sistema.


"Organización Secuencial-Indexado"

Existen al menos dos metodologías: La primera, consiste en establecer un elemento índice para ir ordenando los datos utilizando el mismo archivo. La segunda metodología, y probablemente la más común, por su eficiencia, consiste en dejar el archivo de manera secuencial, y crear otro archivo de índices. En este archivo de índices se elige el elemento por el cual se ordenaran los datos, y solamente se manipula el archivo de índices, ya que el archivo de datos quedara igual. Y cuando se desea visualizar la información, se consulta el archivo de índices, y se busca por 'claves', la información dentro del archivo organizado de manera secuencial".

Ventajas

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

Desventajas

- Ocupa más espacio en el disco que los ficheros secuénciales, debido al uso del área de índices.
- 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.
- Solo se puede utilizar soportes direccionables.
- Obliga a una inversión económica mayor, por la necesidad de programas y, a veces, hardware más sofisticado.
- Menos eficiente que la secuencial, menos rápida que la directa.

"Organización Directa"

Consiste en guardar la información de "manera directa", es decir, no lleva un orden específico, pero se pueden localizar los datos haciendo uso de sus "direcciones" (saltando registro o líneas), sin necesidad de leer completamente todos los datos

Ventajas

-Acceso rápido a registros específicos.
-Permite la consulta directa, sin lectura de los registros anteriores
-Permite realizar operaciones de escritura y lectura simultáneamente
-Son muy rápidos al tratar registros individuales.

Desventajas

-Dejan gran cantidad de posiciones libres de memoria del fichero.
-Se producen colisiones, ya que puede existir más de un registro con la misma calve

2) Investigar acerca las características de los métodos de búsqueda y ordenamiento (al menos dos de cada uno). Desarrollar un resumen o tabla comparativa o mapa conceptual o diagrama para representar lo investigado en forma textual o gráficamente, el cual debe compartir en este foro.

RESUMEN:
---METODOS DE BUSQUEDA---
Los métodos de búsqueda pueden clasificarse según la ubicación de los datos sobre los que se realizara la búsqueda. Existen dos clases:
• Métodos de Búsqueda Interna
• Métodos de Búsqueda Externa.

"METODOS DE BUSQUEDA INTERNA"
Se denomina búsqueda interna cuando todos los elementos se encuentran en la memoria principal. Por ejemplo, almacenados en estructuras estáticas (arreglos) o en estructuras dinámicas (listas ligadas y arboles).
Los métodos de búsqueda mas importantes son:
• Secuencial o lineal
• Binaria
• Por transformación de claves

-BUSQUEDA SECUENCIAL
• Búsqueda secuencial consiste en revisar elemento por elemento hasta encontrar el dato buscado, o hasta llegar al final de la lista de datos disponible.
-CARACTERISTICAS
• La búsqueda se puede realizar en arreglos desordenados.
• El método es totalmente confiable.
• El numero de comparaciones es significativa si el arreglo es muy grande.
• En arreglos desordenados de N componentes puede suceder que el elemento no se encuentre, por lo tanto se harán N comparaciones al recorrer todo el arreglo
• Cantidad mínima de comparaciones es 1.
• Cantidad media de comparaciones es (1+N)/2.
• Cantidad máxima de comparaciones es N.

-BUSQUEDA BINARIA
• La búsqueda binaria utiliza un método de `divide y vencerás' para localizar el valor deseado. Con este método se examina primero el elemento central de la lista; si éste es el elemento buscado, entonces la búsqueda ha terminado.
• En caso contrario, se determinar si el elemento buscado será en la primera o la segunda mitad de la lista y a continuación se repite este proceso, utilizando el elemento central de esa sub-lista.
-CARACTERISTICAS
• Sirve únicamente para arreglos ordenados.
• Es mas eficiente que el método de búsqueda secuencial, debido a que el numero de comparaciones se reduce a la mitad por cada iteración del método.
• Cantidad mínima de comparaciones es 1.
• Cantidad media de comparaciones es (1+log₂(N))/2.
• Cantidad máxima de comparaciones es log₂(N).

-BUSQUEDA POR TRANSFORMACION DE CLAVES (HASH)
• Aumenta la velocidad de búsqueda sin necesidad de tener los objetos ordenados.
• El tiempo de búsqueda es totalmente independiente del numero de componentes del arreglo.
• La búsqueda se realiza por medio de direcciones, creadas por una función hash(H).
-FUNCIONES HASH
• Las Funciones HASH (H) mas aplicadas son:
• Función Modulo (Por división).
• Función Cuadrado.
• Función Plegamiento.
• Función Truncamiento.

"METODOS DE BUSQUEDA EXTERNA"
• Se denomina búsqueda externa cuando todos los elementos se encuentran en memoria secundaria (archivos almacenados en dispositivos tales como cintas y discos magnéticos).


---METODOS DE ORDENAMIENTO---
Debido a que las estructuras de datos son utilizadas para almacenar información, para poder recuperar esa información de manera eficiente es deseable que aquella esté ordenada. Existen varios métodos para ordenar las diferentes estructuras de datos básicas.
En general los métodos de ordenamiento no son utilizados con frecuencia, en algunos casos sólo una vez. Hay métodos muy simples de implementar que son útiles en los casos en dónde el número de elementos a ordenar no es muy grande (ej, menos de 500 elementos). Por otro lado hay métodos sofisticados, más difíciles de implementar pero que son más eficientes en cuestión de tiempo de ejecución.

-ORDENAMIENTO DE BURBUJA
La Ordenación de burbuja (Bubble Sort en inglés) es un sencillo algoritmo de ordenamiento. Funciona revisando cada elemento de la lista que va a ser ordenada con el siguiente, intercambiándolos de posición si están en el orden equivocado. Es necesario revisar varias veces toda la lista hasta que no se necesiten más intercambios, lo cual significa que la lista está ordenada. Este algoritmo obtiene su nombre de la forma con la que suben por la lista los elementos durante los intercambios, como si fueran pequeñas "burbujas". También es conocido como el método del intercambio directo. Dado que solo usa comparaciones para operar elementos, se lo considera un algoritmo de comparación, siendo el más sencillo de implementar.

-ORDENAMIENTO SHELL
El algoritmo Shell sort mejora el ordenamiento por inserción comparando elementos separados por un espacio de varias posiciones. Esto permite que un elemento haga "pasos más grandes" hacia su posición esperada. Los pasos múltiples sobre los datos se hacen con tamaños de espacio cada vez más pequeños. El último paso del Shell sort es un simple ordenamiento por inserción, pero para entonces, ya está garantizado que los datos del vector están casi ordenados.

-ORDENAMIENTO POR INSERCION
El ordenamiento por inserción (insertion sort en inglés) es una manera muy natural de ordenar para un ser humano, y puede usarse fácilmente para ordenar un mazo de cartas numeradas en forma arbitraria. Requiere O(n²) operaciones para ordenar una lista de n elementos.

-ORDENAMIENTO POR SELECCION
El ordenamiento por selección (Selection Sort en inglés) es un algoritmo de ordenamiento que requiere O(n^2) operaciones para ordenar una lista de n elementos.
Su funcionamiento es el siguiente:
Buscar el mínimo elemento de la lista
Intercambiarlo con el primero
Buscar el mínimo en el resto de la lista
Intercambiarlo con el segundo
Y en general:
Buscar el mínimo elemento entre una posición i y el final de la lista
Intercambiar el mínimo con el elemento de la posición i.

http://estdatosgrupo8a.blogspot.mx/2009/05/metodos-de-busqueda.html
http://iutprogramacion.blogspot.mx/2013/02/metodos-de-ordenamiento.html

ATENTAMENTE :
GRUPO: 4A6   "LOS PAISAS"
* CITLALI ARROYO ROMERO  
*CARLOS ALBERTO RUIZ GUTIERREZ
*NEFTALI CABRERA TORRES  
*CRISTIAN ALONSO IGNACIO  

Organización de Archivos

Se refiere a las diferentes maneras en las que puede ser organizada la información de los archivos, así como las diferentes maneras en que ésta puede ser accesada. Dado que hay 2 niveles de visión de los archivos (físico y lógico), se puede hablar también de 2 aspectos de organización de archivos: Organización de archivos lógicos y de archivos físicos.


El sistema de archivos está relacionado especialmente con la administración del espacio de almacenamiento secundario, fundamentalmente con el almacenamiento de disco.

Una forma de organización de un sistema de archivos puede ser la siguiente:

Se utiliza una “raíz ” para indicar en qué parte del disco comienza el “directorio raíz ” .
El “directorio raíz ” apunta a los “directorios de usuarios”.
Un “directorio de usuario” contiene una entrada para cada uno de los archivos del usuario.
Cada entrada de archivo apunta al lugar del disco donde está almacenado el archivo referenciado.
Esta forma de organización

Los nombres de archivos solo necesitan ser únicos dentro de un directorio de usuario dado.

El nombre del sistema para un archivo dado debe ser único para el sistema de archivos.

En sistemas de archivo “jerárquicos” el nombre del sistema para un archivo suele estar formado como el “nombre de la trayectoria” del directorio raíz al archivo.

Organización lógica.

La mayoría de las computadoras organizan los archivos en jerarquías llamadas carpetas, directorios o catálogos . (El concepto es el mismo independientemente de la terminología usada.) Cada carpeta puede contener un número arbitrario de archivos, y también puede contener otras carpetas. Las otras carpetas pueden contener todavía más archivos y carpetas, y así sucesivamente, construyéndose un estructura en árbol en la que una «carpeta raíz» (el nombre varía de una computadora a otra) puede contener cualquier número de niveles de otras carpetas y archivos. A las carpetas se les puede dar nombre exactamente igual que a los archivos (excepto para la carpeta raíz, que a menudo no tiene nombre). El uso de carpetas hace más fácil organizar los archivos de una manera lógica.

La mayor parte de las estructuras de organizaciones alternativas de archivos se encuentran dentro de estas cinco categorías:

Pilas

Los registros pueden tener campos diferentes o similares en un orden distinto. Cada campo debe ser autodescriptivo, incluyendo tanto un campo de nombre como el valor. La longitud de cada campo debe indicarse implícitamente con delimitadores, explícitamente incluidos como un subcampo más.

El acceso a los registros se hace por búsquedas exhaustiva y son fáciles de actualizar. Si se quiere encontrar un registro que contiene un campo particular y un valor determinado, es necesario examinar cada registro de la pila hasta encontrar el registro deseado. Si se quieren encontrar todos los registros que contienen un campo particular o que tienen un valor determinado para ese campo, debe buscarse el archivo entero.

Se aplica cuando los datos se recogen o almacenan antes de procesarlos o cuando no son fáciles de organizar. Esta clase de archivo aprovecha bien el espacio cuando los datos almacenados varían en tamaño y estructura. Fuera de estos usos limitados, este tipo de archivos no se adapta a la mayoría de las aplicaciones.

Archivos secuenciales

Es la forma más común de estructura de archivos.

Se emplea un formato fijo para los registros, son de la misma longitud y constan del mismo número de campos de tamaño fijo con un orden determinado.

Se necesita almacenar los valores de cada campo; el nombre del campo y la longitud de cada uno son atributos de la estructura del archivo. Cada registro tiene un campo clave que lo identifica (generalmente es el primero de cada registro). Los registros se almacenan en secuencia por la clave.

Se utilizan normalmente en aplicaciones de procesos por lotes, ya que es la única organización de archivos que se puede guardar tanto en cintas como en discos.

Para las aplicaciones interactivas que incluyen peticiones o actualizaciones de registros individuales, los archivos secuenciales no son óptimos. El acceso requiere una búsqueda secuencial de correspondencias con la clave. Si el archivo entero o gran parte de él pueden traerse a la memoria principal de una sola vez, se podrán aplicar técnicas de búsquedas más eficientes. Al acceder un registro de un archivo secuencial grande, se produce un procesamiento extra y un retardo considerable.

La organización física del archivo en una cinta o disco se corresponde exactamente con la organización lógica del archivo, por lo tanto el procedimiento habitual es ubicar los nuevos registros en un archivo de pila separado, es llamado archivo de registro o archivo de transacciones .

Una alternativa es organizar físicamente el archivo secuencial como una lista enlazada, en cada bloque físico se almacena uno o más registros y cada bloque del disco contiene un puntero al bloque siguiente. La inserción de un nuevo registro implica la manipulación de puntero, pero no requiere que el nuevo registro ocupe una posición particular del bloque físico.

Archivos secuenciales indexados

Los registros se organizan en una secuencia basada en un campo clave presentando dos características, un índice del archivo para soportar los accesos aleatorios y un archivo de desbordamiento. El índice proporciona una capacidad de búsqueda para llagar rápidamente al registro deseado y el archivo de desbordamiento es similar al archivo de registros usado en un archivo secuencial, pero está integrado de forma que los archivos de desbordamiento se ubiquen siguiendo un puntero desde su registro predecesor.

La estructura más simple tiene como índice un archivo secuencial simple, cada registro del archivo índice tiene dos campos, un campo clave igual al del archivo principal y un puntero al archivo principal. Para encontrar un campo especifico se busca en el índice hasta encontrar el valor mayor de la clave que es iguale o precede al valor deseado de la clave, la búsqueda continua en el archivo principal a partir de la posición que indique el puntero.

Cada registro del archivo principal tiene un campo adicional que es un puntero al archivo de desbordamiento. Cuando se inserta un nuevo registro al archivo, también se añade al archivo de desbordamiento. El registro del archivo principal que precede inmediatamente al nuevo registro según la secuencia lógica se actualiza con un puntero del registro nuevo en el archivo de desbordamiento, si el registro inmediatamente anterior está también en el archivo de desbordamiento se actualizará el puntero en el registro.

Para procesar secuencialmente un archivo completo los registros del archivo principal se procesarán en secuencia hasta encontrar un puntero al archivo de desbordamiento, el acceso continua en el archivo de desbordamiento hasta que encuentra un puntero nulo, entonces renueva el acceso donde se abandonó en el archivo principal.

Archivos indexados

A los registros se accede solo a través de sus índices. No hay resticción en la ubicación de los registros, al menos un índice contiene un puntero a cada registro y pueden emplearse registros de longitud variable.

Se suelen utilizar dos tipos de índices, uno exhaustivo que contiene una entrada para cada registro del archivo principal y se organiza como un archivo secuencial para facilitar la búsqueda, el otro índice es parcial que contiene entrada a los registros donde esté el campo de interés.

Con registro de longitud variable, algunos registros no contendrán todos los campos y cuando se añade un registro al archivo principal, todos los archivos de índices deben actualizarse.

Archivos directos o de dispersión

Explotan la capacidad de los discos para acceder directamente a cualquier bloque de dirección conocida.

Se requiere un campo clave en cada registro.

Los archivos directos son muy usados donde se necesita un acceso muy rápido, donde se usan registros de longitud fija y donde siempre se accede a los registros de una vez.

Organización física.

Los datos son arreglados por su adyacencia física, es decir, de acuerdo con el dispositivo de almacenamiento secundario. Los registros son de tamaño fijo o de tamaño variable y pueden organizarse de varias formas para constituir archivos físicos.

Cinta magnética.

En este dispositivo el archivo físico esta formado por un conjunto de registros físicos, y los bloques están organizados en forma consecutiva, ya que se asigna en igual forma.

Además tales registros puede contener etiquetas que permitan un mayor control sobre los datos almacenados, y son las siguientes:

- Etiqueta de volumen.- Contiene información que permite identificar la cinta, el nombre del propietario y cualquier información general requerida.

- Etiqueta de archivo.- Se utilizan por pares para indicar el inicio y fin del archivo, contiene información acerca del nombre del archivo, fecha de creación.

- Etiqueta de usuario.- Sirven para guardar información adicional de importancia para el usuario; no son procesados por el sistema operativo.

Discos Magnéticos.

El archivo físico en un disco es una colección de registros físicos de igual tamaño, los cuales pueden estar organizados en forma consecutiva, ligada o con una tabla de mapeo.

En la organización contigua, el archivo utiliza registros físicos contiguos, siguiendo la secuencia normal de direcciones.

La organización encadenada consiste un conjunto de bloques, cada uno de los cuales tiene un campo destinado para indicar la dirección del siguiente registro, o sea, para lo que se ha llamado enlace o liga.

Otra forma de organización es la tabla de mapeo que consiste en una tabla de apuntadores a los registros físicos que forman el archivo.

La organización física de un archivo en el almacenamiento secundario depende de la estrategia de agrupación y de la estrategia de asignación de archivos.

Para elegir una organización de archivos se deben tener en cuenta ciertos criterios:

Si un archivo va a procesar solamente por lotes, accediendo cada vez a todos los registros, entonces el acceso rápido para la recuperación de un único registro es una preocupación mínima. Un archivo almacenado en CD-ROM nunca será actualizado, por lo que la facilidad de actualización no se considera. Para la economía de almacenamiento , debería existir una mínima redundancia de los datos, ésta redundancia es el medio fundamental para incrementar la velocidad de acceso a los datos.

Este tipo de organización muestra a su vez, 2 aspectos importantes: Métodos De Asignación De Espacio Libre y Asignación De Espacio De Almacenamiento Del Archivo.

METODOS DE ASIGNACION DE ESPACIO LIBRE

Un método de asignación de espacio libre determina la manera en que un Sistema Operativo controla los lugares del disco que no están siendo ocupados.
Para el control del espacio libre se puede utilizar como base alguno de los métodos teóricos: Vector de Bits, Lista Ligada, Por Agrupacion y por Contador.

VECTOR DE BITS

Se tiene un arreglo de bits, el número de bits que tiene, representa cada sector del disco, o sea que si los sectores 10 y 11 están ocupados su representacion será:

LISTA LIGADA

Existe una cabeceraen la que se tiene la direccion del primer sector vacio, ese sector a su vez, tiene un apuntador al siguiente bloque, y así sucesivamente hasta que se encuentre una marca indicando que ya no hay espacio libre, tal y como se muestra en la siguiente figura.

POR AGRUPACION
Es similar a la lista ligada, solo que en este se tiene por cada sector, un grupo de apuntadores a varios espacios vacíos, al final de cada bloque se tiene un apuntador a otro grupo de apuntadores, observe la figura.

MÉTODOS DE ASIGNACIÓN DE ESPACIO EN DISCO.

Un método de asignación de espacio en disco determina la manera en que un Sistema Operativo controla los lugares del disco ocupados por cada archivo de datos. Se debe controlar básicamente la identificación del archivo, sector de inicio y sector final.

Para el control del espacio ocupado en disco se puede utilizar como base alguno de los métodos teóricos: Asignación Contigua, Asignación Ligada, Asignación Indexada.
ASIGNACIÓN CONTIGUA.

Este método consiste en asignar el espacio en disco de tal manera que las direcciones de todos losbloques correspondientes a un archivo definen un orden lineal.

DESVENTAJAS

- La cabeza de lectura no se mueve demasiado en la lectura de un archivo.

- Produce fragmentación externa.

ASIGNACIÓN LIGADA

En este método, cada archivo es una lista ligada de bloques de disco. En el directorio hay un apuntador al bloque de inicio y un apuntador al bloque final para cada archivo. En cada uno de los bloques donde se encuentra un archivo hay un apuntador al siguiente bloque de la lista. Por ejemplo:


DESVENTAJAS

- No produce fragmentación externa.
La cabeza de lectura se puede mover demasiado en la lectura de un archivo.
- Si una liga se pierde, se perderá el archivo completo.
Es ineficiente para la implementación de archivos directos.
Se necesita un campo extra para el apuntador.
ASIGNACIÓN INDEXADA

Como ya se vio, la asignación ligada resuelve problemas de fragmentación externa, sin embargo, laasignación ligada no soporta eficientemente el acceso directo a los archivos. La asignación indexada resuelve este problema poniendo todos los apuntadores en una sola localidad: El bloque índice .

Cada archivo tiene su bloque índice, El cual es un arreglo de direcciones de bloques de disco.

DESVENTAJAS

No produce fragmentación externa.
Eficiente para la implementación de archivos directos.

Existe desperdicio cuando hay archivos muy chicos.
Desbordamiento de bloque índice. (Solución: creación de un esquema ligado; el ultimo bloque índice apunta a otro índice) .


integrantes:
karina rayo alcantar 
juan jose ruiz mojica
uriel nazario garcía
juan giles león

grupo: 4b6

ORGANIZACIONES DE ARCHIVOS

TIPO: SECUENCIAL
CONCEPTO: Es la forma básica de organizar un conjunto de registros, forman un archivo, utilizando una organización secuencial
VENTAJAS: *Tiene un acceso más eficiente a todos los datos. *Tiene menos uso de espacio de almacenaje.
DESVENTAJAS: *Tiene un acceso muy lento a registros

TIPO: SECUENCIAL INDEXADO
CONCEPTO: Se utiliza cuando existe la necesidad tanto de acezar los registros secuencialmente, por algún valor de llave, como de acezarlos individualmente
VENTAJAS: *Más rápida que la organización secuencial. *Más eficiente que la organización directa.
DESVENTAJAS: *Menos rápida que la directa. *Menor eficiente que la secuencial.


TIPO: DIRECTA
CONCEPTO: Consiste en guardar la información de manera directa, es decir, no
lleva un orden especifico, pero se pueden localizar los datos haciendo uso de sus "direcciones", sin necesidad de leer completamente todos los datos
VENTAJAS: *Tiene un gran acceso rápido a registros
DESVENTAJAS: *Tiene una ineficiencia de acceso a la totalidad.
*Mayor uso de espacio de almacenamiento.

BÚSQUEDA SECUENCIAS

concepto:
ESTE MÉTODO SE USA PARA BUSCAR UN ELEMENTO DE UN VECTOR, ES EXPLORAR SECUENCIALMENTE EL VECTOR, ES DECIR; RECORRER EL VECTOR DESDE EL PRIOR ELEMENTO HASTA EL ÚLTIMO.
caracteristicas:
*LA BÚSQUEDA SE PUEDE REALIZAR EN ARREGLOS DESORDENADOS.
*EL MÉTODO ES TOTALMENTE CONFIABLE.
*EL NUMERO DE COMPARACIONES ES SIGNIFICATIVA SI EL ARREGLO ES MUY GRANDE.

BÚSQUEDA BINARIA

concepto:
ES UN MÉTODO QUE SE BASA EN LA DIVISIÓN SUCESIVA DEL ESPACIO OCUPADO POR EL VECTOR EN SUCESIVAS MITADES, HASTA ENCONTRAR EL ELEMENTO BUSCADO.

carateristicas:
*SIRVE ÚNICAMENTE PARA ARREGLOS ORDENADOS.
*ES MAS EFICIENTE QUE EL MÉTODO DE BÚSQUEDA SECUENCIAL, DEBIDO AL NUMERO DE COMPARACIONES SE REDUCE ALA MITAD POR CADA ITERACIÓN MÍNIMA DEL MÉTODO.

METODO DE ORDENAMINETO

BURBUJA

concepto:
FUNCIONA REVISANDO CADA ELEMENTO DE LA LISTA QUE VA A SER ORDENADA.

caracteristicas:
*ES BASTANTE SENCILLO.
*ES MUCHO MAS EFICAZ.

QUICKSORT

concepto:
ESTE MÉTODO ES UNA MEJORA SUSTANCIAL DEL MÉTODO DE INTERCAMBIO DIRECTO Y RECIBE SU NOMBRE POR LA VELOCIDAD CON LA QUE ORDENA.

caracteristicas:
*EL MÉTODO DE ORDENAMIENTO QUICK SORT ES ACTUALMENTE EL MÁS EFICIENTE Y VELOZ DE LOS MÉTODOS DE ORDENACIÓN INTERNA.

INSERCCION

concepto:
ES UN ALGORITMO RELATIVAMENTE SENCILLO Y SE COMPORTA RAZONABLEMENTE BIEN EN GRAN CANTIDAD DE SITUACIONES.

caracteristicas:
*PARA ORDENAR LOS ELEMENTOS TOMAMOS COMO NUMERO PIVOTE EL PRIMER NÚMERO DEL LADO IZQUIERDO