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 (para una justificación más detallada
- ver FIXME: REFERENCIA A EXPLICACION DE B+)3.
+ 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
\family typewriter
INDICE_DATO
\family default
-: usado para representar el conjunto de un ID más la ubicación del dato
- asociado.
+: usado para representar el conjunto de un ID más su dato.
\layout Itemize
\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
Integración con
\family typewriter
EMUFS
+\family default
+.
\layout Standard
Para integrar la utilización de índices a
fueron necesarios los siguientes cambios:
\layout Paragraph
-Nuevos tipos de archivo
+Nuevos tipos de archivo.
\layout Standard
Se incluyen dos tipos de archivo nuevos T4 y T5, que representan, respectivament
ya que al saber que es T4 o T5 siempre se inserta de forma ordenada.
\layout Paragraph
-Puntero a un arreglo de índices
+Puntero a un arreglo de índices.
\layout Standard
Se agrega a la estructura
, donde el primero es siempre el índice principal.
\layout Chapter
-Implementación
+Especificaciones de índices
\layout Section
-Árbol B
+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 (numero 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 indice debe almacenar string, estos no son guardados en el arbol,
+ 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
+ de longitud variable sin bloques, elegida de forma arbitraria.
+ En la clave del arbol se guardará entonces el ID del registro que contiene
+ el texto en la estructura mensionada 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 indices con clave repetida (como ser
+ el selectivo y el exahustivo).
+ 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
+ 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
+ clave es eliminada del arbol.
+\layout Standard
+
+Puede darse el caso (es mas, casi todos los indices utilizados en el TP
+ son de esta manera) que ocurran ambas situaciones descriptas anteriormente,
+ por lo que para un indice, por ejemplo de presentacion de los articulos,
+ se tenga que acceder a 9 archivos (el arbol 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 identifacac
+ion no unico es muy superior a realizar una busqueda secuencial sobre todo
+ el archivo para realizar una consultas.
\layout Section
-Árbol B*
+Indice B*
+\layout Standard
+
+Para la implantación de los árboles B* se tomo la desición de tratar a la
+ raiz como si fuera un árbol B en lugar de tomar una raiz de 2*tam_bloque
+ para reutilizar el código ya hecho para el árbol B y todas las funciones
+ anexas.
+\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
+ 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
-Árbol B+
+Indice B+ Organizacion 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 arbol 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 estan
+ 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 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
+\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
+ 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 anlca 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 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
+\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
-Ordenamiento externo
+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
+
+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.
\the_end
projects / z.facultad / 75.06 / emufs.git / blobdiff