Se agrega doc de external sort y algo de 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.
\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 interface 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 Section

Indice B*
\layout Subsection

Desiciones de diseño
\layout Standard

Una de las pocas desiciones 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
 hubieramos 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

Ademas 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+ Secuencial Indexado
\layout Standard

Se ha implementado un índice secuencial indexado utilizando un árbol B+,
 el cual tiene la particularidad de tener en sus hojas todas las claves
 que se han insertado.
\layout Standard

La estructura de un nodo del árbol 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, 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 el hijo 
\series bold 
\emph on 
n+1
\series default 
\emph default 
 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
 arbol 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 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 estan 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.
\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 órden (descripta por dicha
 función).
\layout Section

Desiciones 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 creyo necesario buscar una alternativa más rapida 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