Se agrega justificación de bugo para usar B+ solo de primario.

[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 2a570668e7a73acc19957844faa20a65e9584dc2..7c71ab5246c249931be6578ab9df9cb0a0f81c8f 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


@@ -360,15 +365,88 @@ Estas son las dos razones principales por las cuales elegimos tratar el
  nodo raíz como lo hace el árbol B.
 \layout Section
 
  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
+
+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
+
+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
 
 \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.
+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 más adelante, pero básicamente realizaremos una
+ búsqueda del ancla menor inmediata a la clave del registro que se desea
+ insertar, y esto nos indicará el bloque apropiado (el bloque donde esta
+ el ancla).

 \layout Standard
 
 \layout Standard
 

-La estructura de un nodo del árbol es la siguiente:
+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 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 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
 \layout Itemize
 
 Nivel


@@ -392,8 +470,8 @@ Esta organizaci
  datos ordenado por la clave principal.
 \layout Standard
 
  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
 
  (ver 3.3.1 Inserción)
 \layout Standard
 


@@ -435,13 +513,13 @@ n+1
 \series default 
 \emph default 
  contiene las claves mayores.
 \series default 
 \emph default 
  contiene las claves mayores.

- En el caso particular del nivel 1 el hijo 
+ En el caso particular del nivel 1 (index set) el hijo 

 \series bold 
 \emph on 
 n+1
 \series default 
 \emph default 
 \series bold 
 \emph on 
 n+1
 \series default 
 \emph default 

- contiene las claves mayores o iguales ya que el 
+ (sequence set) contiene las claves mayores o iguales ya que el 

 \begin_inset Quotes eld
 \end_inset 
 
 \begin_inset Quotes eld
 \end_inset 
 


@@ -458,6 +536,12 @@ En nuestro caso hemos implementado un Secuencial Indexado tipo ISAM (Indexed
  bloque en el archivo de datos, es decir, solo se guardan en los nodos del
  árbol la menor de las claves de un bloque del archivo de datos, acompañada
  cada clave por el numero de bloque al cual pertenece.
  bloque en el archivo de datos, es decir, solo se guardan en los nodos del
  árbol 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 Standard
+
+Hemos adoptado que la cantidad de claves máxima en un nodo del árbol sea
+ una cantidad impar, ya que esto facilita la elección de la clave que será
+ promovida hacia su nodo padre en caso de que se produzca un overflow en
+ el nodo.

 \layout Subsection
 
 Inserción
 \layout Subsection
 
 Inserción


@@ -594,7 +678,70 @@ Si el registro a eliminar fuera el primero del bloque, habr
 \layout Standard
 
 En cualquier otro caso, solo se eliminará el registro correspondiente y
 \layout Standard
 
 En cualquier otro caso, solo se eliminará el registro correspondiente y

- se justificarán los regitros a izquierda.
+ se justificarán los registros a izquierda.
+\layout Subsection
+
+Búsqueda
+\layout Standard
+
+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 número de bloque donde se debe
+ encontrar el registro.
+\layout Standard
+
+Para obtener dicho número de bloque, el árbol internamente busca el ancla
+ menor inmediata a la clave buscada y luego devuelve el número de bloque
+ de datos donde está dicha ancla (el nro bloque será el dato asociado a
+ la clave ancla, en el árbol), el cual será el bloque potencial donde se
+ encuentre el registro buscado.
+\layout Standard
+
+Una desventaja de esta implementación con indexación parcial, es que no
+ sabremos si el registro se encuentra efectivamente en el bloque indicado,
+ hasta no buscarlo dentro del mismo en formal secuencial.
+ Si lo hallamos, daremos por finalizada la búsqueda del registro.
+\layout Subsection
+
+Recorrida secuencial de registros
+\layout Standard
+
+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 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ó
+n de archivo, y con el correspondiente árbol de indexación primaria B+ en
+ el disco, si se nos pidiera por ejemplo, recorrer los registros de articulos
+ desde el ID_Articulo 40, hasta el ID_Articulo 1406, la operativa será la
+ siguiente:
+\layout Itemize
+
+Acudimos al árbol y obtenemos el numero de bloque para el ID_Articulo 40,
+ buscando el ancla menor inmediata y obteniendo el nro de bloque de datos
+ donde se encuentra, siendo este el nro de bloque donde debería estar el
+ artículo de clave ID_Articulo 40.
+\layout Itemize
+
+Levantamos el bloque de datos y lo recorremos secuencialmente, pues como
+ dijimos anteriormente, sus registros se encuentran ordenados por la clave
+ de identificación primaria, en este caso ID_Articulo.
+\layout Itemize
+
+Cuando ya hayamos procesado todo el bloque, debemos obtener la siguiente
+ ancla a través del árbol y repetir el proceso.
+\layout Itemize
+
+NOTA: Cabe desatacar, que todas las anclas estan en las hojas del B+, y
+ por ello las recorremos a nivel hojas a traves del Sequence Set, que gracias
+ a su encadenamiento, nos permite obtener en forma muy directa y efectiva,
+ las anclas de bloque ordenadas en secuencia, y por consiguiente, recorrer
+ el archivo en forma secuencial minimizando accesos.

 \layout Chapter
 
 Ordenamiento Externo
 \layout Chapter
 
 Ordenamiento Externo