From: Nicolás Dimov Date: Mon, 31 May 2004 08:00:49 +0000 (+0000) Subject: agrego capitulo para especificaciones de arboles y pongo algo del B+ que bugo sabrá... X-Git-Tag: svn_import_r684~19 X-Git-Url: https://git.llucax.com/z.facultad/75.06/emufs.git/commitdiff_plain/6cbbc480fefe9835cb9ca59e2f29ea4aa7f5f38c agrego capitulo para especificaciones de arboles y pongo algo del B+ que bugo sabrá completar --- diff --git a/doc/informe_2da_entrega.lyx b/doc/informe_2da_entrega.lyx index 1c34de4..2d6cf6d 100644 --- a/doc/informe_2da_entrega.lyx +++ b/doc/informe_2da_entrega.lyx @@ -94,8 +94,7 @@ Exhaustivo Con la autorización de los ayudantes de la cátedra decidimos que el árbol B+ sólo pueda ser utilizado para índices principal ya que de otra manera - no tiene sentido el set secuencial (para una justificación más detallada - ver FIXME: REFERENCIA A EXPLICACION DE B+)3. + no tiene sentido el set secuencial. \layout Standard Finalmente, para obtener listados basados en campos de los cuales no se @@ -152,8 +151,7 @@ indices.h \family typewriter INDICE_DATO \family default -: usado para representar el conjunto de un ID más la ubicación del dato - asociado. +: usado para representar el conjunto de un ID más su dato. \layout Itemize @@ -278,6 +276,8 @@ EMUFS Integración con \family typewriter EMUFS +\family default +. \layout Standard Para integrar la utilización de índices a @@ -287,7 +287,7 @@ EMUFS fueron necesarios los siguientes cambios: \layout Paragraph -Nuevos tipos de archivo +Nuevos tipos de archivo. \layout Standard Se incluyen dos tipos de archivo nuevos T4 y T5, que representan, respectivament @@ -301,7 +301,7 @@ EMUFS ya que al saber que es T4 o T5 siempre se inserta de forma ordenada. \layout Paragraph -Puntero a un arreglo de índices +Puntero a un arreglo de índices. \layout Standard Se agrega a la estructura @@ -315,17 +315,183 @@ INDICE , donde el primero es siempre el índice principal. \layout Chapter -Implementación +Especificaciones de índices \layout Section -Árbol B +Indice B \layout Section -Árbol B* +Indice B* \layout Section -Árbol B+ -\layout Section +Indice B+ Secuencial Indexado +\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. +\layout Standard + +La estructura de un nodo del árbol es la siguiente: +\layout Itemize + +Nivel +\layout Itemize + +Cantidad de claves +\layout Itemize + +Arreglo de claves +\layout Itemize + +Arreglo de hijos +\layout Standard + +Esta estructura se encuentra en el archivo +\family typewriter +indice_bplus.h +\layout Standard + +Esta organización permite, con la ayuda del árbol, mantener el archivo de + datos ordenado por la clave principal. +\layout Standard + +Para lograr esto, el árbol nos indicará donde (en qué bloque) debe insertarse + un registro. + (ver 3.3.1 Inserción) +\layout Standard + +En el caso de una hoja, dado que cada nodo posee un hijo mas que la cantidad + de claves, el hijo que sobra será utilizado como referencia al nodo +\begin_inset Quotes eld +\end_inset + +hermano +\begin_inset Quotes erd +\end_inset + +, lo cual constituye el +\begin_inset Quotes eld +\end_inset + +set secuencial +\begin_inset Quotes erd +\end_inset + + del índice. + Para un nodo que no sea hoja el hijo será el número de nodo correspondiente + según la clave, es decir, para la clave +\series bold +\emph on +n +\series default +\emph default +el hijo +\series bold +\emph on +n +\series default +\emph default + contiene claves menores y el hijo +\series bold +\emph on +n+1 +\series default +\emph default + contiene las claves mayores. + En el caso particular del nivel 1 el hijo +\series bold +\emph on +n+1 +\series default +\emph default + contiene las claves mayores o iguales ya que el +\begin_inset Quotes eld +\end_inset + +secuence set +\begin_inset Quotes erd +\end_inset + + debe contener todas las claves insertadas, esto produce que exista una + repetición de las claves entre el nivel 1 y el 0. +\layout Standard + +En nuestro caso hemos implementado un Secuencial Indexado tipo ISAM (Indexed + Sequential Access Method) el cual posee en sus hojas las anclas de cada + bloque en el archivo de datos, es decir, solo se guardan en los nodos del + arbol la menor de las claves de un bloque del archivo de datos, acompañada + cada clave por el numero de bloque al cual pertenece. +\layout Subsection + +Inserción +\layout Standard + +Para realizar una inserción en el archivo de datos se debe realizar una + consulta en el árbol, la cual nos indicará el número de bloque donde debemos + insertar el nuevo registro. +\layout Standard + +Las consultas se realizan a través de una estructura INDEX_DAT que posee: +\layout Itemize + +Clave +\layout Itemize + +Número de Bloque +\layout Standard + +Esta estructura se encuentra en el archivo +\family typewriter +indice_bplus.h +\layout Standard + +El modo de uso es el siguiente: +\layout Standard + +En primer lugar se carga la clave a insertar en el campo Clave, y en el + campo Número de Bloque se almacena un número de bloque válido, mas adelante + se explica el por qué. +\layout Standard + +Luego se invoca a la función +\family typewriter +int emufs_b_plus_get_bloque(INDICE, INDEX_DAT) +\family default +la cual recibe como parámetro una estructura de índice y un INDEX_DAT para + realizar la consulta. +\layout Standard + +Esta función recorre recursivamente el árbol y busca una clave mayor inmediata + a la enviada, siempre culminando la búsqueda en una hoja. + Al encontrar la clave mayor inmediata, el resultado de la búsqueda será + la clave anterior en el nodo, pues cada clave en el nodo es un ancla de + bloque de datos, de esta manera la clave anterior será menor a la clave + enviada, pues las claves en las hojas estan ordenadas. + +\layout Standard + +En este paso pueden suceder dos cosas: +\layout Enumerate + +Que exista una clave menor a la enviada. +\layout Enumerate + +Que la clave enviada sea menor a todas las claves del árbol. +\layout Standard + +En el primer caso, se ha encontrado la clave y se carga la estructura con + el hijo de esa clave, que será el número de bloque donde debe insertarse + el nuevo registro (por el cual se realizó la consulta), sobreescribiendo + el valor que almacenaba al ingresar, y la función retornará código 0 que + indica que se ha encontrado un bloque donde insertar. +\layout Standard -Ordenamiento externo +En el segundo caso, puede darse que la clave enviada sea menor a todas las + claves del árbol, por lo cual no es posible encontrar un ancla de bloque + para esa clave. + Aquí la función retornará código -1 lo cual indica que no se ha encontrado + un bloque donde insertar el registro nuevo, y es por esto que la estructura + debe inicializarse con un número de bloque válido antes de realizarse la + consulta. \the_end