agrego b y B*

[z.facultad/75.06/emufs.git] / doc / informe_2da_entrega.lyx

#LyX 1.3 created this file. For more info see http://www.lyx.org/
\lyxformat 221
\textclass book
\language spanish
\inputencoding auto
\fontscheme palatino
\graphics default
\paperfontsize default
\spacing single 
\papersize a4paper
\paperpackage widemarginsa4
\use_geometry 0
\use_amsmath 0
\use_natbib 0
\use_numerical_citations 0
\paperorientation portrait
\secnumdepth 3
\tocdepth 3
\paragraph_separation indent
\defskip medskip
\quotes_language english
\quotes_times 2
\papercolumns 1
\papersides 1
\paperpagestyle default

\layout Title

Organización de Datos (75.06)
\newline 
Trabajo Práctico
\newline 
E
\begin_inset Formula $\mu$
\end_inset 

FS
\layout Author


\series bold 
Grupo 11
\series default 

\newline 
Nicolás Dimov (77624)
\newline 
Alan Kennedy (78907)
\newline 
Leandro Lucarella (77891)
\newline 
Ricardo Markiewicz (78226)
\layout Date

Segunda Entrega, 31 de Mayo de 2004
\layout Standard


\begin_inset LatexCommand \tableofcontents{}

\end_inset 


\layout Chapter

Introducción
\layout Standard

En esta entrega el trabajo estuvo concentrado en el manejo de índices para
 los tipos de archivos implementados en la primer entrega.
 Los índices se implementaron con:
\layout Enumerate

Árbol B
\layout Enumerate

Árbol B*
\layout Enumerate

Árbol B+
\layout Standard

Además de esto, se pide 3 funciones distintas para estos índices:
\layout Enumerate

Principal
\layout Enumerate

Selectivo
\layout Enumerate

Exhaustivo
\layout Standard

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 (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
 tiene un índice, se implementó un ordenamiento externo.
\layout Standard

A continuación se presenta una descripción un poco más detallada sobre todas
 herramientas utilizadas para resolver el trabajo práctico.
\layout Section

Documentación de la API
\layout Standard

Para obtener una documentación de la API más completa, se incluye en formato
 HTML en el CD-ROM la documentación generado con Doxygen.
 Esta documentación se encuentra en el directorio 
\family typewriter 
doc/api/html/index.html
\family default 
.
\layout Chapter

Estructura común
\layout Section

Tipos
\layout Standard

Se detallan a continuación los tipos de datos definidos y utilizados en
 las distintas implementaciones que conforman nuestro sistema, siendo el
 más importante de ellos en esta entrega, la estructura 
\family typewriter 
INDICE
\family default 
 que actúa como interfaz común para el manejo de cualquier tipo de índice
 (no importa que tipo de organización física ni de que forma esté implementado,
 esta estructura proveerá una interfaz abstracta para su manejo).
\layout Subsection

Tipos Comunes
\layout Standard

Se agregaron varios tipos comunes nuevos en esta entrega, en su mayoría
 relacionados a los índices.
 Estos tipos son brevemente descriptos a continuación y pueden ser hallados
 en el archivo 
\family typewriter 
indices.h
\family default 
:
\layout Itemize


\family typewriter 
INDICE_DATO
\family default 
: usado para representar el conjunto de un ID más su dato.
\layout Itemize


\family typewriter 
INDICE_TIPO
\family default 
: indica el tipo de índice (B, B* o B+).
\layout Itemize


\family typewriter 
INDICE_FUNCION
\family default 
: indica la función que cumple el índice (principal, selectivo o exhaustivo).
\layout Itemize


\family typewriter 
INDICE_TIPO_DATO
\family default 
: indica el tipo de dato que se usa como clave.
\layout Itemize


\family typewriter 
CLAVE
\family default 
: representa una clave de un índice.
\layout Subsection

INDICE
\layout Standard


\family typewriter 
INDICE
\family default 
\emph on 
 
\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 interfaz para
 distintas implementaciones de árboles.
 
\layout Standard

Su declaración puede ser observada en el archivo 
\family typewriter 
indices.h
\family default 
\series bold 
 
\series default 
y cuenta con la siguiente información:
\layout Itemize

Tipo de índice.
\layout Itemize

Tipo de dato que maneja.
\layout Itemize

Función del índice.
\layout Itemize

Información sobre el desplazamiento para ubicar el dato dentro de la estructura
 a indexar (para poder tener una implementación genérica que sirva para
 cualquier estructura).
\layout Itemize

Información sobre archivos auxiliares para almacenar cadenas de texto y
 otras estructuras que eventualmente requiera un índice.
\layout Itemize

Punteros a funciones para:
\begin_deeper 
\layout Itemize

Agregar entrada.
\layout Itemize

Borrar entrada.
\layout Itemize

Verificar la existencia de una entrada.
\layout Itemize

Buscar entradas.
\layout Itemize

Obtener clave menor o mayor del índice.
\layout Itemize

Obtener siguiente clave (para recorrido secuencial).
\end_deeper 
\layout Standard

Esta estructura define los valores de sus punteros según el tipo de implementaci
ón que se desee manejar y esto se realiza a través de la API 
\family typewriter 
emufs_indice
\family default 
, implementada en 
\family typewriter 
indices.h
\family default 
.
 Esta API posee funciones para crear y destruir índices, agregarlos y quitarlos
 de una estructura 
\family typewriter 
EMUFS
\family default 
, comparar claves y otras, necesarias para la correcta y completa utilización
 de los índices a través de la interfaz de 
\family typewriter 
EMUFS
\family default 
 descripta en la entrega anterior.
\layout Subsubsection

Integración con 
\family typewriter 
EMUFS
\family default 
.
\layout Standard

Para integrar la utilización de índices a 
\family typewriter 
EMUFS
\family default 
 fueron necesarios los siguientes cambios:
\layout Paragraph

Nuevos tipos de archivo.
\layout Standard

Se incluyen dos tipos de archivo nuevos T4 y T5, que representan, respectivament
e, un archivo T1 (registros variables, bloques fijos) y un archivo T3 (registros
 y bloques fijos), ambos organizados como un set secuencial indexado.
 De esta manera se conserva la interfaz de 
\family typewriter 
EMUFS
\family default 
 (los punteros a funciones) incluso cuando se debe insertar de forma ordenada,
 ya que al saber que es T4 o T5 siempre se inserta de forma ordenada.
\layout Paragraph

Puntero a un arreglo de índices.
\layout Standard

Se agrega a la estructura 
\family typewriter 
EMUFS
\family default 
 un puntero a un arreglo de 
\family typewriter 
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 (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

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

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

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