1 #LyX 1.3 created this file. For more info see http://www.lyx.org/
11 \paperpackage widemarginsa4
15 \use_numerical_citations 0
16 \paperorientation portrait
19 \paragraph_separation indent
21 \quotes_language english
25 \paperpagestyle default
29 Organización de Datos (75.06)
34 \begin_inset Formula $\mu$
50 Leandro Lucarella (77891)
52 Ricardo Markiewicz (78226)
55 Segunda Entrega, 31 de Mayo de 2004
59 \begin_inset LatexCommand \tableofcontents{}
69 En esta entrega el trabajo estuvo concentrado en el manejo de índices para
70 los tipos de archivos implementados en la primer entrega.
71 Los índices se implementaron con:
83 Además de esto, se pide 3 funciones distintas para estos índices:
95 Con la autorización de los ayudantes de la cátedra decidimos que el árbol
96 B+ sólo pueda ser utilizado para índices principal ya que de otra manera
97 no tiene sentido el set secuencial.
100 Finalmente, para obtener listados basados en campos de los cuales no se
101 tiene un índice, se implementó un ordenamiento externo.
104 A continuación se presenta una descripción un poco más detallada sobre todas
105 herramientas utilizadas para resolver el trabajo práctico.
108 Documentación de la API
111 Para obtener una documentación de la API más completa, se incluye en formato
112 HTML en el CD-ROM la documentación generado con Doxygen.
113 Esta documentación se encuentra en el directorio
115 doc/api/html/index.html
126 Se detallan a continuación los tipos de datos definidos y utilizados en
127 las distintas implementaciones que conforman nuestro sistema, siendo el
128 más importante de ellos en esta entrega, la estructura
132 que actúa como interfaz común para el manejo de cualquier tipo de índice
133 (no importa que tipo de organización física ni de que forma esté implementado,
134 esta estructura proveerá una interfaz abstracta para su manejo).
140 Se agregaron varios tipos comunes nuevos en esta entrega, en su mayoría
141 relacionados a los índices.
142 Estos tipos son brevemente descriptos a continuación y pueden ser hallados
154 : usado para representar el conjunto de un ID más su dato.
161 : indica el tipo de índice (B, B* o B+).
168 : indica la función que cumple el índice (principal, selectivo o exhaustivo).
175 : indica el tipo de dato que se usa como clave.
182 : representa una clave de un índice.
195 es la estructura principal que encapsula todas las funciones para el manejo
197 Posee punteros a funciones que permite utilizar la misma interfaz para
198 distintas implementaciones de árboles.
202 Su declaración puede ser observada en el archivo
209 y cuenta con la siguiente información:
215 Tipo de dato que maneja.
221 Información sobre el desplazamiento para ubicar el dato dentro de la estructura
222 a indexar (para poder tener una implementación genérica que sirva para
223 cualquier estructura).
226 Información sobre archivos auxiliares para almacenar cadenas de texto y
227 otras estructuras que eventualmente requiera un índice.
230 Punteros a funciones para:
240 Verificar la existencia de una entrada.
246 Obtener clave menor o mayor del índice.
249 Obtener siguiente clave (para recorrido secuencial).
253 Esta estructura define los valores de sus punteros según el tipo de implementaci
254 ón que se desee manejar y esto se realiza a través de la API
263 Esta API posee funciones para crear y destruir índices, agregarlos y quitarlos
268 , comparar claves y otras, necesarias para la correcta y completa utilización
269 de los índices a través de la interfaz de
273 descripta en la entrega anterior.
274 \layout Subsubsection
283 Para integrar la utilización de índices a
287 fueron necesarios los siguientes cambios:
290 Nuevos tipos de archivo.
293 Se incluyen dos tipos de archivo nuevos T4 y T5, que representan, respectivament
294 e, un archivo T1 (registros variables, bloques fijos) y un archivo T3 (registros
295 y bloques fijos), ambos organizados como un set secuencial indexado.
296 De esta manera se conserva la interfaz de
300 (los punteros a funciones) incluso cuando se debe insertar de forma ordenada,
301 ya que al saber que es T4 o T5 siempre se inserta de forma ordenada.
304 Puntero a un arreglo de índices.
307 Se agrega a la estructura
311 un puntero a un arreglo de
315 , donde el primero es siempre el índice principal.
318 Especificaciones de índices
330 Una de las pocas decisiones que tuvimos que tomar fue la forma de manejar
332 Hay dos formas comunes de hacerlo:
335 Permitir que el nodo raíz pueda almacenar 2N+1 claves (siendo N el número
336 máximo de claves permitido por nodo).
339 Hacer que se comporte como un árbol B.
342 La primera forma garantiza un mejor aprovechamiento del espacio, ya que
343 se sigue haciendo una partición en 3 nodos hijo con 2/3 de los espacios
345 El problema que encontramos para hacerlo de esa forma fue que usamos un
346 tamaño de nodo fijo de 512 para poder leer un sector completo del disco
347 y ganar algo de velocidad, por lo que para poder mantener este esquema
348 hubiéramos necesitado de 3 bloques de 512 para poder guardar los 2N+1 claves,
349 desperdiciando 512-tamaño_de_clave espacio en el bloque final y haciendo
350 que cualquier ahorro de espacio en los hijos del nodo raíz difícilmente
354 Además de esto, el utilizar la segunda forma trae como ventaja la reutilización
355 de código del árbol B, lo que facilita la implementación y el mantenimiento
359 Estas son las dos razones principales por las cuales elegimos tratar el
360 nodo raíz como lo hace el árbol B.
363 Indice B+ Secuencial Indexado
369 Se ha implementado un índice secuencial indexado utilizando un árbol B+,
370 el cual tiene la particularidad de tener en sus hojas todas las claves
371 que se han insertado.
374 La estructura de un nodo del árbol es la siguiente:
389 Esta estructura se encuentra en el archivo
394 Esta organización permite, con la ayuda del árbol, mantener el archivo de
395 datos ordenado por la clave principal.
398 Para lograr esto, el árbol nos indicará donde (en qué bloque) debe insertarse
400 (ver 3.3.1 Inserción)
403 En el caso de una hoja, dado que cada nodo posee un hijo mas que la cantidad
404 de claves, el hijo que sobra será utilizado como referencia al nodo
405 \begin_inset Quotes eld
409 \begin_inset Quotes erd
412 , lo cual constituye el
413 \begin_inset Quotes eld
417 \begin_inset Quotes erd
421 Para un nodo que no sea hoja el hijo será el número de nodo correspondiente
422 según la clave, es decir, para la clave
434 contiene claves menores y el hijo
440 contiene las claves mayores.
441 En el caso particular del nivel 1 (index set) el hijo
447 (secuence set) contiene las claves mayores o iguales ya que el
448 \begin_inset Quotes eld
452 \begin_inset Quotes erd
455 debe contener todas las claves insertadas, esto produce que exista una
456 repetición de las claves entre el nivel 1 y el 0.
459 En nuestro caso hemos implementado un Secuencial Indexado tipo ISAM (Indexed
460 Sequential Access Method) el cual posee en sus hojas las anclas de cada
461 bloque en el archivo de datos, es decir, solo se guardan en los nodos del
462 árbol la menor de las claves de un bloque del archivo de datos, acompañada
463 cada clave por el numero de bloque al cual pertenece.
466 Hemos adoptado que la cantidad de claves máxima en un nodo del árbol sea
467 una cantidad impar, ya que esto facilita la elección de la clave que será
468 promovida hacia su nodo padre en caso de que se produzca un overflow en
475 Para realizar una inserción en el archivo de datos se debe realizar una
476 consulta en el árbol, la cual nos indicará el número de bloque donde debemos
477 insertar el nuevo registro.
480 Las consultas se realizan a través de una estructura INDEX_DAT que posee:
489 Esta estructura se encuentra en el archivo
494 El modo de uso es el siguiente:
497 En primer lugar se carga la clave a insertar en el campo Clave, y en el
498 campo Número de Bloque se almacena un número de bloque válido, mas adelante
499 se explica el por qué.
502 Luego se invoca a la función
504 int emufs_b_plus_get_bloque(INDICE, INDEX_DAT)
506 la cual recibe como parámetro una estructura de índice y un INDEX_DAT para
507 realizar la consulta.
510 Esta función recorre recursivamente el árbol y busca una clave mayor inmediata
511 a la enviada, siempre culminando la búsqueda en una hoja.
512 Al encontrar la clave mayor inmediata, el resultado de la búsqueda será
513 la clave anterior en el nodo, pues cada clave en el nodo es un ancla de
514 bloque de datos, de esta manera la clave anterior será menor a la clave
515 enviada, pues las claves en las hojas están ordenadas.
519 En este paso pueden suceder dos cosas:
522 Que exista una clave menor a la enviada.
525 Que la clave enviada sea menor a todas las claves del árbol.
528 En el primer caso, se ha encontrado la clave y se carga la estructura con
529 el hijo de esa clave, que será el número de bloque donde debe insertarse
530 el nuevo registro (por el cual se realizó la consulta), sobreescribiendo
531 el valor que almacenaba al ingresar, y la función retornará código 0 que
532 indica que se ha encontrado un bloque donde insertar.
535 En el segundo caso, puede darse que la clave enviada sea menor a todas las
536 claves del árbol, por lo cual no es posible encontrar un ancla de bloque
538 Aquí la función retornará código -1 lo cual indica que no se ha encontrado
539 un bloque donde insertar el registro nuevo, y es por esto que la estructura
540 debe inicializarse con un número de bloque válido antes de realizarse la
541 consulta.De esta manera el árbol indica donde debe insertarse un nuevo registro
542 en el archivo de datos.
545 Otro detalle de la inserción es que cuando el árbol indica donde debe insertarse
546 un registro pueden pasar dos cosas nuevamente:
549 Que el registro quepa en el bloque.
552 Que el registro no quepa en el bloque.
555 El primer caso es trivial y el registro se insertará sin problemas en el
559 En el caso que el registro no quepa en el bloque, se deberán separar los
560 registros del bloque en 2 bloques, en original y uno nuevo, cada uno con
561 la mitad (aproximadamente) de los registros.
565 Al partir el bloque el ancla del bloque original no se modificará, pero
566 en el bloque nuevo se crea una nueva anlca de bloque, pues una de las claves
567 pertenecientes a los registros que contiene, será la menor.
570 Antes de actualizar el árbol con el ancla nueva, habrá que discriminar en
571 qué bloque se debe insertar el registro nuevo.
572 Para ello se compara la menor de las claves del nuevo bloque con la clave
573 del registro, si la clave del registro es menor que el ancla del nuevo
574 bloque, este debe ir en el bloque original, y se inserta ordenado en él
575 y se le informa al árbol que actualice (inserte) una nueva clave correspondient
576 e al bloque nuevo, sino se inserta en el bloque nuevo de forma ordenada
577 y en este caso cabe la posibilidad de que el nuevo registro posea la clave
578 mas pequeña de todas en el bloque, por ello se lo inserta ordenadamente
579 con ayuda de la función
581 CLAVE grabar_ordenado_en_bloque(EMUFS *emu, void *ptr, EMUFS_REG_SIZE size,
582 void *bloque, int num_bloque, EMUFS_FREE fs, int *err)
584 la cual inserta el registro ordenado por CLAVE y devuelve la menor de las
585 claves del bloque, que se usará para informarle al árbol que inserte una
586 clave nueva junto con el número de bloque, para indexar este bloque.
592 El proceso de eliminación es bastante similar al de inserción en el sentido
593 que también hay que realizar una consulta en el árbol para obtener el número
594 de bloque al que pertenece una clave.
595 Una vez conocido este número se levanta el bloque correspondiente y se
596 busca secuencialmente el registro que se debe eliminar.
599 Si el registro a eliminar fuera el primero del bloque, habrá que modificar
600 el ancla de bloque en el árbol con el ancla que corresponda a la clave
601 del nuevo menor registro, y si el que se elimina fuera el único registro
602 en el bloque habrá que eliminar la clave del árbol.
605 En cualquier otro caso, solo se eliminará el registro correspondiente y
606 se justificarán los regitros a izquierda.
612 Descripción del algoritmo
615 Luego de buscar varias alternativas sobre algoritmos de ordenamiento externo,
616 se optó por el siguiente (que resultó una mezcla de las alternativas analizadas
620 Tomar uno a uno los registros del archivo a ordenar e
624 en un buffer ordenado hasta llenar el buffer.
627 Quitar el menor de los valores (
631 uno nuevo desde el archivo a ordenar) e insertarlo en un archivo temporal.
634 Quitar del buffer el mínimo valor mayor al último insertado en el archivo
639 nuevamente un registro obtenido del archivo a ordenar) y se lo inserta
640 en el archivo temporal.
641 De esta forma quedan ordenados los registros en el archivo temporal.
644 Repetir el paso 3 hasta que se vacíe el buffer o hasta que no haya ningún
645 valor mayor al último insertado en el archivo temporal.
646 Cuando esto suceda se crea un nuevo archivo temporal volviendo al paso
650 En este punto ya tenemos el buffer vacío y todos los valores del archivo
651 a ordenar repartidos en 1 o más archivos temporales ordenados, sólo queda
652 unir los archivos para volver a un sólo archivo completo y ordenado.
653 El procedimiento es simple:
656 Obtener el mínimo valor de los archivos temporales e insertarlo en el archivo
660 Repetir 1 hasta agotar los registros de todos los archivos temporales.
663 Debe quedar claro que los archivos temporales se comportan como una cola.
664 Es decir que al obtener un registro de un archivo temporal se obtiene el
665 primer registro que se haya insertado (el mínimo por la forma en la que
672 A continuación se presenta un ejemplo para una más fácil comprensión del
676 Supongamos que queremos ordenar un archivo con registros de números enteros
677 (el archivo se lee de izquierda a derecha): 9 6 34 2 8 3 12 43 23 4 19
681 Supongamos que disponemos de un buffer capaz de almacenar 3 registros.
684 Se llena el buffer ordenado
687 Se lee 9 del archivo original y se lo inserta en el buffer ordenado.
691 Se lee 6 del archivo original y se lo inserta en el buffer ordenado.
695 Se lee 34 del archivo original y se lo inserta en el buffer ordenado.
699 Se crea el archivo temporal ordenado 1
702 Se lee el mínimo valor del buffer (6), se lo inserta en el archivo temporal
703 y se carga un nuevo valor del archivo original al buffer (2).
708 Se lee el mínimo valor del buffer mayor al insertado anteriormente (9),
709 se lo inserta en el archivo temporal y se carga un nuevo valor del archivo
710 original al buffer (8).
715 Se lee el mínimo valor del buffer mayor al insertado anteriormente (34),
716 se lo inserta en el archivo temporal y se carga un nuevo valor del archivo
717 original al buffer (3).
722 No hay más valores en el buffer mayores al último insertado (34), fin del
726 Se crea el archivo temporal ordenado 2
729 Se lee el mínimo valor del buffer (2), se lo inserta en el archivo temporal
730 y se carga un nuevo valor del archivo original al buffer (12).
735 Se lee el mínimo valor del buffer mayor al insertado anteriormente (3),
736 se lo inserta en el archivo temporal y se carga un nuevo valor del archivo
737 original al buffer (43).
742 Se lee el mínimo valor del buffer mayor al insertado anteriormente (8),
743 se lo inserta en el archivo temporal y se carga un nuevo valor del archivo
744 original al buffer (23).
749 Se lee el mínimo valor del buffer mayor al insertado anteriormente (12),
750 se lo inserta en el archivo temporal y se carga un nuevo valor del archivo
751 original al buffer (4).
756 Se lee el mínimo valor del buffer mayor al insertado anteriormente (23),
757 se lo inserta en el archivo temporal y se carga un nuevo valor del archivo
758 original al buffer (19).
760 Archivo2: 2 3 8 12 23
763 Se lee el mínimo valor del buffer mayor al insertado anteriormente (43),
764 se lo inserta en el archivo temporal y se carga un nuevo valor del archivo
765 original al buffer (21).
767 Archivo2: 2 3 8 12 23 43
770 No hay más valores en el buffer mayores al último insertado (43), fin del
774 Se crea el archivo temporal ordenado 3
777 Se repite el proceso anterior.
782 Se crea el archivo temporal ordenado 4
785 Se repite el proceso anterior.
787 Archivo4: 1 16 36 42 65
790 Se mezclan los archivos temporales ordenados obteniendo un archivo completo
794 Se obtiene el menor valor de los archivos temporales ordenados (sólo tenemos
795 que elegir entre el primer valor de cada uno).
799 Archivo2: 2 3 8 12 23 43.
800 Archivo3: 4 19 21 87.
801 Archivo4: 1 16 36 42 65
804 Sólo debo comparar y obtener el menor entre 6, 2, 4, y 1.
805 Obtengo el 1, lo saco del archivo temporal y lo agrego al de salida:
809 Archivo2: 2 3 8 12 23 43.
810 Archivo3: 4 19 21 87.
811 Archivo4: 16 36 42 65 Salida: 1
814 Repito hasta que no hayan más valores en los archivos temporales:
818 Archivo2: 3 8 12 23 43.
819 Archivo3: 4 19 21 87.
820 Archivo4: 16 36 42 65.
825 Archivo2: 8 12 23 43.
826 Archivo3: 4 19 21 87.
827 Archivo4: 16 36 42 65.
832 Archivo2: 8 12 23 43.
834 Archivo4: 16 36 42 65.
839 Archivo2: 8 12 23 43.
841 Archivo4: 16 36 42 65.
846 Archivo2: 8 12 23 43.
848 Archivo4: 16 36 42 65.
855 Archivo4: 16 36 42 65.
862 Archivo4: 16 36 42 65.
863 Salida: 1 2 3 4 6 8 9
869 Archivo4: 16 36 42 65.
870 Salida: 1 2 3 4 6 8 9 12
877 Salida: 1 2 3 4 6 8 9 12 16
884 Salida: 1 2 3 4 6 8 9 12 16 19
891 Salida: 1 2 3 4 6 8 9 12 16 19 21
898 Salida: 1 2 3 4 6 8 9 12 16 19 21 23
905 Salida: 1 2 3 4 6 8 9 12 16 19 21 23 34
912 Salida: 1 2 3 4 6 8 9 12 16 19 21 23 34 36
919 Salida: 1 2 3 4 6 8 9 12 16 19 21 23 34 36 42
926 Salida: 1 2 3 4 6 8 9 12 16 19 21 23 34 36 42 43
933 Salida: 1 2 3 4 6 8 9 12 16 19 21 23 34 36 42 43 65
940 Salida: 1 2 3 4 6 8 9 12 16 19 21 23 34 36 42 43 65 87
946 Finalmente, tengo en el archivo de salida el archivo original ordenado.
952 El algoritmo de ordenamiento es completamente genérico, ya que recibe un
953 puntero void como registro, su tamaño (para poder manipularlo sin conocer
954 su tipo) y una función de comparación, para poder comparar dos registros
955 (sin saber su tipo) a través de una relación de orden (descripta por dicha
959 Decisiones de diseño.
962 El algoritmo se eligió en base a una serie de razones y cuenta con una serie
963 de ventajas y desventajas.
966 El algoritmo es simple, tanto teóricamente como para implementar.
969 Tiene la desventaja de que puede llegar a usar muchos archivos temporales
970 y todos abiertos al mismo tiempo, pero considerando que el sistema operativo
971 en el que se utiliza suele manejar bien grandes cantidades de archivos
972 no es una desventaja importante.
975 Al usar un buffer intermedio, se puede controlar muy bien la cantidad de
976 memoria que utiliza y experimentar con distintos valores para analizar
980 El buffer ordenado se implementó con un árbol binario debido a que tiene
981 una buena relación entre velocidad de búsqueda y facilidad de implementación.
982 Al ser el principal determinante de la velocidad los accesos a disco no
983 se creyó necesario buscar una alternativa más rápida para mantener el buffer
984 ordenado en memoria, ya que no cambiaría de forma notable el tiempo total
986 Otras posibilidades hubieran sido cargar todo el buffer en memoria y ordenarlo
987 posteriormente (dependiendo del algoritmo de ordenamiento a utilizar puede
988 ser más o menos rápido que el árbol y más o menos complicado de implementar)
989 o hacer una búsqueda secuencial sobre un buffer desordenado (es más fácil
990 de implementar pero claramente más lento).
991 Una posible ventaja notable de leer el buffer primero y luego ordenarlo
992 en memoria es que se necesita un sólo acceso al disco para llenar el buffer,
993 mientras que al obtener uno a uno los valores puede generar muchos accesos
995 Esto no debería ser muy notable ya que las funciones de acceso a archivos
996 de la biblioteca estándar de C poseen un buffer interno, por lo que los
997 accesos a disco probablemente sea muy poco aún cuando se obtienen uno a
projects / z.facultad / 75.06 / emufs.git / blob