Árboles

A continuación presentamos un resumen con la información principal sobre el tema de árboles, así como algunos ejemplos de código sobre sus operaciones:

Arboles resumen

View more documents from Cogu09

DISPERSIÓN HASH

Dipersion

View more presentations from UDG.

Cortesía de equipo 7

Proceso secuencial coordinado

Procesamiento coordinado

View more presentations from Carlos_solraC

Enlaces

En el sistema de archivos que se está siseñando, el enlace de la llave primaria con una dirección se lleva a cabo en el momento en que se constituyen los archivo. Las llaves secundaria que llegana a una dirección en el momento en que se usan.

El enlace se valida en el momento de la construcción del archivo permitiendo un acceso más rápido. Una vez que se haya encontrado el registro de índice correcto, se tiene la distancia en bytes de registro de datos que se esta buscando.

Por lo que gráficamente se podría representar de la siguiente forma:

Enlace ---> Dirección de Archivo (NRR) ----> Índice

Indización y Operaciones

La siguiente presentación la realizó el Equipo 6 y es quien nos la proporcionó.

indizacion

View more presentations from Cogu09.

Ordenamiento Shell

Método de ordenamiento shell

View more presentations from UDG.

Búsqueda Binaria

     Es un algoritmo que reduce el tiempo de búsqueda, ya que reduce exponencialmente el numero de iteraciones necesarias.
     Se utiliza cuando el arreglo en el que queremos determinar la existencia de una elemento esta previamente ordenado.
     Consiste en dividir el intervalo de búsqueda en dos partes, comparando el elemento buscado con el que ocupa la posición central en el arreglo. En caso de que no sean iguales, se predefinen los extremos del intervalo, según el elemento central sea mayor o menor que el elemento buscado, disminuyendo el espacio de búsqueda, el proceso termina cuando encuentra el elemento buscado o el intervalo de búsqueda se anula, es vació.
     Con cada iteración del método el espacio de búsqueda se reduce a la mitad.

Click aquí para ver el vídeo de búsqueda binaria

Búsqueda Secuencial

    La búsqueda es el proceso de localizar un registro (elemento) con un valor de llave particular. La búsqueda termina exitosamente cuando se localiza el registro que contenga la llave buscada, o termina sin éxito, cuando se determina que no aparece ningún registro con esa llave.

 

    Búsqueda secuencial, también se le conoce como búsqueda lineal. Supongamos una colección de registros organizados como una lista lineal. El algoritmo básico de búsqueda secuencial consiste en empezar al inicio de la lista e ir a través de cada registro hasta encontrar la llave indicada(k), o hasta al final de la lista.

 

 

La situación óptima es que el registro buscado sea el primero en ser examinado. El peor caso es cuando las llaves de todos los n registros son comparados con k (lo que se busca). El caso promedio es n/2 comparaciones.

    Este método de búsqueda es muy lento, pero si los datos no están en orden es el único método que puede emplearse para hacer las búsquedas. Si los valores de la llave no son únicos, para encontrar todos los registros con una llave particular, se requiere buscar en toda la lista.

Acceso a los Archivos

     Dependiendo de la manera en que se acceden a los registren de un archivo, se le clasifican como SECUENCIALES o como DIRECTOS.  

En los archivos de acceso secuencial, para tener acceso al registro localizado en la posición N, se deben haber procesado los N-1 registros previos, en un orden secuencial.

Cuando se tienen pocos registros en un archivo, o que los registros son pequeños, la diferencia entre los tipos de acceso de forma secuencial y directa pueden no ser perceptible para el usuario; sin embargo, la diferencia viene a ser significativa cuando se manejan archivos con grandes cantidades de información.

La forma de manejar los archivos de acceso secuencial es mas sencilla en la mayoría de los lenguajes de programación, por lo que su estudio se antepone al de los archivos de acceso directo.

El manejo secuencial de un archivo es recomendable cuando se deben procesar todos o la mayoría de los registros, como por ejemplo en los casos de una nomina de empleados o en la elaboración de reportes contables. 

Lectura de un archivo

Normalmente la lectura de un archivo no tiene sentido por si sola, si no que adquiere significado cuando se asocia con la actualización del archivo o con la generación de un reporte cualquiera.

   De alguna manera podemos pensar en la lectura de un archivo como un proceso inverso al de su creación, puesto que ahora se pasara la información desde el disco hacia la memoria auxiliar.

Veamos un procedimiento que lea todos los registros del archivo “empleados.dat”, y los despliegues en la pantalla.

Mantenimiento de Archivos y Eliminación (Conceptos)

1) Mantenimiento de Archivos
      Son aquellas modificaciones que se le pueden realizar a un archivo. Pueden ser de tres formas:

• Agregar
• Actualizar
• Eliminar

     El mantenimiento se vuelve complejo cuando se actualiza registros de longitud variable o se eliminan registros de longitud fija o variable. Cuando se elimina un registro se desea reutilizar el espacio. Hay dos tipos de archivos, en línea y fuera de línea; los primeros son los que están en constante actualización, los segundos se someten a pocos cambios.

2) Compactación del Almacenamiento

     Se refiere a la reutilización de los espacios que han sido desocupados al momento de eliminar un registro.

     La forma más sencilla es marcar de alguna forma el registro a eliminar y generar un duplicado de archivo omitiendo los registros marcados, una vez que se decida eliminarlos por completo.

3) Panorama de Eliminación de Registros de Longitud Fija

     Para proporcionar un mecanismo de eliminación de registros con la subsecuente reutilización del espacio, es necesario garantizar dos cosas:

1.  Que los registros eliminados se marquen de alguna forma especial.
2.  Que se pueda encontrar el espacio que los registros eliminados ocupan para reutilizarlo cuando se agreguen otros registros.

    Al momento de insertar registros para una forma más rápida se necesita:

• Una forma de saber de inmediato si hay lugares vacíos en el archivo.
• Una forma de saltar directamente a uno de esos lugares en caso de existir.

4) Eliminación de Registros de Longitud Fija

     Es una función que primero mueve el apuntador a la posición NRR (Número Relativo de Registro). Luego marca con la bandera de eliminación (*) y en la lista de disponibles graba el NRR para indicar que está disponible y así poderlo reutilizar, sino hubiera disponible se escribe el registro al final de la lista.

     También se necesita una función que revisa si el registro no está eliminado.

5) Eliminación de Registros de Longitud Variable

     Es una operación que emplea la reutilización del espacio de los registros eliminados para colocar un registro de igual o menor tamaño.

     Para llevar a cabo la reutilización realiza una búsqueda sobre los NRR para identificar los tamaños y si el registro a agregar es mayor al espacio dejado por la eliminación se agrega al final de la lista.

6) Fragmentación del Almacenamiento

     Es el espacio desperdiciado dentro de un registro. Hay dos tipos de registros: Longitud fija y variable. Los de longitud fija al establecerse automáticamente, crea la fragmentación, y los de longitud variable crea la fragmentación sólo si se borra un registro.

     La fragmentación se combate con la unión de los huecos fragmentados para crear un espacio mayor y reutilizable.

Tipos de fragmentación:
          - Externa: Es cuando el espacio que no se utiliza está fuera de los registros individuales.
          - Interna: Es cuando el espacio desperdiciado se encuentra dentro de un registro.

Unión de Espacios:
          Si dos o más registros son eliminados, los adyacentes "físicos" pueden unirse para cubrir el espacio que quedó entre ellos.
 

7) Estrategias de Colocación

     Es una forma de ir almacenando la información en el disco duro, esto en los archivos de longitud variable.

Definición de Colocación: Mecanismo para elegir el espacio adecuado para los nuevos registros.

Primer ajuste:

     Se utiliza la mínima cantidad posible de trabajo y  no se preocupa por la exactitud del ajuste. Se acepta la primera entrada disponible. Ven en secuencia o por tamaño.

Mejor ajuste:

     El ajuste entre la entrada disponible y las necesidades del registro nuevo. Orden ascendente.

Peor ajuste:

     Inicia su búsqueda al principio de la lista de disponibles, siempre devuelve la entrada disponible más grande. Orden descendente.

Comandos en C para manejo de archivos

FILE: 
      Declara la variable donde se almacena la ruta del archivo a utilizar, generalmente se coloca como global.Su sintaxis es la siguiente:
          FILE *nombre_variable;


fopen();
     Permite abrir un archivo, devolviendo un valor NULL sino se abrió correctamente y TRUE si ocurre lo contrario. Su sintaxis es la siguiente:
          nombre_FILE = fopen(<"nombre de archivo">,<"modo">);
     Modo:

• r  = Sólo lectura.
• w  = Abre o sobrescribe.
• a  = Añade al fichero.
• r+ = Lectura y escritura.
• w+ = Lectura, escritura y sobrescribe.
• a+ = Añadir, lectura y escritura.

     NOTA: Después del modo se incluye el tipo (b = binario, t = texto).

fclose();

     Permite cerrar un archivo, al final de un programa es necesario cerrar un archivo para no perder información. Su sintaxis es la siguiente:

          fclose(<nombre_FILE>);

fputs();

     Escribe una cadena en un fichero. Su sintaxis es la siguiente:

          fputs(<variable_char>, *nombre, <variable_FILE>);

fwrite();

     Escribe en un fichero uno o varios registros de la misma longitud, almacenados a partir de una dirección; trabajo en conjunto con fread(). Su sintaxis es la siguiente:

     fwrite(<&registro>,sizeof(<estructura>),1,<variable_FILE>);

fprintf();

     Permite escribir o imprimir en un archivo. Su sintaxis es la siguiente:

          fprintf(<variable_FILE>,<"información">);

fread();

     Permite leer registros de un archivo y permite almacenar la información en una variable.Su sintaxis es igual a la de fwrite.

          fread(<&registro>,sizeof(<estructura>),1,<variable_FILE>);

feof();

     Comprueba el final de un archivo y retorna un valor boleano. Usualmente se combina con algún ciclo (for, if, while). Su sintaxis es la siguiente.

           feof(<variable_FILE>);

fscanf();

     Permite leer en un archivo utilizando una máscara para el tipo de dato que se lee. Su sintaxis es la siguiente:

       fscanf(<variable_FILE>,<máscara>,<variable_registro.campo>);

fseek();

     Permite posicionar el cursor dentro del archivo para después realizar una búsqueda. Su sintaxis es la siguiente:

          fseek(<variable_FILE>, <longitud>, <origen>);

     Origen: Es la posición a mandar el cursor: 

• SEEK_SET: Principio.
• SEEK_CUR: Posición actual.
• SEEK_END: Final.

     Longitud: Permite indicar como ir posicionando el cursor, es decir, de uno en uno o algún otro valor.

Tipos de Registros y Operaciones

Tipo de Transacción
  Inserción, eliminación y modificación

Campos adicionales
   Todo, ninguno y campo a modificar.

Creacion de Archivos:   Es la asignacion de un espacio en el medio de almacenamiento mediante la colocación del nombre del archivo en el directorio.

Apertura:   Establecimiento de un canal de comunicación con un archivo determinado. En C se utiliza el comando fopen.

Cierre:  Cancelación de un canal de comunicación previamente establecido con un archivo.  En C se utiliza el comando fclose();

Asignación:  Se le asocia un nombre de achivo con la extensión correspondiente.

Actualización:  Es un proceso que modifica el contenido de la base de datos (altas, bajas, cambios).

Factor:

1. Velocidad de cambios de los datos.
2. Necesidad de tener los datos al día.
3. Tamaño del archivo maestro.

En proporción:

1. Directa (disponibilidad).
2. Directa (riesgos).
3. Inversa (costos).

Organización de la Información en un Disco Duro

     La información se almacena en el disco duro en sectores y pistas. Las pistas son círculos concéntricos divididos en sectores, cada sector contiene un número fijo de bytes, y se agrupan en clusters.
   
     Los sectores no son físicos sino lógicos y no son iguales en todos los discos, varía en función del tamaño del disco y Sistema Operativo instalado, que es quien divide los sectores.
   
     El principal sector del disco duro es el denominado sector de arranque, suele ser el primer sector del primer disco. Aquí el sistema Operativo guarda la información que debe cargarse al arrancar el equipo.
  
     La preparación del disco se puede hacer de dos formas, Formateo a bajo nivel, que establece las pistas y los sectores en el disco, la otra forma es el formateo a alto nivel, graba las estructuras de almacenamiento de ficheros y la FAT.

Algunos Conceptos

Proceso:   Son programas en ejecucion, archivos ejecutables. Existen con procesadores con multiproceso y otros con sólo uno.

Controlador de Procesos:  Dice cuantos programas se van a ejecutar.

Hilos:  Es una subdivición de un programa. También podrían ser funciones.

Controlador de Archivos:  Maneja toso los archivos ya sea paginación, segmentaci´pon, virtual RAM O Disco Duro.

Memoria Virtual:  Simulador de memoria RAM utilizando dispositivos de almacenamiento Secundario.

Paginación:  Archivo dividido en páginas y se crea un índice que die donde esta guardado.

Segmentación:  Tamaño variable, divide los archivos.

Sector: Es una parte en forma de cuña del mismo, cada sector está numerado. el sector más pequeño empleado fue de 512 bytes.  No son físicos sino lógicos.

Clusters:  Agrupación de sectores continuos y su capacidad depende del tamaño del disco. Es la capacidad más pequeña para asignar archivos.

FAT(Tabla de Localización  de Ficheros):  Índice de los archivos, e indica donde se encuetran.

Buffer: Memoria de paso, permite guardar la información para ser procesada, almacena lo último que se ha leído o guarado en el disco duro.

FORMA DE ORGANIZACIÓN POR BLOQUES EN EL DISCO DURO:

     Los bloques son de longitud fija o variable, son definidos por usuario o Sistema Operativo. Se designan como registros físicos.

     La ventaja de organización por bloque es que los archivos los deja todo unido y por concecuencia no existe fragmentación a diferencia de organizacióon por pistas o sectores.

Clasificación y Caracteristicas de la Estuctura de Archivos

Estructura de Archivos:
   Es el nivel más básico de organización.
   Es una organización impuesta a un archivo para facilitar su procesamiento. Es la combinación de representaciones de datos en archivos y al poseer una estructura de arvhivos asegura que los usuarios y programas pueden acceder y escribir a los archivos.

    Un buen diseño de estuctura de archivos brindará una gran capacidad de información, sin gastar tiempo de espera.


Características de los Archivos:

• Independencia de las informaciones respecto de los programas.
• La información almacenada es permantente.
• Un archivo puede ser accedido por distintos programas en distintos momentos.
• Gran capacidad de almacenamiento.

Clasificación Según su Acceso :

• Secuenciales:   El usuario los utiliza uno tras otro.
• Directo: El usuario va a donde quiere drectamente.
• Por índice:  Dice el contendio y donde se encuentra específicamente el archivo.
• Dinámico: De manera aleatoria accede a los archivos.

Dependiendo Tipo de Valores  Permitidos a Cada Byte:

• Texto: Toma lo creado por medio de código Ascci y  lo convierte en hexadeciimal.
• Binario: Todos los que no tengan formato o de texto. Ej. Música, Imágenes, etc.

Dependiendo Dirección de Flujo de Datos:

•   De Entrada:  Los datos se leen por el programa desde los archivos.
•   De Salida: Los datos se escriben desde el programa.
•   De Entrada y Salida: Las dos cosas.

Según la Longitud de Registro:

• Longitud Variable:  Cada byte es como un registro,. Son poco utilizados.
• Longitud constante:  Los datos se almacenan en forma de registro de tamaño constante. En C se utilizan las estructruras para definir registros.

Clasificación por Función:

• Maestros:  En el que principalmente sus datos se almacenan permanentemente. Contiene los datos principales de una base de datos.
• De Transacciones:  Es el archivo que recolecta toso los datos para modificar.
• De Reporte:  Resultados de consultas a partir de las transacciones.
• De Programa:  Archivos que tienen instrucciones necesarias para que funcionen los programas.
• De Texto:  Tipo de formato para almacenar registro de datos en forma de achivo. Continen datos alfanuméricos.

Dispositivos de Almacenamiento Secundario

     Un dispositivo de almacenamiento es todo aparato que se utilice para grabar los datos de la computadora ya sea de forma permanente o temporal.

    
     El dispositivo de almacenamiento primario es aquel que su contenido es temporal. En cambio los dispositivos de almacenamiento secundario que son en los que nos enfocaremos son aquellos que su contenido es permanente.

  

EVOLUCIÓN:

1) Tarjeta Perforada

     Las tarjetas perforadas son el primer dispositivo de almacenamiento tienen forma de cartulinas gruesas con unas cuantas perforaciones, estas se conectaban a la computadora para leer su contenido y esta lo hacía de forma secuencial  y ya que se le había hecho las perforaciones, ya no se le podía modificar su contenido. Una sola perforación en una columna correspondía a un número, mientras que dos perforaciones en diferentes posiciones de una misma columna correspondían a una letra.
    
     Cada columna tenía diez posiciones numeradas del “0” al “9” y dos más sin numerar situadas hacia el borde superior de la tarjeta. Una perforación, por ejemplo, en la posición “1” de cualquier columna correspondía igualmente con el número “1”, mientras si se añadía otra perforación en la parte más alta sin numerar de la misma columna, correspondía entonces a la letra “A”, solamente  se podía poner ochenta letras, números o signos por cada línea impresa de lectura, correspondientes a las 80 columnas de la tarjeta perforada.

 

 

2) Cinta Magnética

 
     Una cinta magnética es un medio de almacenamiento de información que se graba mediante pista en una banda de plástico con un material magnetizado, la manera en que funciona es linealmente esto significaba ocupar completamente la anchura de la cinta y escribiendo o leyendo todas las pistas a la vez, solo graba una pista a la vez,después de realizar una pasada completa, la cabeza se desplaza ligeramente y hace otra pasada en la dirección contraria.

     Este procedimiento es repetido hasta que todas las pistas han sido leídas o escritas, existe un método llamado “helical” en el cual, solo necesita una pasada para leer o grabar en la cinta.

3) Discos Magnéticos

     Algunos discos son permanentes, en el sentido de que no se pueden desconectar de los circuitos que los rodean y que sirven para comunicarse con la computadora para leer y escribir la información en el disco, y son los que han terminado llamándose discos duros .

     Otros discos se pueden remover del dispositivo que lee y escribe información. Estos discos son una capa delgada y flexible y se les conoce como disquetes.

4) Discos Duros 

     Dentro de un disco duro hay varios platos (entre 2 y 4), que son discos (de aluminio o cristal) concéntricos y que giran todos a la vez. El cabezal (dispositivo de lectura y escritura) es un conjunto de brazos alineados verticalmente que se mueven hacia dentro o fuera según convenga, todos a la vez. En la punta de dichos brazos están las cabezas de lectura/escritura, que gracias al movimiento del cabezal pueden leer tanto zonas interiores como exteriores del disco.

     Cada plato tiene dos caras, y es necesaria una cabeza de lectura/escritura para cada cara (no es una cabeza por plato, sino una por cara). Si se mira el esquema Cilindro-Cabeza-Sector, a primera vista se ven 4 brazos, uno para cada plato. En realidad, cada uno de los brazos es doble, y contiene 2 cabezas: una para leer la cara superior del plato, y otra para leer la cara inferior. Por tanto, hay 8 cabezas para leer 4 platos.

5) Discos Ópticos

a) CD

       Capacidad:

               700 MB

       Color del Láser:

               Infrarrojo

       Tasa de Transferencia:

               7.8 Mbps

b) DVD

       Capacidad:

               4.7 - 8.5 GB

       Longitud de Onda del Rayo:

               650 nm

       Color del Láser:

               Rojo

       Tasa de Transferencia:

               11,01 / 10,01 Mbps

      

c) HD DVD

       Capacidad:

               15 - 30 GB

       Longitud de Onda del Rayo:

               405 nm

       Color del Láser:

               Violeta

       Tasa de Transferencia:

               36,55 Mbps

d) Blu-ray

       Capacidad:

               23,3 - 54 GB

       Longitud de Onda del Rayo:

               405 nm

       Color del Láser:

               Azul

       Tasa de Transferencia:

               36,0 / 54,0 Mbps

  

6) Memoria Flash

     Es una tecnología de almacenamiento —derivada de la memoria EEPROM— que permite la lecto-escritura de múltiples posiciones de memoria en la misma operación. Gracias a ello, la tecnología flash, siempre mediante impulsos eléctricos, permite velocidades de funcionamiento muy superiores frente a la tecnología EEPROM primigenia, que sólo permitía actuar sobre una única celda de memoria en cada operación de programación.

     Se trata de la tecnología empleada en los dispositivos pendrive. Teóricamente pueden retener los datos durante unos 20 años y escribirse hasta un millón de veces.

Conceptos principales de "Estructura de Archivos"

     El mapa conceptual que presentamos a continuación muestra la relación de los principales conceptos utilizados en Estructura de Archivos. (De clic sobre la imagen para ampliarla)

Bienvenido al BLOG

     Bienvenidos al blog de la materia Estructuras de Archivos de la carrera Ingeniería en Computación
somos el Equipo  101, que consta de los integrantes:

• José Javier Ponce Anaya.
• José Cristian Ramírez Navarro
• Fernando Cornejo Gutiérrez.
• Carlos Alfredo Gómez González

En este blog postearemos toda la temática de la materia conforme se vaya abordando en clase.