X-Git-Url: https://git.llucax.com/z.facultad/75.06/emufs.git/blobdiff_plain/c869e2f4e8c17209c8afc4cd60f72ad03f6042e8..939371a10ca8ccd1811505ec58865046aba4d7f2:/doc/informe_2da_entrega.lyx diff --git a/doc/informe_2da_entrega.lyx b/doc/informe_2da_entrega.lyx index 1e9f612..7c71ab5 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 @@ -382,10 +387,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 +405,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 @@ -480,7 +519,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 @@ -639,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 - 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