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