Agrego funciones de busqueda y recorrida secuencial del B+

[z.facultad/75.06/emufs.git] / doc / informeChapter5.lyx

diff --git a/doc/informeChapter5.lyx b/doc/informeChapter5.lyx
index 06e07c47a8cbf602fe2d58af6f6acb621086b7ea..4c7b215d3a15bca89c24ef421a92b0bc8167bf2d 100644 (file)
--- 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
 ), 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
+<lyxtabular version="3" rows="3" columns="3">
+<features>
+<column alignment="center" valignment="top" leftline="true" width="0">
+<column alignment="center" valignment="top" leftline="true" width="0">
+<column alignment="center" valignment="top" leftline="true" rightline="true" width="0">
+<row topline="true" bottomline="true">
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\layout Standard
+
+
+\emph on 
+ID_REGISTRO
+\end_inset 
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\layout Standard
+
+
+\emph on 
+OFFSET
+\end_inset 
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\layout Standard
+
+\end_inset 
+</cell>
+</row>
+<row topline="true">
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\layout Standard
+
+
+\series bold 
+0
+\end_inset 
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\layout Standard
+
+
+\series bold 
+4
+\end_inset 
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\layout Standard
+
+El primer registro (reg0) comienza en el byte 4
+\end_inset 
+</cell>
+</row>
+<row topline="true" bottomline="true">
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\layout Standard
+
+1
+\end_inset 
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\layout Standard
+
+
+\series bold 
+60
+\end_inset 
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\layout Standard
+
+El segundo registro (reg1) comienza en el byte 60
+\end_inset 
+</cell>
+</row>
+</lyxtabular>
+
+\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
+<lyxtabular version="3" rows="2" columns="3">
+<features>
+<column alignment="center" valignment="top" leftline="true" width="0">
+<column alignment="center" valignment="top" leftline="true" width="0">
+<column alignment="center" valignment="top" leftline="true" rightline="true" width="0">
+<row topline="true" bottomline="true">
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\layout Standard
+
+
+\emph on 
+OFFSET
+\end_inset 
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\layout Standard
+
+
+\emph on 
+FREESPACE
+\end_inset 
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\layout Standard
+
+\end_inset 
+</cell>
+</row>
+<row topline="true" bottomline="true">
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\layout Standard
+
+
+\series bold 
+42
+\end_inset 
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\layout Standard
+
+
+\series bold 
+18
+\end_inset 
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\layout Standard
+
+18 bytes libres a partir del byte 42 del .dat
+\end_inset 
+</cell>
+</row>
+</lyxtabular>
+
+\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)
 \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
 \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
 \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.
 .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
 \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).
 ) 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
 \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.
  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 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
 \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.
 
 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)
 \layout Section
 
 Detalles de implementación (funciones internas, ver si lo ponemos o no)