X-Git-Url: https://git.llucax.com/z.facultad/75.06/emufs.git/blobdiff_plain/35461b28428de0b91e4e2151d86ead1b1c7feb3b..36612600baec1e24eee239cf773bba048c5d6453:/doc/informe_2da_entrega.lyx diff --git a/doc/informe_2da_entrega.lyx b/doc/informe_2da_entrega.lyx index 65f4e09..934ed6e 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,81 @@ 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 (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 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 @@ -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. - 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 - 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 @@ -400,6 +477,40 @@ Como resultado concreto de este comportamiento (teniendo en cuenta tambi 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 @@ -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 - 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 @@ -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 - 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ó @@ -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 -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