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 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
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
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
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
\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
\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
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
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
projects / z.facultad / 75.06 / emufs.git / blobdiff