agrego b y B*

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

diff --git a/doc/informe_2da_entrega.lyx b/doc/informe_2da_entrega.lyx
index 65f4e092d6b277dc9f3ded925cfdea749ca075b6..934ed6e451af4af55e48b0a2484658941e489f91 100644 (file)
--- a/doc/informe_2da_entrega.lyx
+++ b/doc/informe_2da_entrega.lyx
@@ -94,7 +94,12 @@ 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.
+ no tiene sentido el set secuencial (ver página 
+\begin_inset LatexCommand \pageref{sub:justificacion}
+
+\end_inset 
+
+ para una justificación más detallada).

 \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


@@ -319,9 +324,81 @@ Especificaciones de 
 \layout Section
 
 Indice B
 \layout Section
 
 Indice B

+\layout Standard
+
+En esta sección no se explicará como funciona la implementación del árbol
+ B, sino que se darán algunos detalles de la implementación para algunos
+ casos particulares.
+\layout Standard
+
+Cada nodo del árbol cuenta con un header y un array de datos, donde cada
+ dato contiene, entre otras cosas la clave, el dato al que apunta (id/bloque
+ del archivo de datos) y el hijo derecho (aquel nodo que contiene las claves
+ superiores).
+ En el header se guarda el puntero (numero de nodo) al hijo izquierdo, que
+ viene a ser el nodo que contiene claves menores a la primer clave de nodo
+ actual.
+\layout Standard
+
+Existen 2 casos particulares para lo que contiene la clave y el dato.
+ El primer caso se da cuando la clave es de tipo string.
+\layout Standard
+
+Cuando un indice debe almacenar string, estos no son guardados en el arbol,
+ sino que se reutiliza la estructura EMUFS de la primer entrega para guardar
+ las cadenas de texto, utilizano para ello una organización de registros
+ de longitud variable sin bloques, elegida de forma arbitraria.
+ En la clave del arbol se guardará entonces el ID del registro que contiene
+ el texto en la estructura mensionada anteriormente.
+ Cuando se quiere recuperar una clave, se lee el archivo que contiene las
+ claves de texto (que permanecen abreviadas).
+\layout Standard
+
+El otro caso particular es para los indices con clave repetida (como ser
+ el selectivo y el exahustivo).
+ Para este caso lo que cambia es lo que se almacena en el campo DATO que
+ acompaña a la clave.
+ Este DATO contendra el ID de un registro que se guarda nuevamente en un
+ EMUFS en formato de registro de longitud variable sin bloques, donde estarán
+ los ID/Bloque reales del archivo de dato de todas las ocurrencias de la
+ clave correspondiente.
+\layout Standard
+
+Cada vez que se inserta una clave y ya existia una previa, se agrega a dicho
+ arreglo la nueva posicion y luego se guarda.
+ Si al eliminar todos los datos de una clave este array quedara vacio, la
+ clave es eliminada del arbol.
+\layout Standard
+
+Puede darse el caso (es mas, casi todos los indices utilizados en el TP
+ son de esta manera) que ocurran ambas situaciones descriptas anteriormente,
+ por lo que para un indice, por ejemplo de presentacion de los articulos,
+ se tenga que acceder a 9 archivos (el arbol B, 4 para los string, 4 para
+ las claves repetidas) para obtener todos los ID del archivo de datos para
+ mostrar en pantalla.
+ Con esta falla de diseño y todo el acceso a registros por campos de identifacac
+ion no unico es muy superior a realizar una busqueda secuencial sobre todo
+ el archivo para realizar una consultas.

 \layout Section
 
 Indice B*
 \layout Section
 
 Indice B*

+\layout Standard
+
+Para la implantación de los árboles B* se tomo la desición de tratar a la
+ raiz como si fuera un árbol B en lugar de tomar una raiz de 2*tam_bloque
+ para reutilizar el código ya hecho para el árbol B y todas las funciones
+ anexas.
+\layout Standard
+
+Lo único que se reescribió fue la función insertar, que aunque es muy similar
+ al del otro árbol, meter más codigo en la misma función hacía aún más dificil
+ de mantener y debuggear el árbol.
+\layout Standard
+
+Otro cambio a la API de árbol B fue en el borrar, que mediante una macro
+ se verifica que tipo de árbol se está tratando y en base a eso se calcula
+ la cantidad de hijos mínimos antes de fundir 2 nodos (o pedir una clave
+ a algún hermano).

 \layout Subsection
 
 Decisiones de diseño
 \layout Subsection
 
 Decisiones de diseño


@@ -382,10 +459,10 @@ En torno a esta distinci
  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.
  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
+ La operativa se detalla más adelante, pero básicamente realizaremos una

  búsqueda del ancla menor inmediata a la clave del registro que se desea
  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).
+ insertar, y esto nos indicará el bloque apropiado (el bloque donde esta
+ el ancla).

 \layout Standard
 
 Como resultado concreto de este comportamiento (teniendo en cuenta también
 \layout Standard
 
 Como resultado concreto de este comportamiento (teniendo en cuenta también


@@ -400,6 +477,40 @@ Como resultado concreto de este comportamiento (teniendo en cuenta tambi
  del encadenamiento es denominada 
 \series bold 
 Sequence Set.
  del encadenamiento es denominada 
 \series bold 
 Sequence Set.

+\layout Subsubsection
+
+
+\begin_inset LatexCommand \label{sub:justificacion}
+
+\end_inset 
+
+Razones por las cuales el B+ es útil sólo para clave principal.
+\layout Standard
+
+El mejor aprovechamiento del Arbol B+ se da en su utilizacion en implementacion
+ ISAM (Indexed Sequential Access Method), en donde se realiza una indexacion
+ parcial de claves, sólo ingresando en el árbol las claves anclas de cada
+ bloque en el archivo de datos.
+ 
+\layout Standard
+
+Esta aplicación del árbol B+ a ISAM, además de indicarnos donde grabar y
+ donde buscar los registros por identificación primaria, nos asegura el
+ ordenamiento de los registros parcialmente a nivel de bloque (esto es,
+ los registros en un bloque dado, estarán ordenados, pero los bloques no
+ necesariamente).
+ Así pués, recorriendo el Sequence Set del Arbol B+, minimizaremos los saltos
+ de lectura en disco, pues dentro de un bloque indicado por un ancla dada
+ en el Sequence Set, podremos recorrer los registros secuencialmente.
+\layout Standard
+
+Visto y considerando que la aplicación más importante a nuestro criterio
+ del Arbol B+, era para la indexacion parcial de claves primarias, y que
+ en caso de utilizarlo para otros índices, el B+ se convertiría simplemente
+ en un B con encadenamiento a nivel de hojas, luego de consultar con los
+ ayudantes, decidimos utilizarlo unicamente para el índice primario, y utilizar
+ el B y B* para los restantes índices y/o el primario.
+ 

 \layout Subsection
 
 Estructura
 \layout Subsection
 
 Estructura


@@ -648,7 +759,7 @@ B
 El proceso de búsqueda de un registro por su clave de identificación primaria
  en la Organización Secuencial Indexada, es bastante directa en su entendimiento.
  Para buscar un registro, acudiremos al árbol B+ con la clave anteriormente
 El proceso de búsqueda de un registro por su clave de identificación primaria
  en la Organización Secuencial Indexada, es bastante directa en su entendimiento.
  Para buscar un registro, acudiremos al árbol B+ con la clave anteriormente

- mencionada, y obtendremos del mismo, el numero de bloque donde se debe
+ mencionada, y obtendremos del mismo, el número de bloque donde se debe

  encontrar el registro.
 \layout Standard
 
  encontrar el registro.
 \layout Standard
 


@@ -671,10 +782,9 @@ Recorrida secuencial de registros
 Una consecuencia importante de la organización secuencial indexada, en este
  caso implementada a través de un árbol B+ con indexación parcial, es que
  como mencionamos anteriormente, los registros dentro de un bloque se encuetran
 Una consecuencia importante de la organización secuencial indexada, en este
  caso implementada a través de un árbol B+ con indexación parcial, es que
  como mencionamos anteriormente, los registros dentro de un bloque se encuetran

- ordenados, y si bien los bloques en si pueden estar no ordenados en el
- archivo de datos, algunos lo estaran, y minimizarán en base a estas cosa
- características, los tiempos de acceso para una recorrida secuencial de
- registros.
+ ordenados, y si bien los bloques en si pueden no estar ordenados en el
+ archivo de datos, algunos lo estarán, y minimizarán en base a estas característ
+icas, los tiempos de acceso para una recorrida secuencial de registros.

 \layout Standard
 
 Suponiendo que nos encontramos con varios registros cargados en esta organizació
 \layout Standard
 
 Suponiendo que nos encontramos con varios registros cargados en esta organizació


@@ -695,7 +805,7 @@ Levantamos el bloque de datos y lo recorremos secuencialmente, pues como
  de identificación primaria, en este caso ID_Articulo.
 \layout Itemize
 
  de identificación primaria, en este caso ID_Articulo.
 \layout Itemize
 

-Cuando ya hallamos procesado todo el bloque, debemos obtener la siguiente
+Cuando ya hayamos procesado todo el bloque, debemos obtener la siguiente

  ancla a través del árbol y repetir el proceso.
 \layout Itemize
 
  ancla a través del árbol y repetir el proceso.
 \layout Itemize