X-Git-Url: https://git.llucax.com/z.facultad/75.06/emufs.git/blobdiff_plain/187d0e19e248fcf279b0180f4cb903ad03f5f10e..refs/heads/master:/doc/informe_2da_entrega.lyx diff --git a/doc/informe_2da_entrega.lyx b/doc/informe_2da_entrega.lyx index 165ff48..f62d190 100644 --- 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 - 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 @@ -319,9 +324,75 @@ Especificaciones de \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 (número 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 índice debe almacenar string, estos no son guardados en el árbol, + sino que se reutiliza la estructura EMUFS de la primer entrega para guardar + las cadenas de texto, utilizando para ello una organización de registros + de longitud variable sin bloques, elegida de forma arbitraria. + En la clave del árbol se guardará entonces el ID del registro que contiene + el texto en la estructura mencionada 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 índices con clave repetida (como ser + el selectivo y el exhaustivo). + Para este caso lo que cambia es lo que se almacena en el campo DATO que + acompaña a la clave. + Este DATO contendrá 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 existía una previa, se agrega a dicho + arreglo la nueva posición y luego se guarda. + Si al eliminar todos los datos de una clave este array quedará vació, la + clave es eliminada del árbol. +\layout Standard + +Puede darse el caso (es más, casi todos los índices utilizados en el TP + son de esta manera) que ocurran ambas situaciones descriptas anteriormente, + por lo que para un índice, por ejemplo de presentación de los artículos, + se tenga que acceder a 9 archivos (el árbol 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 identificac +ión no único es muy superior a realizar una búsqueda secuencial sobre todo + el archivo para realizar una consultas. \layout Section Indice B* +\layout Standard + +Lo único que se reescribió fue la función insertar, que aunque es muy similar + al del otro árbol, meter más código en la misma función hacía aún más difícil + 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 @@ -360,18 +431,88 @@ Estas son las dos razones principales por las cuales elegimos tratar el nodo raíz como lo hace el árbol B. \layout Section -Indice B+ Secuencial Indexado +Indice B+ Organización Secuencial Indexada \layout Subsection Decisiones de diseño \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. +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 árbol 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 + +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 -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 están + 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 Árbol B+ se da en su utilización en implementación + ISAM (Indexed Sequential Access Method), en donde se realiza una indexación + 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í pues, recorriendo el Sequence Set del Árbol 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 Árbol B+, era para la indexación 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 únicamente 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 árbol, la cual + es la siguiente: \layout Itemize Nivel @@ -395,8 +536,8 @@ Esta organizaci 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 @@ -444,7 +585,7 @@ n+1 n+1 \series default \emph default - (secuence set) 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 @@ -563,7 +704,7 @@ En el caso que el registro no quepa en el bloque, se deber \layout Standard Al partir el bloque el ancla del bloque original no se modificará, pero - en el bloque nuevo se crea una nueva anlca de bloque, pues una de las claves + en el bloque nuevo se crea una nueva ancla de bloque, pues una de las claves pertenecientes a los registros que contiene, será la menor. \layout Standard @@ -603,7 +744,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 - 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 número 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 encuentran + 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 artículos + 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 número de bloque de datos + donde se encuentra, siendo este el número 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 están en las hojas del B+, y + por ello las recorremos a nivel hojas a través 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 @@ -977,6 +1181,12 @@ Al usar un buffer intermedio, se puede controlar muy bien la cantidad de los resultados. \layout Itemize +Necesita sólo la misma cantidad de espacio libre en disco que la cantidad + de espacio que ocupa el archivo a ordenar. + Todos los métodos analizados necesitaban igual o más cantidad de espacio + libre. +\layout Itemize + El buffer ordenado se implementó con un árbol binario debido a que tiene una buena relación entre velocidad de búsqueda y facilidad de implementación. Al ser el principal determinante de la velocidad los accesos a disco no @@ -996,4 +1206,63 @@ El buffer ordenado se implement de la biblioteca estándar de C poseen un buffer interno, por lo que los accesos a disco probablemente sea muy poco aún cuando se obtienen uno a uno. +\layout Chapter + +Conclusiones +\layout Standard + +Luego de terminar con todo los requerimientos del TP, nos pusimos a tratar + de realizar las comparaciones entre los distintos índices y los tipos de + archivo. + En un primer momento se trató de hacer midiendo tiempos, pero al no poseer + ANSI C funciones de tiempo con suficiente precisión no se pudo obtener + ninguna conclusión relevante. +\layout Standard + +Fue entonces que decidimos hacer una comparativa basada en el uso del programa + modificando los parámetros de carga. + Lo que hicimos fue, para cada archivo (artículos y facturas), probar de + utilizar la clave primaria con los tres tipos de árboles y luego navegar + por los menús del programa realizando operaciones de consulta, búsqueda, + etc. + a fin de ver si se notaba diferencia. + Este último análisis no es del todo objetivo, pero nos dio pié para realizar + una charla por IRC donde discutimos nuestra experiencia con cada tipo de + índice. +\layout Standard + +La conclusión a que llegamos es que para el archivo de artículos, que es + de tipo maestro (pues es un archivo que tiene pocas altas y muchas consultas) + sería preferible utilizar un índice primario de tipo B+ ya que nos permite + acceder de manera ordenada de 2 formas, mediante el índice y tener un acceso + secuencial (ideal para hacer un reporte por ejemplo), y dado que los artículos + permanecerán ordenados los reportes saldrán de la misma manera. +\layout Standard + +En cambio para las facturas sería mejor tener un índice B o B*, ya que es + un archivo de transacciones, donde se suponen que las altas son mayores + que las consultas (es deseable vender mucho). + La ventaja del B y B* es que la inserción es más simple, requiere de un + menor movimiento de registros a la hora de agregar, ya que no es necesario + que en el archivo de datos estos queden ordenados, pudiendo quedar en cualquier + orden físicamente, aún estando en el mismo bloque. + Esta forma de organizarla obviamente no es para nada útil si necesitáramos + por alguna razón acceder secuencialmente por clave primaria, ya que deberíamos + estar saltando por todo el archivo para poder hacerlo, lo que implica muchos + posicionamientos en el disco, operación que resulta muy +\emph on +cara +\emph default +. +\layout Standard + +No hemos encontrado muchas razones para decidirnos por B o B*, y que nuestra + implementación es la misma salvando por el insertar, que en el caso del + B* hace todas las rotaciones posibles antes de hacer un split, cosa que + puede beneficiar ya que la creación de nodos es menor, pero para las cantidades + de datos manejados no vemos que influya mucho. + Antes grandes cantidades de datos puede ser más notoria la diferencia, + ya que al aprovechar mejor el espacio el B* se obtiene un árbol menos profundo + y es necesario leer menos bloques para encontrar una clave (y por lo tanto + son necesarias menos operaciones de disco que son las más lentas). \the_end