\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
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
projects / z.facultad / 75.06 / emufs.git / commitdiff