From c869e2f4e8c17209c8afc4cd60f72ad03f6042e8 Mon Sep 17 00:00:00 2001 From: Alan Kennedy Date: Mon, 31 May 2004 08:56:57 +0000 Subject: [PATCH] Extiendo un poco la intro --- doc/informe.lyx | 8 +- doc/informeChapter5.lyx | 377 +++++++++++++++++++++++++++++++++++- doc/informe_2da_entrega.lyx | 50 ++++- 3 files changed, 422 insertions(+), 13 deletions(-) diff --git a/doc/informe.lyx b/doc/informe.lyx index dc71eb8..50e10c8 100644 --- a/doc/informe.lyx +++ b/doc/informe.lyx @@ -6631,10 +6631,10 @@ Analizaremos ahora que pasa luego de borrar varios registros en posiciones para almacenar registros grandes en ambos casos (recordar que tipo1 tiene recuperación de espacio libre para n bloques consecutivos, no siempre se agrega al final). - De todos determinar un espacio libre para un archivo de tipo 2 es mucho - más rápido que para tipo1 si el tamaño del registro es grande, ya que el - archivo de tipo1 debe hacer una búsqueda sobre n bloques, mientras que - el tipo 2 encuentra un gap de tamaño suficiente más rápido. + De todos modos determinar un espacio libre para un archivo de tipo 2 es + mucho más rápido que para tipo1 si el tamaño del registro es grande, ya + que el archivo de tipo1 debe hacer una búsqueda sobre n bloques, mientras + que el tipo 2 encuentra un gap de tamaño suficiente más rápido. \layout Standard Pero no todo es color de rosa en el mundo de archivos de tipo2. diff --git a/doc/informeChapter5.lyx b/doc/informeChapter5.lyx index 06e07c4..4c7b215 100644 --- a/doc/informeChapter5.lyx +++ b/doc/informeChapter5.lyx @@ -120,7 +120,311 @@ EMUFS_REG_SIZE ), y posteriormente el registro (bloque de datos) en sí. Luego se encuentra el espacio libre de 18 bytes dejado por el registro de 10 bytes eliminado (10 bytes de datos + header de 8 bytes) y finalmente - el segundo registro mencionado.dsds + el segundo registro mencionado. +\layout Subsection + +Comportamiento Particular de los Archivos Auxiliares +\layout Standard + +Como fue explicado al inicio de la documentación, la implementacion de cualquier +a de las tres organizaciones físicas de archivos presenta la necesidad de + poseer tres archivos auxiliares que actuarán como índice de direcciones + de registro (. +\series bold +idx +\series default +), administrador de espacio libre ( +\series bold +.fsc +\series default +) y administrador de Id's liberados ( +\series bold +.did +\series default +) respectivamente. +\layout Standard + +No obstante, cada tipo de organización presentara sus particularidades respecto + de estos tres archivos, las cuales describiremos a continuación en caso + de haberla. +\layout Subsubsection + +Archivo índice o de posiciones relativas (.idx) +\layout Standard + +El archivo indice ( +\series bold +.idx +\series default +), permite la localizacin de los registros en el .DAT de forma directa, mediante + la obtención de su offset o posición relativa respecto del inicio del +\series bold +.dat +\series default + en donde se encuentra un registro dado, indicado por su ID. +\layout Standard + +Así pues, si tomamos el ejemplo descripto al inicio de este capítudlo, tendremos + las siguientes entradas en el archivo indice +\series bold +.idx +\series default + : +\newline + +\layout Standard + + +\begin_inset Tabular + + + + + + + +\begin_inset Text + +\layout Standard + + +\emph on +ID_REGISTRO +\end_inset + + +\begin_inset Text + +\layout Standard + + +\emph on +OFFSET +\end_inset + + +\begin_inset Text + +\layout Standard + +\end_inset + + + + +\begin_inset Text + +\layout Standard + + +\series bold +0 +\end_inset + + +\begin_inset Text + +\layout Standard + + +\series bold +4 +\end_inset + + +\begin_inset Text + +\layout Standard + +El primer registro (reg0) comienza en el byte 4 +\end_inset + + + + +\begin_inset Text + +\layout Standard + +1 +\end_inset + + +\begin_inset Text + +\layout Standard + + +\series bold +60 +\end_inset + + +\begin_inset Text + +\layout Standard + +El segundo registro (reg1) comienza en el byte 60 +\end_inset + + + + +\end_inset + + +\layout Standard + + +\series bold +\emph on +\SpecialChar ~ + +\newline +Observación: +\series default +\emph default + LOCATION indica donde comienza el header del registro buscado, y por consiguien +te luego del header tendremos el registro en sí (los datos). +\layout Subsubsection + +Achivo de Gaps / Espacios Libres (.fsc) +\layout Standard + +El archivo de espacios libres o gaps (.fsc), tiene como función la administracion + del espacio libre o gaps (agujeros), generados por previas eliminaciones + de registros en el archivo de datos. + El mismo, nos indicará donde hay lugar para insertar un nuevo registro + (se podrán insertar en algún gap acorde, o bien al final del archivo). + Este archivo será utilizado tambien para el proceso de compactación de + un archivo, explicado luego. +\layout Standard + +Así pues, si tomamos el ejemplo descripto al inicio del documento, tendremos + las siguientes entradas en el archivo índice +\series bold +.fsc +\series default + : +\newline + +\newline + +\begin_inset Tabular + + + + + + + +\begin_inset Text + +\layout Standard + + +\emph on +OFFSET +\end_inset + + +\begin_inset Text + +\layout Standard + + +\emph on +FREESPACE +\end_inset + + +\begin_inset Text + +\layout Standard + +\end_inset + + + + +\begin_inset Text + +\layout Standard + + +\series bold +42 +\end_inset + + +\begin_inset Text + +\layout Standard + + +\series bold +18 +\end_inset + + +\begin_inset Text + +\layout Standard + +18 bytes libres a partir del byte 42 del .dat +\end_inset + + + + +\end_inset + + +\layout Standard + + +\series bold +\emph on +\SpecialChar ~ + +\newline +Nota: +\series default +\emph default + Por requerimiento del algoritmo de compactación, los gaps se graban en + forma ordenada en el (.fsc). + (El orden se corresponde con lo que hay en el .dat) +\layout Subsubsection* + +GAP Merging +\layout Standard + +Si bien la utilización concreta de los GAPS será explicada posteriormente + en la ALTA y BAJA de registros, debemos remarcar la funcionalidad de MERGING + que posee nuestro sistema FSC. +\layout Standard + +Ante la eliminación de un registro del archivo de datos, se generara por + consiguiente un gap o espacio libre en alguna posición del archivo. + Ese gap deberá ser registrado en el archivo de gaps (.fsc). + Ahora bien, nuestro sistema de gaps, contemplará como es debido, la posibilidad + de que se haya eliminado un registro que posee un GAP por delante, un GAP + por detrás, o bien un GAP por delante y por detrás del mismo. +\layout Standard + +Nuestro sistema actuará en consecuencia, realizando un merge de los espacios + libres, y unificándolos en una UNICA entrada en el archivo .fsc, que contendrá + como dato de freespace, la suma correspondiente de los espacios libres + antes mencionados. +\layout Subsubsection + +Archivo de ID's liberados (.did) +\layout Standard + +El archivo de ID's liberados no presenta ningún aspecto particular en este + tipo de organización. + Remitirse al capítulo correspondiente a los archivos auxiliares para consultar + su estructura y funcionamiento. \layout Section Comportamiento (funciones de la interfáz) @@ -184,7 +488,15 @@ RegSize \series default ). Contando así con el tamaño del registro, procedemos a leer el mismo (los - datos), dando por finalizada la lectura. + datos), dando por finalizada la lectura y devolviendo el registro pedido. +\layout Standard + + +\series bold +\emph on +ver +\series default +: void *emufs_tipo2_modificar_registro() \layout Subsection Altas de registros @@ -254,6 +566,14 @@ Actualizamos la entrada correspondiente al registro ingresado (determinada .idx \series default ), indicando su offset donde podrá ser accedido luego. +\layout Standard + + +\series bold +\emph on +ver +\series default +: EMUFS_REG_ID emufs_tipo2_agregar_registro() \layout Subsection Bajas de registros @@ -338,6 +658,14 @@ Se marca en el archivo ) la eliminación, mediante el valor ¨-1¨ en el registro correspondiente al registro recién eliminado (se le cambia el valor al n-esimo registro, donde N = IDReg del reg eliminado). +\layout Standard + + +\series bold +\emph on +ver +\series default +: int emufs_tipo2_borrar_registro() \layout Subsection Modificación de registros @@ -366,9 +694,44 @@ NOTA: Como fue indicado, dada la naturaleza de PILA del subsistema de administración de ID liberados, es asegurado que la nueva inserción del registro modificado se realizará con el mismo RegID. +\newline + +\layout Standard + + +\series bold +\emph on +ver +\series default +: EMUFS_REG_ID emufs_tipo2_modificar_registro() \layout Subsection Obtención de estadísticas +\layout Standard + +Se puede tener acceso a las estadísticas generales del archivo, por ejemplo, + cantidad de bloques, cantidad de registros, espacio libre total, espacio + libre promedio, espacio libre máximo y mínimo, etc. +\layout Standard + +Esta información es el resultado de ciertos cálculos realizados tanto en + el archivo de datos como en los archivos índice. +\layout Standard + +Completa una estructura del tipo EMUFS_Estadisticas con las estadísticas + del archivo de datos, espacio libre total, cantidad de registros, cantidad + de bloques, tamaño del archivo en bytes, relaciones entre tamaños y espacios + libres, etc. +\newline + +\layout Standard + + +\series bold +\emph on +ver +\series default +: EMUFS_Estadisticas emufs_tipo3_leer_estadisticas() \layout Subsection Compactación del archivo de datos @@ -622,6 +985,16 @@ Mustmove_bytes = Datsize - Source Damos por terminada así, la explicación del algoritmo de compresión el cual para el caso del tipo 2, es realmente bastante sencillo. +\newline + +\layout Standard + + +\series bold +\emph on +ver +\series default +: void emufs_tipo2_compactar() \layout Section Detalles de implementación (funciones internas, ver si lo ponemos o no) diff --git a/doc/informe_2da_entrega.lyx b/doc/informe_2da_entrega.lyx index 165ff48..1e9f612 100644 --- a/doc/informe_2da_entrega.lyx +++ b/doc/informe_2da_entrega.lyx @@ -360,18 +360,54 @@ Estas son las dos razones principales por las cuales elegimos tratar el nodo raíz como lo hace el árbol B. \layout Section -Indice B+ Secuencial Indexado +Indice B+ Organizacion Secuencial Indexada \layout Subsection Decisiones de diseño \layout Standard -Se ha implementado un índice secuencial indexado utilizando un árbol B+, - el cual tiene la particularidad de tener en sus hojas todas las claves - que se han insertado. +Para la implementación de la organización secuencial indexada de archivos, + se ha utilizado un árbol B+, conocido por ser utilizado en términos generales + para implementaciones de esta índole. \layout Standard -La estructura de un nodo del árbol es la siguiente: +Como particularidad el arbol B+, poseerá en sus hojas todas las claves que + se hayan insertado en el árbol. + No obstante, las mismas no serán todas las claves que se encuentren en + el archivo de datos, sino la primer clave de cada bloque de datos, también + denominadas 'anclas de bloque'. +\layout Standard + +En torno a esta distinción respecto de los demás arboles, el árbol B+ nos + indicará a la hora de grabar registros en nuestro archivo de datos con + bloques (Organización del TP1, Tipo1 o 3), en que bloque de datos debemos + realizar la mencionada inserción. + La operativa se detalla mas adelante, pero basicamente realizaremos una + búsqueda del ancla menor inmediata a la clave del registro que se desea + insertar, y esto nos indicara el bloque apropiado. + (el bloque donde esta el ancla). +\layout Standard + +Como resultado concreto de este comportamiento (teniendo en cuenta también + el borrado y partición de bloques del .dat), obtendremos un archivo secuencial + indexado, en donde los registros se encuentran ordenados a nivel de bloques, + esto es, dentro de un bloque dado del archivo de datos, los registros estan + ordenados por clave primaria. + No obstante, los bloques no estarán necesariamente ordenados, pero igualmente + la cantidad de accesos para recorrer el archivo en forma secuencial, se + ve minimizada respecto de otras organizaciones, gracias al encadenamiento + de las hojas y la posesión de las anclas de bloque, cuya lista resultante + del encadenamiento es denominada +\series bold +Sequence Set. +\layout Subsection + +Estructura +\layout Standard + +Para comprender mejor la implementación particular que hemos dado al árbol + B+, damos una breve reseña de la estructura de un nodo del arbol, la cual + es la siguiente: \layout Itemize Nivel @@ -395,8 +431,8 @@ Esta organizaci datos ordenado por la clave principal. \layout Standard -Para lograr esto, el árbol nos indicará donde (en qué bloque) debe insertarse - un registro. +Para lograr esto, como fue expuesto anteriormente, el árbol nos indicará + donde (en qué bloque) debe insertarse un registro. (ver 3.3.1 Inserción) \layout Standard -- 2.43.0