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+ Organizacion Secuencial Indexada
+Indice B+ Organización Secuencial Indexada
\layout Subsection
Decisiones de diseño
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
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
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
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 arbol, la cual
+ B+, damos una breve reseña de la estructura de un nodo del árbol, la cual
es la siguiente:
\layout Itemize
\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
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
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.
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
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.
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