agrego capitulo para especificaciones de arboles y pongo algo del B+ que bugo sabrá...

diff --git a/doc/informe_2da_entrega.lyx b/doc/informe_2da_entrega.lyx
index 1c34de4b003f8411689bcdb8a2040b0ff6ded4dc..2d6cf6dd430e78f42754dac08b9a1d8c4fcf6278 100644 (file)
--- 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
 
 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
 \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 
 \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
 
 
 \layout Itemize
 
 


@@ -278,6 +276,8 @@ EMUFS
 Integración con 
 \family typewriter 
 EMUFS
 Integración con 
 \family typewriter 
 EMUFS

+\family default 
+.

 \layout Standard
 
 Para integrar la utilización de índices a 
 \layout Standard
 
 Para integrar la utilización de índices a 


@@ -287,7 +287,7 @@ EMUFS
  fueron necesarios los siguientes cambios:
 \layout Paragraph
 
  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
 \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
 
  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 
 \layout Standard
 
 Se agrega a la estructura 


@@ -315,17 +315,183 @@ INDICE
 , donde el primero es siempre el índice principal.
 \layout Chapter
 
 , donde el primero es siempre el índice principal.
 \layout Chapter
 

-Implementación
+Especificaciones de índices

 \layout Section
 
 \layout Section
 

-Árbol B
+Indice B

 \layout Section
 
 \layout Section
 

-Árbol B*
+Indice B*

 \layout Section
 
 \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
 \the_end