X-Git-Url: https://git.llucax.com/z.facultad/75.06/emufs.git/blobdiff_plain/7ccae609792550a7d81d2496742def35f003bf26..refs/heads/master:/doc/informe_2da_entrega.lyx diff --git a/doc/informe_2da_entrega.lyx b/doc/informe_2da_entrega.lyx index da86c5c..f62d190 100644 --- a/doc/informe_2da_entrega.lyx +++ b/doc/informe_2da_entrega.lyx @@ -346,34 +346,34 @@ Existen 2 casos particulares para lo que contiene la clave y el dato. 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, utilizano para ello una organización de registros + 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 arbol se guardará entonces el ID del registro que contiene + 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 exahustivo). + 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 contendra el ID de un registro que se guarda nuevamente en un + 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 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 +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 arbol B, 4 para los string, 4 para + 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 @@ -385,7 +385,7 @@ 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 codigo en la misma función hacía aún más dificil + 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 @@ -431,7 +431,7 @@ 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+ Organizacion Secuencial Indexada +Indice B+ Organización Secuencial Indexada \layout Subsection Decisiones de diseño @@ -442,7 +442,7 @@ Para la implementaci para implementaciones de esta índole. \layout Standard -Como particularidad el arbol B+, poseerá en sus hojas todas las claves que +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 @@ -462,7 +462,7 @@ En torno a esta distinci 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 + 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 @@ -481,8 +481,8 @@ Sequence Set. 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 +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. @@ -493,16 +493,16 @@ Esta aplicaci 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 + 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 Arbol B+, era para la indexacion parcial de claves primarias, y que + 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 unicamente para el índice primario, y utilizar + ayudantes, decidimos utilizarlo únicamente para el índice primario, y utilizar el B y B* para los restantes índices y/o el primario. \layout Subsection @@ -511,7 +511,7 @@ 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 + B+, damos una breve reseña de la estructura de un nodo del árbol, la cual es la siguiente: \layout Itemize @@ -704,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 @@ -759,9 +759,9 @@ El proceso de b 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. + 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 @@ -775,7 +775,7 @@ 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 + 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. @@ -783,15 +783,15 @@ icas, los tiempos de acceso para una recorrida secuencial de registros. 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 + 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 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. + 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 @@ -803,8 +803,8 @@ 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 +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. @@ -1181,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 @@ -1200,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