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
\emph default
es la estructura principal que encapsula todas las funciones para el manejo
de un índice.
- Posee punteros a funciones que permite utilizar la misma interface para
+ Posee punteros a funciones que permite utilizar la misma interfaz para
distintas implementaciones de árboles.
\layout Standard
INDICE
\family default
, donde el primero es siempre el índice principal.
+\layout Chapter
+
+Especificaciones de índices
+\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
+\layout Standard
+
+Una de las pocas decisiones que tuvimos que tomar fue la forma de manejar
+ el nodo raíz.
+ Hay dos formas comunes de hacerlo:
+\layout Enumerate
+
+Permitir que el nodo raíz pueda almacenar 2N+1 claves (siendo N el número
+ máximo de claves permitido por nodo).
+\layout Enumerate
+
+Hacer que se comporte como un árbol B.
+\layout Standard
+
+La primera forma garantiza un mejor aprovechamiento del espacio, ya que
+ se sigue haciendo una partición en 3 nodos hijo con 2/3 de los espacios
+ llenos.
+ El problema que encontramos para hacerlo de esa forma fue que usamos un
+ tamaño de nodo fijo de 512 para poder leer un sector completo del disco
+ y ganar algo de velocidad, por lo que para poder mantener este esquema
+ hubiéramos necesitado de 3 bloques de 512 para poder guardar los 2N+1 claves,
+ desperdiciando 512-tamaño_de_clave espacio en el bloque final y haciendo
+ que cualquier ahorro de espacio en los hijos del nodo raíz difícilmente
+ lo compense.
+\layout Standard
+
+Además de esto, el utilizar la segunda forma trae como ventaja la reutilización
+ de código del árbol B, lo que facilita la implementación y el mantenimiento
+ del código.
+\layout Standard
+
+Estas son las dos razones principales por las cuales elegimos tratar el
+ nodo raíz como lo hace el árbol B.
+\layout Section
+
+Indice B+ Organización Secuencial Indexada
+\layout Subsection
+
+Decisiones de diseño
+\layout Standard
+
+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
+
+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
+\layout Itemize
+
+Cantidad de claves
+\layout Itemize
+
+Arreglo de claves
+\layout Itemize
+
+Arreglo de hijos
+\layout Standard
+
+Esta estructura se encuentra en el archivo
+\family typewriter
+indice_bplus.h
+\layout Standard
+
+Esta organización permite, con la ayuda del árbol, mantener el archivo de
+ datos ordenado por la clave principal.
+\layout Standard
+
+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
+
+En el caso de una hoja, dado que cada nodo posee un hijo mas que la cantidad
+ de claves, el hijo que sobra será utilizado como referencia al nodo
+\begin_inset Quotes eld
+\end_inset
+
+hermano
+\begin_inset Quotes erd
+\end_inset
+
+, lo cual constituye el
+\begin_inset Quotes eld
+\end_inset
+
+set secuencial
+\begin_inset Quotes erd
+\end_inset
+
+ del índice.
+ Para un nodo que no sea hoja el hijo será el número de nodo correspondiente
+ según la clave, es decir, para la clave
+\series bold
+\emph on
+n
+\series default
+\emph default
+el hijo
+\series bold
+\emph on
+n
+\series default
+\emph default
+ contiene claves menores y el hijo
+\series bold
+\emph on
+n+1
+\series default
+\emph default
+ contiene las claves mayores.
+ En el caso particular del nivel 1 (index set) el hijo
+\series bold
+\emph on
+n+1
+\series default
+\emph default
+ (sequence set) contiene las claves mayores o iguales ya que el
+\begin_inset Quotes eld
+\end_inset
+
+secuence set
+\begin_inset Quotes erd
+\end_inset
+
+ debe contener todas las claves insertadas, esto produce que exista una
+ repetición de las claves entre el nivel 1 y el 0.
+\layout Standard
+
+En nuestro caso hemos implementado un Secuencial Indexado tipo ISAM (Indexed
+ Sequential Access Method) el cual posee en sus hojas las anclas de cada
+ bloque en el archivo de datos, es decir, solo se guardan en los nodos del
+ árbol la menor de las claves de un bloque del archivo de datos, acompañada
+ cada clave por el numero de bloque al cual pertenece.
+\layout Standard
+
+Hemos adoptado que la cantidad de claves máxima en un nodo del árbol sea
+ una cantidad impar, ya que esto facilita la elección de la clave que será
+ promovida hacia su nodo padre en caso de que se produzca un overflow en
+ el nodo.
+\layout Subsection
+
+Inserción
+\layout Standard
+
+Para realizar una inserción en el archivo de datos se debe realizar una
+ consulta en el árbol, la cual nos indicará el número de bloque donde debemos
+ insertar el nuevo registro.
+\layout Standard
+
+Las consultas se realizan a través de una estructura INDEX_DAT que posee:
+\layout Itemize
+
+Clave
+\layout Itemize
+
+Número de Bloque
+\layout Standard
+
+Esta estructura se encuentra en el archivo
+\family typewriter
+indice_bplus.h
+\layout Standard
+
+El modo de uso es el siguiente:
+\layout Standard
+
+En primer lugar se carga la clave a insertar en el campo Clave, y en el
+ campo Número de Bloque se almacena un número de bloque válido, mas adelante
+ se explica el por qué.
+\layout Standard
+
+Luego se invoca a la función
+\family typewriter
+int emufs_b_plus_get_bloque(INDICE, INDEX_DAT)
+\family default
+la cual recibe como parámetro una estructura de índice y un INDEX_DAT para
+ realizar la consulta.
+\layout Standard
+
+Esta función recorre recursivamente el árbol y busca una clave mayor inmediata
+ a la enviada, siempre culminando la búsqueda en una hoja.
+ Al encontrar la clave mayor inmediata, el resultado de la búsqueda será
+ la clave anterior en el nodo, pues cada clave en el nodo es un ancla de
+ bloque de datos, de esta manera la clave anterior será menor a la clave
+ enviada, pues las claves en las hojas están ordenadas.
+
+\layout Standard
+
+En este paso pueden suceder dos cosas:
+\layout Enumerate
+
+Que exista una clave menor a la enviada.
+\layout Enumerate
+
+Que la clave enviada sea menor a todas las claves del árbol.
+\layout Standard
+
+En el primer caso, se ha encontrado la clave y se carga la estructura con
+ el hijo de esa clave, que será el número de bloque donde debe insertarse
+ el nuevo registro (por el cual se realizó la consulta), sobreescribiendo
+ el valor que almacenaba al ingresar, y la función retornará código 0 que
+ indica que se ha encontrado un bloque donde insertar.
+\layout Standard
+
+En el segundo caso, puede darse que la clave enviada sea menor a todas las
+ claves del árbol, por lo cual no es posible encontrar un ancla de bloque
+ para esa clave.
+ Aquí la función retornará código -1 lo cual indica que no se ha encontrado
+ un bloque donde insertar el registro nuevo, y es por esto que la estructura
+ debe inicializarse con un número de bloque válido antes de realizarse la
+ consulta.De esta manera el árbol indica donde debe insertarse un nuevo registro
+ en el archivo de datos.
+\layout Standard
+
+Otro detalle de la inserción es que cuando el árbol indica donde debe insertarse
+ un registro pueden pasar dos cosas nuevamente:
+\layout Enumerate
+
+Que el registro quepa en el bloque.
+\layout Enumerate
+
+Que el registro no quepa en el bloque.
+\layout Standard
+
+El primer caso es trivial y el registro se insertará sin problemas en el
+ bloque indicado.
+\layout Standard
+
+En el caso que el registro no quepa en el bloque, se deberán separar los
+ registros del bloque en 2 bloques, en original y uno nuevo, cada uno con
+ la mitad (aproximadamente) de los registros.
+
+\layout Standard
+
+Al partir el bloque el ancla del bloque original no se modificará, pero
+ 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
+
+Antes de actualizar el árbol con el ancla nueva, habrá que discriminar en
+ qué bloque se debe insertar el registro nuevo.
+ Para ello se compara la menor de las claves del nuevo bloque con la clave
+ del registro, si la clave del registro es menor que el ancla del nuevo
+ bloque, este debe ir en el bloque original, y se inserta ordenado en él
+ y se le informa al árbol que actualice (inserte) una nueva clave correspondient
+e al bloque nuevo, sino se inserta en el bloque nuevo de forma ordenada
+ y en este caso cabe la posibilidad de que el nuevo registro posea la clave
+ mas pequeña de todas en el bloque, por ello se lo inserta ordenadamente
+ con ayuda de la función
+\family typewriter
+ CLAVE grabar_ordenado_en_bloque(EMUFS *emu, void *ptr, EMUFS_REG_SIZE size,
+ void *bloque, int num_bloque, EMUFS_FREE fs, int *err)
+\family default
+la cual inserta el registro ordenado por CLAVE y devuelve la menor de las
+ claves del bloque, que se usará para informarle al árbol que inserte una
+ clave nueva junto con el número de bloque, para indexar este bloque.
+\layout Subsection
+
+Eliminación
+\layout Standard
+
+El proceso de eliminación es bastante similar al de inserción en el sentido
+ que también hay que realizar una consulta en el árbol para obtener el número
+ de bloque al que pertenece una clave.
+ Una vez conocido este número se levanta el bloque correspondiente y se
+ busca secuencialmente el registro que se debe eliminar.
+\layout Standard
+
+Si el registro a eliminar fuera el primero del bloque, habrá que modificar
+ el ancla de bloque en el árbol con el ancla que corresponda a la clave
+ del nuevo menor registro, y si el que se elimina fuera el único registro
+ en el bloque habrá que eliminar la clave del árbol.
+\layout Standard
+
+En cualquier otro caso, solo se eliminará el registro correspondiente y
+ 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
+\layout Section
+
+Descripción del algoritmo
+\layout Standard
+
+Luego de buscar varias alternativas sobre algoritmos de ordenamiento externo,
+ se optó por el siguiente (que resultó una mezcla de las alternativas analizadas
+):
+\layout Enumerate
+
+Tomar uno a uno los registros del archivo a ordenar e
+\emph on
+inyectarlos
+\emph default
+ en un buffer ordenado hasta llenar el buffer.
+\layout Enumerate
+
+Quitar el menor de los valores (
+\emph on
+inyectando
+\emph default
+ uno nuevo desde el archivo a ordenar) e insertarlo en un archivo temporal.
+\layout Enumerate
+
+Quitar del buffer el mínimo valor mayor al último insertado en el archivo
+ temporal (
+\emph on
+inyectando
+\emph default
+ nuevamente un registro obtenido del archivo a ordenar) y se lo inserta
+ en el archivo temporal.
+ De esta forma quedan ordenados los registros en el archivo temporal.
+\layout Enumerate
+
+Repetir el paso 3 hasta que se vacíe el buffer o hasta que no haya ningún
+ valor mayor al último insertado en el archivo temporal.
+ Cuando esto suceda se crea un nuevo archivo temporal volviendo al paso
+ 2.
+\layout Standard
+
+En este punto ya tenemos el buffer vacío y todos los valores del archivo
+ a ordenar repartidos en 1 o más archivos temporales ordenados, sólo queda
+ unir los archivos para volver a un sólo archivo completo y ordenado.
+ El procedimiento es simple:
+\layout Enumerate
+
+Obtener el mínimo valor de los archivos temporales e insertarlo en el archivo
+ ordenado de salida.
+\layout Enumerate
+
+Repetir 1 hasta agotar los registros de todos los archivos temporales.
+\layout Standard
+
+Debe quedar claro que los archivos temporales se comportan como una cola.
+ Es decir que al obtener un registro de un archivo temporal se obtiene el
+ primer registro que se haya insertado (el mínimo por la forma en la que
+ fueron insertados).
+\layout Subsection
+
+Ejemplo
+\layout Standard
+
+A continuación se presenta un ejemplo para una más fácil comprensión del
+ algoritmo.
+\layout Standard
+
+Supongamos que queremos ordenar un archivo con registros de números enteros
+ (el archivo se lee de izquierda a derecha): 9 6 34 2 8 3 12 43 23 4 19
+ 21 87 1 16 36 42 65
+\layout Standard
+
+Supongamos que disponemos de un buffer capaz de almacenar 3 registros.
+\layout Paragraph
+
+Se llena el buffer ordenado
+\layout Standard
+
+Se lee 9 del archivo original y se lo inserta en el buffer ordenado.
+ Buffer: 9
+\layout Standard
+
+Se lee 6 del archivo original y se lo inserta en el buffer ordenado.
+ Buffer: 6 9
+\layout Standard
+
+Se lee 34 del archivo original y se lo inserta en el buffer ordenado.
+ Buffer: 6 9 34
+\layout Paragraph
+
+Se crea el archivo temporal ordenado 1
+\layout Standard
+
+Se lee el mínimo valor del buffer (6), se lo inserta en el archivo temporal
+ y se carga un nuevo valor del archivo original al buffer (2).
+ Buffer: 2 9 34.
+ Archivo1: 6
+\layout Standard
+
+Se lee el mínimo valor del buffer mayor al insertado anteriormente (9),
+ se lo inserta en el archivo temporal y se carga un nuevo valor del archivo
+ original al buffer (8).
+ Buffer: 2 8 34.
+ Archivo1: 6 9
+\layout Standard
+
+Se lee el mínimo valor del buffer mayor al insertado anteriormente (34),
+ se lo inserta en el archivo temporal y se carga un nuevo valor del archivo
+ original al buffer (3).
+ Buffer: 2 3 8.
+ Archivo1: 6 9 34
+\layout Standard
+
+No hay más valores en el buffer mayores al último insertado (34), fin del
+ Archivo1.
+\layout Paragraph
+
+Se crea el archivo temporal ordenado 2
+\layout Standard
+
+Se lee el mínimo valor del buffer (2), se lo inserta en el archivo temporal
+ y se carga un nuevo valor del archivo original al buffer (12).
+ Buffer: 3 8 12.
+ Archivo2: 2
+\layout Standard
+
+Se lee el mínimo valor del buffer mayor al insertado anteriormente (3),
+ se lo inserta en el archivo temporal y se carga un nuevo valor del archivo
+ original al buffer (43).
+ Buffer: 8 12 43.
+ Archivo2: 2 3
+\layout Standard
+
+Se lee el mínimo valor del buffer mayor al insertado anteriormente (8),
+ se lo inserta en el archivo temporal y se carga un nuevo valor del archivo
+ original al buffer (23).
+ Buffer: 12 23 43.
+ Archivo2: 2 3 8
+\layout Standard
+
+Se lee el mínimo valor del buffer mayor al insertado anteriormente (12),
+ se lo inserta en el archivo temporal y se carga un nuevo valor del archivo
+ original al buffer (4).
+ Buffer: 4 23 43.
+ Archivo2: 2 3 8 12
+\layout Standard
+
+Se lee el mínimo valor del buffer mayor al insertado anteriormente (23),
+ se lo inserta en el archivo temporal y se carga un nuevo valor del archivo
+ original al buffer (19).
+ Buffer: 4 19 43.
+ Archivo2: 2 3 8 12 23
+\layout Standard
+
+Se lee el mínimo valor del buffer mayor al insertado anteriormente (43),
+ se lo inserta en el archivo temporal y se carga un nuevo valor del archivo
+ original al buffer (21).
+ Buffer: 4 19 21.
+ Archivo2: 2 3 8 12 23 43
+\layout Standard
+
+No hay más valores en el buffer mayores al último insertado (43), fin del
+ Archivo2.
+\layout Paragraph
+
+Se crea el archivo temporal ordenado 3
+\layout Standard
+
+Se repite el proceso anterior.
+ Buffer: 1 16 36.
+ Archivo3: 4 19 21 87
+\layout Paragraph
+
+Se crea el archivo temporal ordenado 4
+\layout Standard
+
+Se repite el proceso anterior.
+ Buffer: .
+ Archivo4: 1 16 36 42 65
+\layout Paragraph
+
+Se mezclan los archivos temporales ordenados obteniendo un archivo completo
+ ordenado
+\layout Standard
+
+Se obtiene el menor valor de los archivos temporales ordenados (sólo tenemos
+ que elegir entre el primer valor de cada uno).
+\layout Standard
+
+Archivo1: 6 9 34.
+ Archivo2: 2 3 8 12 23 43.
+ Archivo3: 4 19 21 87.
+ Archivo4: 1 16 36 42 65
+\layout Standard
+
+Sólo debo comparar y obtener el menor entre 6, 2, 4, y 1.
+ Obtengo el 1, lo saco del archivo temporal y lo agrego al de salida:
+\layout Standard
+
+Archivo1: 6 9 34.
+ Archivo2: 2 3 8 12 23 43.
+ Archivo3: 4 19 21 87.
+ Archivo4: 16 36 42 65 Salida: 1
+\layout Standard
+
+Repito hasta que no hayan más valores en los archivos temporales:
+\layout Standard
+
+Archivo1: 6 9 34.
+ Archivo2: 3 8 12 23 43.
+ Archivo3: 4 19 21 87.
+ Archivo4: 16 36 42 65.
+ Salida: 1 2
+\layout Standard
+
+Archivo1: 6 9 34.
+ Archivo2: 8 12 23 43.
+ Archivo3: 4 19 21 87.
+ Archivo4: 16 36 42 65.
+ Salida: 1 2 3
+\layout Standard
+
+Archivo1: 6 9 34.
+ Archivo2: 8 12 23 43.
+ Archivo3: 19 21 87.
+ Archivo4: 16 36 42 65.
+ Salida: 1 2 3 4
+\layout Standard
+
+Archivo1: 6 9 34.
+ Archivo2: 8 12 23 43.
+ Archivo3: 19 21 87.
+ Archivo4: 16 36 42 65.
+ Salida: 1 2 3 4
+\layout Standard
+
+Archivo1: 9 34.
+ Archivo2: 8 12 23 43.
+ Archivo3: 19 21 87.
+ Archivo4: 16 36 42 65.
+ Salida: 1 2 3 4 6
+\layout Standard
+
+Archivo1: 9 34.
+ Archivo2: 12 23 43.
+ Archivo3: 19 21 87.
+ Archivo4: 16 36 42 65.
+ Salida: 1 2 3 4 6 8
+\layout Standard
+
+Archivo1: 34.
+ Archivo2: 12 23 43.
+ Archivo3: 19 21 87.
+ Archivo4: 16 36 42 65.
+ Salida: 1 2 3 4 6 8 9
+\layout Standard
+
+Archivo1: 34.
+ Archivo2: 23 43.
+ Archivo3: 19 21 87.
+ Archivo4: 16 36 42 65.
+ Salida: 1 2 3 4 6 8 9 12
+\layout Standard
+
+Archivo1: 34.
+ Archivo2: 23 43.
+ Archivo3: 19 21 87.
+ Archivo4: 36 42 65.
+ Salida: 1 2 3 4 6 8 9 12 16
+\layout Standard
+
+Archivo1: 34.
+ Archivo2: 23 43.
+ Archivo3: 21 87.
+ Archivo4: 36 42 65.
+ Salida: 1 2 3 4 6 8 9 12 16 19
+\layout Standard
+
+Archivo1: 34.
+ Archivo2: 23 43.
+ Archivo3: 87.
+ Archivo4: 36 42 65.
+ Salida: 1 2 3 4 6 8 9 12 16 19 21
+\layout Standard
+
+Archivo1: 34.
+ Archivo2: 43.
+ Archivo3: 87.
+ Archivo4: 36 42 65.
+ Salida: 1 2 3 4 6 8 9 12 16 19 21 23
+\layout Standard
+
+Archivo1:.
+ Archivo2: 43.
+ Archivo3: 87.
+ Archivo4: 36 42 65.
+ Salida: 1 2 3 4 6 8 9 12 16 19 21 23 34
+\layout Standard
+
+Archivo1:.
+ Archivo2: 43.
+ Archivo3: 87.
+ Archivo4: 42 65.
+ Salida: 1 2 3 4 6 8 9 12 16 19 21 23 34 36
+\layout Standard
+
+Archivo1:.
+ Archivo2: 43.
+ Archivo3: 87.
+ Archivo4: 65.
+ Salida: 1 2 3 4 6 8 9 12 16 19 21 23 34 36 42
+\layout Standard
+
+Archivo1:.
+ Archivo2:.
+ Archivo3: 87.
+ Archivo4: 65.
+ Salida: 1 2 3 4 6 8 9 12 16 19 21 23 34 36 42 43
+\layout Standard
+
+Archivo1:.
+ Archivo2:.
+ Archivo3: 87.
+ Archivo4:.
+ Salida: 1 2 3 4 6 8 9 12 16 19 21 23 34 36 42 43 65
+\layout Standard
+
+Archivo1:.
+ Archivo2:.
+ Archivo3:.
+ Archivo4:.
+ Salida: 1 2 3 4 6 8 9 12 16 19 21 23 34 36 42 43 65 87
+\layout Paragraph
+
+Fin
+\layout Standard
+
+Finalmente, tengo en el archivo de salida el archivo original ordenado.
+\layout Section
+
+Alcance
+\layout Standard
+
+El algoritmo de ordenamiento es completamente genérico, ya que recibe un
+ puntero void como registro, su tamaño (para poder manipularlo sin conocer
+ su tipo) y una función de comparación, para poder comparar dos registros
+ (sin saber su tipo) a través de una relación de orden (descripta por dicha
+ función).
+\layout Section
+
+Decisiones de diseño.
+\layout Standard
+
+El algoritmo se eligió en base a una serie de razones y cuenta con una serie
+ de ventajas y desventajas.
+\layout Itemize
+
+El algoritmo es simple, tanto teóricamente como para implementar.
+\layout Itemize
+
+Tiene la desventaja de que puede llegar a usar muchos archivos temporales
+ y todos abiertos al mismo tiempo, pero considerando que el sistema operativo
+ en el que se utiliza suele manejar bien grandes cantidades de archivos
+ no es una desventaja importante.
+\layout Itemize
+
+Al usar un buffer intermedio, se puede controlar muy bien la cantidad de
+ memoria que utiliza y experimentar con distintos valores para analizar
+ 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
+ se creyó necesario buscar una alternativa más rápida para mantener el buffer
+ ordenado en memoria, ya que no cambiaría de forma notable el tiempo total
+ del algoritmo.
+ Otras posibilidades hubieran sido cargar todo el buffer en memoria y ordenarlo
+ posteriormente (dependiendo del algoritmo de ordenamiento a utilizar puede
+ ser más o menos rápido que el árbol y más o menos complicado de implementar)
+ o hacer una búsqueda secuencial sobre un buffer desordenado (es más fácil
+ de implementar pero claramente más lento).
+ Una posible ventaja notable de leer el buffer primero y luego ordenarlo
+ en memoria es que se necesita un sólo acceso al disco para llenar el buffer,
+ mientras que al obtener uno a uno los valores puede generar muchos accesos
+ a disco.
+ Esto no debería ser muy notable ya que las funciones de acceso a archivos
+ 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