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
\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
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
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
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.
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
\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