ARI: Unidad 2

De La Palta

Estructuras Básicas de Archivos: Una estructura de archivos es una técnica para agrupar físicamente los registros de un archivo en dispositivos de almacenamiento secundario.

Se debe considerar:

• Características físicas de los dispositivos de almacenamiento
• Sistema Operativo existente
• Software para la administracion de archivos.
• Nececidades del usuario para almacenar y accesar datos.

Criterios:

• Acceso rápido para la recuperacion de datos.
• Alto rendimiento para las transacciones de procesamiento.
• Uso eficiente del espacio en disco
• Protección ante pérdida de datos y falllas
• Minimización de la nececidad de reorganizacion de los datos

Organizacion Lógica de los Datos:

• Dentro del Archivo:
  • Coleccion de registros estructurados
  • En torno a una clave
  • Independiente del dispositivo
  • Interesa más su uso que sus atributos físicos

Operaciones sobre archivos

• Recorrer el archivo
• Agregar registros al archivo
• Eliminar registros del archivo
• Modificar valores del archivo
• Ordenar el archivo

Conceptos maracos:

1. Registro: Definicion de cada uno de los registros de datos (duh!) que serán usados dentro de una aplicación, y cuya extensión determina el tipo de archivo que lo contiene.

• • Archivo de Largo Fijo (ALF): Compone registros del mismo tipo(mismo tamaño y wa).
  • Archivo de largo Variable (ALV): Pueden ser por distintas causas:
    • Registros del mismo tipo, pero al menos uno de los campos tiene un NUMERO DE OCURRENCIAS variable.
    • Registro del mismo tipo pero LARGO de al menos uno de sus campos es variable
    • El archivo se compone de registros del mismo tipo, pero uno de los campos es opcional.
    • El archivo se compone por mas de un tipo de registro.

1. Campo o Atributo (Clave): Ítem de datos que describe una característica de la entidad representada por un registro lógico. Tiene distintos tipos:

• • Clave Candidata: Atribuo(s) que no soportan valores repetidos. Ej: el RUT.
  • Identificador o Clave primaria: Clave candidata escogida como clave de acceso principal.
    • CLave Alternativa: Toda clave candidata que no es elegida xD.
    • Clave Secundaria: Atributo que permite valores repetidos.
    • Clave Inteligente: Atributo cuyo contenido permite derivar informacion adicional de la entidad a la cual pertenece. Ej: el ROL

1. Archivos Secuenciales: Registros almacenados "uno tras otro". Características:

• • El mas simple de usar!
  • Espacio Ocupado es Mínimo!!, solo se almacenan los datos.
  • Poseen dos tipos de orden, Desordenado, y Ordenado (LOL).

• • • Desordenado Vs/ Ordenado:
      • Pendiente :P

Ordenamiento Externo

• Aplicable a archivos que por su tamaño no pueden ordenarse en memoria principal.
• Consta de dos fases: una fase de ordenamiento y una fase de mezcla.

La Fase de ordenamiento:

1. Se leen datos que son almacenados en memoria principal, en un área de ordenamiento
2. Usando una rutina de ordenamiento interno obtiene los registros ordenados, los que son escritos en dos o más archivos (particiones) en memoria secundaria
3. Los registros en las particiones quedan ordenados en forma relativa a cada una de ellas
4. Se mezclan las particiones

La Fase de Mezcla:

• Se combinan los archivos obtenidos en la fase anterior, es decir, se mezclan las pariciones generadas en la fase de ordenamiento, produciendo particiones más grandes hasta llegar a una sola partición: el archivo ordenado.

Algoritmos para la Fase de Ordenamiento:

1. Ordenamiento Interno: Consiste en leer M registros de una vez desde el archivo desordenado, luego se ordenan a través de un algortimo de ordenamiento interno (duh!) y se generan particiones de salida. Se asume que M es el tamaño de la memoria principal disponible (tam del buffer).

1. Selección por Reemplazo: Consiste en leer M registros, e ir generando archivos de salida aprovecando "algún" ordenamiento parcial que pueda existir en el archivo de entrada. M = tam. del Buffer.

• • Importante Interno y Reemplazo: -Al tener particiones grandes, se requeriran menos mezclas, sin embargo, esto no es el único criterio a considerar para seleccionar un algoritmo
    • Una ventaja del ordenamiento interno es que genera particiones del mismo tamaño, excepto la ultima.
    • La seleccion por reemplazo, en promedio, produce particiones más grandes que el ordenamiento interno.

1. N-Way Balanceada: Las particiones son agrupadas en dos conjuntos, lo más cercanos posibles en cuanto al número de registro que contengan. Los registros de los archivos de entrada son leídos y las particiones de mezcladas son distribuidas en los archivos de salida. Esto se realiza en varias fases, alternando el rol de los archivos entre éstas.

1. Mezcla Óptima: Las particiones iniciales son escritas en archivos separados, así se tiene un conjunto de F archivos cada uno con una particion. Durante cada fase, las F-1 particiones màs pequeñas son leídas y mezcladas, y la partición mezclada es escrita en un archivo de salida. Los archivos de entrada son removidos del conjunto y los archivos de salida son agregados. El Proceso de repite hasta que el conjunto contiene un único archivo.

1. Mezcla Polifásica: Variación no balanciada de la mezcla N-Way....

Archivos Secuenciales con Registros Mixtos

• Es posible almacenar en un mismo archivo registros de diferentes tipos (lo que da origen a un archivo de largo variable)
• Para distinguir los registros de un archivo mixto, cada registro tiene, ademas de los campos propios, un campo llamado "tipo_registro", el cual especifica el tipo de registro.

Archivos Directos

Tipos de direccionamiento:

1. Direccionamiento Directo: Los registros son direccionados en forma Absoluta! (el programa entraga una dirección de hardware y el método de acceso ubica el registro) o Relativa""(Entrega un número relativo a la posición del primer registro en el archivo y el método de acceso ubica el registro).

• • La clave primaria seria una direccion de hardware o un número relativo según sea el caso(lol).
• Ventajas!:
  • No existe transformacion previa de la clave primaria(eficiente ;D), pero es dificil que la clave primaria pueda ser una dirección de hardware (:C).
  • No existen problemas de colisiones :D.
  • Fácil acceso secuencial, pues las claves pueden ser asignadas en forma ordenada.
• Desventajas!:
  • Cualquier cambio de hardware o falla de él, significaria rehacer la asignación de claves (doble lol).
  • Claves deben definirse en base a características físicas del dispositivo, y no a lo que le conviene al usuaria :C.

1. Direccionamiento Indirecto: Tambien llamado direccionamiento algorítmico. La direccion a ser usada por el S.O para ubicar el registro se obtiene con una función de trasnformacion al valor de la clave primaria (hashing).

• • El espacio de almacenamiento es dividido en secciones llamadas buckets, que pueden almacenar uno o más registros lógicos y se puede seleccionar su capacidad.
  • Un bucket es un bloque del disco o un grupo de bloques de disco. Esta dividido en casilleros de tamaño fijo denominados slots.
  • En la actualidad, la mayoria de los SABD (WTF? Sistema Administracion Base de Datos AWEONAO, firma saint..) implementan sólo este esquema.

...