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
366 Se ha implementado un índice secuencial indexado utilizando un árbol B+,
367 el cual tiene la particularidad de tener en sus hojas todas las claves
368 que se han insertado.
371 La estructura de un nodo del árbol es la siguiente:
386 Esta estructura se encuentra en el archivo
391 Esta organización permite, con la ayuda del árbol, mantener el archivo de
392 datos ordenado por la clave principal.
395 Para lograr esto, el árbol nos indicará donde (en qué bloque) debe insertarse
397 (ver 3.3.1 Inserción)
400 En el caso de una hoja, dado que cada nodo posee un hijo mas que la cantidad
401 de claves, el hijo que sobra será utilizado como referencia al nodo
402 \begin_inset Quotes eld
406 \begin_inset Quotes erd
409 , lo cual constituye el
410 \begin_inset Quotes eld
414 \begin_inset Quotes erd
418 Para un nodo que no sea hoja el hijo será el número de nodo correspondiente
419 según la clave, es decir, para la clave
431 contiene claves menores y el hijo
437 contiene las claves mayores.
438 En el caso particular del nivel 1 el hijo
444 contiene las claves mayores o iguales ya que el
445 \begin_inset Quotes eld
449 \begin_inset Quotes erd
452 debe contener todas las claves insertadas, esto produce que exista una
453 repetición de las claves entre el nivel 1 y el 0.
456 En nuestro caso hemos implementado un Secuencial Indexado tipo ISAM (Indexed
457 Sequential Access Method) el cual posee en sus hojas las anclas de cada
458 bloque en el archivo de datos, es decir, solo se guardan en los nodos del
459 árbol la menor de las claves de un bloque del archivo de datos, acompañada
460 cada clave por el numero de bloque al cual pertenece.
466 Para realizar una inserción en el archivo de datos se debe realizar una
467 consulta en el árbol, la cual nos indicará el número de bloque donde debemos
468 insertar el nuevo registro.
471 Las consultas se realizan a través de una estructura INDEX_DAT que posee:
480 Esta estructura se encuentra en el archivo
485 El modo de uso es el siguiente:
488 En primer lugar se carga la clave a insertar en el campo Clave, y en el
489 campo Número de Bloque se almacena un número de bloque válido, mas adelante
490 se explica el por qué.
493 Luego se invoca a la función
495 int emufs_b_plus_get_bloque(INDICE, INDEX_DAT)
497 la cual recibe como parámetro una estructura de índice y un INDEX_DAT para
498 realizar la consulta.
501 Esta función recorre recursivamente el árbol y busca una clave mayor inmediata
502 a la enviada, siempre culminando la búsqueda en una hoja.
503 Al encontrar la clave mayor inmediata, el resultado de la búsqueda será
504 la clave anterior en el nodo, pues cada clave en el nodo es un ancla de
505 bloque de datos, de esta manera la clave anterior será menor a la clave
506 enviada, pues las claves en las hojas están ordenadas.
510 En este paso pueden suceder dos cosas:
513 Que exista una clave menor a la enviada.
516 Que la clave enviada sea menor a todas las claves del árbol.
519 En el primer caso, se ha encontrado la clave y se carga la estructura con
520 el hijo de esa clave, que será el número de bloque donde debe insertarse
521 el nuevo registro (por el cual se realizó la consulta), sobreescribiendo
522 el valor que almacenaba al ingresar, y la función retornará código 0 que
523 indica que se ha encontrado un bloque donde insertar.
526 En el segundo caso, puede darse que la clave enviada sea menor a todas las
527 claves del árbol, por lo cual no es posible encontrar un ancla de bloque
529 Aquí la función retornará código -1 lo cual indica que no se ha encontrado
530 un bloque donde insertar el registro nuevo, y es por esto que la estructura
531 debe inicializarse con un número de bloque válido antes de realizarse la
532 consulta.De esta manera el árbol indica donde debe insertarse un nuevo registro
533 en el archivo de datos.
536 Otro detalle de la inserción es que cuando el árbol indica donde debe insertarse
537 un registro pueden pasar dos cosas nuevamente:
540 Que el registro quepa en el bloque.
543 Que el registro no quepa en el bloque.
546 El primer caso es trivial y el registro se insertará sin problemas en el
550 En el caso que el registro no quepa en el bloque, se deberán separar los
551 registros del bloque en 2 bloques, en original y uno nuevo, cada uno con
552 la mitad (aproximadamente) de los registros.
556 Al partir el bloque el ancla del bloque original no se modificará, pero
557 en el bloque nuevo se crea una nueva anlca de bloque, pues una de las claves
558 pertenecientes a los registros que contiene, será la menor.
561 Antes de actualizar el árbol con el ancla nueva, habrá que discriminar en
562 qué bloque se debe insertar el registro nuevo.
563 Para ello se compara la menor de las claves del nuevo bloque con la clave
564 del registro, si la clave del registro es menor que el ancla del nuevo
565 bloque, este debe ir en el bloque original, y se inserta ordenado en él
566 y se le informa al árbol que actualice (inserte) una nueva clave correspondient
567 e al bloque nuevo, sino se inserta en el bloque nuevo de forma ordenada
568 y en este caso cabe la posibilidad de que el nuevo registro posea la clave
569 mas pequeña de todas en el bloque, por ello se lo inserta ordenadamente
570 con ayuda de la función
572 CLAVE grabar_ordenado_en_bloque(EMUFS *emu, void *ptr, EMUFS_REG_SIZE size,
573 void *bloque, int num_bloque, EMUFS_FREE fs, int *err)
575 la cual inserta el registro ordenado por CLAVE y devuelve la menor de las
576 claves del bloque, que se usará para informarle al árbol que inserte una
577 clave nueva junto con el número de bloque, para indexar este bloque.
583 El proceso de eliminación es bastante similar al de inserción en el sentido
584 que también hay que realizar una consulta en el árbol para obtener el número
585 de bloque al que pertenece una clave.
586 Una vez conocido este número se levanta el bloque correspondiente y se
587 busca secuencialmente el registro que se debe eliminar.
590 Si el registro a eliminar fuera el primero del bloque, habrá que modificar
591 el ancla de bloque en el árbol con el ancla que corresponda a la clave
592 del nuevo menor registro, y si el que se elimina fuera el único registro
593 en el bloque habrá que eliminar la clave del árbol.
596 En cualquier otro caso, solo se eliminará el registro correspondiente y
597 se justificarán los regitros a izquierda.
603 Descripción del algoritmo
606 Luego de buscar varias alternativas sobre algoritmos de ordenamiento externo,
607 se optó por el siguiente (que resultó una mezcla de las alternativas analizadas
611 Tomar uno a uno los registros del archivo a ordenar e
615 en un buffer ordenado hasta llenar el buffer.
618 Quitar el menor de los valores (
622 uno nuevo desde el archivo a ordenar) e insertarlo en un archivo temporal.
625 Quitar del buffer el mínimo valor mayor al último insertado en el archivo
630 nuevamente un registro obtenido del archivo a ordenar) y se lo inserta
631 en el archivo temporal.
632 De esta forma quedan ordenados los registros en el archivo temporal.
635 Repetir el paso 3 hasta que se vacíe el buffer o hasta que no haya ningún
636 valor mayor al último insertado en el archivo temporal.
637 Cuando esto suceda se crea un nuevo archivo temporal volviendo al paso
641 En este punto ya tenemos el buffer vacío y todos los valores del archivo
642 a ordenar repartidos en 1 o más archivos temporales ordenados, sólo queda
643 unir los archivos para volver a un sólo archivo completo y ordenado.
644 El procedimiento es simple:
647 Obtener el mínimo valor de los archivos temporales e insertarlo en el archivo
651 Repetir 1 hasta agotar los registros de todos los archivos temporales.
654 Debe quedar claro que los archivos temporales se comportan como una cola.
655 Es decir que al obtener un registro de un archivo temporal se obtiene el
656 primer registro que se haya insertado (el mínimo por la forma en la que
663 A continuación se presenta un ejemplo para una más fácil comprensión del
667 Supongamos que queremos ordenar un archivo con registros de números enteros
668 (el archivo se lee de izquierda a derecha): 9 6 34 2 8 3 12 43 23 4 19
672 Supongamos que disponemos de un buffer capaz de almacenar 3 registros.
675 Se llena el buffer ordenado
678 Se lee 9 del archivo original y se lo inserta en el buffer ordenado.
682 Se lee 6 del archivo original y se lo inserta en el buffer ordenado.
686 Se lee 34 del archivo original y se lo inserta en el buffer ordenado.
690 Se crea el archivo temporal ordenado 1
693 Se lee el mínimo valor del buffer (6), se lo inserta en el archivo temporal
694 y se carga un nuevo valor del archivo original al buffer (2).
699 Se lee el mínimo valor del buffer mayor al insertado anteriormente (9),
700 se lo inserta en el archivo temporal y se carga un nuevo valor del archivo
701 original al buffer (8).
706 Se lee el mínimo valor del buffer mayor al insertado anteriormente (34),
707 se lo inserta en el archivo temporal y se carga un nuevo valor del archivo
708 original al buffer (3).
713 No hay más valores en el buffer mayores al último insertado (34), fin del
717 Se crea el archivo temporal ordenado 2
720 Se lee el mínimo valor del buffer (2), se lo inserta en el archivo temporal
721 y se carga un nuevo valor del archivo original al buffer (12).
726 Se lee el mínimo valor del buffer mayor al insertado anteriormente (3),
727 se lo inserta en el archivo temporal y se carga un nuevo valor del archivo
728 original al buffer (43).
733 Se lee el mínimo valor del buffer mayor al insertado anteriormente (8),
734 se lo inserta en el archivo temporal y se carga un nuevo valor del archivo
735 original al buffer (23).
740 Se lee el mínimo valor del buffer mayor al insertado anteriormente (12),
741 se lo inserta en el archivo temporal y se carga un nuevo valor del archivo
742 original al buffer (4).
747 Se lee el mínimo valor del buffer mayor al insertado anteriormente (23),
748 se lo inserta en el archivo temporal y se carga un nuevo valor del archivo
749 original al buffer (19).
751 Archivo2: 2 3 8 12 23
754 Se lee el mínimo valor del buffer mayor al insertado anteriormente (43),
755 se lo inserta en el archivo temporal y se carga un nuevo valor del archivo
756 original al buffer (21).
758 Archivo2: 2 3 8 12 23 43
761 No hay más valores en el buffer mayores al último insertado (43), fin del
765 Se crea el archivo temporal ordenado 3
768 Se repite el proceso anterior.
773 Se crea el archivo temporal ordenado 4
776 Se repite el proceso anterior.
778 Archivo4: 1 16 36 42 65
781 Se mezclan los archivos temporales ordenados obteniendo un archivo completo
785 Se obtiene el menor valor de los archivos temporales ordenados (sólo tenemos
786 que elegir entre el primer valor de cada uno).
790 Archivo2: 2 3 8 12 23 43.
791 Archivo3: 4 19 21 87.
792 Archivo4: 1 16 36 42 65
795 Sólo debo comparar y obtener el menor entre 6, 2, 4, y 1.
796 Obtengo el 1, lo saco del archivo temporal y lo agrego al de salida:
800 Archivo2: 2 3 8 12 23 43.
801 Archivo3: 4 19 21 87.
802 Archivo4: 16 36 42 65 Salida: 1
805 Repito hasta que no hayan más valores en los archivos temporales:
809 Archivo2: 3 8 12 23 43.
810 Archivo3: 4 19 21 87.
811 Archivo4: 16 36 42 65.
816 Archivo2: 8 12 23 43.
817 Archivo3: 4 19 21 87.
818 Archivo4: 16 36 42 65.
823 Archivo2: 8 12 23 43.
825 Archivo4: 16 36 42 65.
830 Archivo2: 8 12 23 43.
832 Archivo4: 16 36 42 65.
837 Archivo2: 8 12 23 43.
839 Archivo4: 16 36 42 65.
846 Archivo4: 16 36 42 65.
853 Archivo4: 16 36 42 65.
854 Salida: 1 2 3 4 6 8 9
860 Archivo4: 16 36 42 65.
861 Salida: 1 2 3 4 6 8 9 12
868 Salida: 1 2 3 4 6 8 9 12 16
875 Salida: 1 2 3 4 6 8 9 12 16 19
882 Salida: 1 2 3 4 6 8 9 12 16 19 21
889 Salida: 1 2 3 4 6 8 9 12 16 19 21 23
896 Salida: 1 2 3 4 6 8 9 12 16 19 21 23 34
903 Salida: 1 2 3 4 6 8 9 12 16 19 21 23 34 36
910 Salida: 1 2 3 4 6 8 9 12 16 19 21 23 34 36 42
917 Salida: 1 2 3 4 6 8 9 12 16 19 21 23 34 36 42 43
924 Salida: 1 2 3 4 6 8 9 12 16 19 21 23 34 36 42 43 65
931 Salida: 1 2 3 4 6 8 9 12 16 19 21 23 34 36 42 43 65 87
937 Finalmente, tengo en el archivo de salida el archivo original ordenado.
943 El algoritmo de ordenamiento es completamente genérico, ya que recibe un
944 puntero void como registro, su tamaño (para poder manipularlo sin conocer
945 su tipo) y una función de comparación, para poder comparar dos registros
946 (sin saber su tipo) a través de una relación de orden (descripta por dicha
950 Decisiones de diseño.
953 El algoritmo se eligió en base a una serie de razones y cuenta con una serie
954 de ventajas y desventajas.
957 El algoritmo es simple, tanto teóricamente como para implementar.
960 Tiene la desventaja de que puede llegar a usar muchos archivos temporales
961 y todos abiertos al mismo tiempo, pero considerando que el sistema operativo
962 en el que se utiliza suele manejar bien grandes cantidades de archivos
963 no es una desventaja importante.
966 Al usar un buffer intermedio, se puede controlar muy bien la cantidad de
967 memoria que utiliza y experimentar con distintos valores para analizar
971 El buffer ordenado se implementó con un árbol binario debido a que tiene
972 una buena relación entre velocidad de búsqueda y facilidad de implementación.
973 Al ser el principal determinante de la velocidad los accesos a disco no
974 se creyó necesario buscar una alternativa más rápida para mantener el buffer
975 ordenado en memoria, ya que no cambiaría de forma notable el tiempo total
977 Otras posibilidades hubieran sido cargar todo el buffer en memoria y ordenarlo
978 posteriormente (dependiendo del algoritmo de ordenamiento a utilizar puede
979 ser más o menos rápido que el árbol y más o menos complicado de implementar)
980 o hacer una búsqueda secuencial sobre un buffer desordenado (es más fácil
981 de implementar pero claramente más lento).
982 Una posible ventaja notable de leer el buffer primero y luego ordenarlo
983 en memoria es que se necesita un sólo acceso al disco para llenar el buffer,
984 mientras que al obtener uno a uno los valores puede generar muchos accesos
986 Esto no debería ser muy notable ya que las funciones de acceso a archivos
987 de la biblioteca estándar de C poseen un buffer interno, por lo que los
988 accesos a disco probablemente sea muy poco aún cuando se obtienen uno a
projects / z.facultad / 75.06 / emufs.git / blob