From: Leandro Lucarella Date: Mon, 31 May 2004 08:26:57 +0000 (+0000) Subject: Se agrega doc de external sort y algo de B*. X-Git-Tag: svn_import_r684~17 X-Git-Url: https://git.llucax.com/z.facultad/75.06/emufs.git/commitdiff_plain/0832f2f1d247cabaec3d2d4cffff93672b2cc304 Se agrega doc de external sort y algo de B*. --- diff --git a/doc/informe_2da_entrega.lyx b/doc/informe_2da_entrega.lyx index 2d6cf6d..506a3df 100644 --- a/doc/informe_2da_entrega.lyx +++ b/doc/informe_2da_entrega.lyx @@ -322,6 +322,42 @@ 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 @@ -494,4 +530,396 @@ En el segundo caso, puede darse que la clave enviada sea menor a todas las 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