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
538 Descripción del algoritmo
541 Luego de buscar varias alternativas sobre algoritmos de ordenamiento externo,
542 se optó por el siguiente (que resultó una mezcla de las alternativas analizadas
546 Tomar uno a uno los registros del archivo a ordenar e
550 en un buffer ordenado hasta llenar el buffer.
553 Quitar el menor de los valores (
557 uno nuevo desde el archivo a ordenar) e insertarlo en un archivo temporal.
560 Quitar del buffer el mínimo valor mayor al último insertado en el archivo
565 nuevamente un registro obtenido del archivo a ordenar) y se lo inserta
566 en el archivo temporal.
567 De esta forma quedan ordenados los registros en el archivo temporal.
570 Repetir el paso 3 hasta que se vacíe el buffer o hasta que no haya ningún
571 valor mayor al último insertado en el archivo temporal.
572 Cuando esto suceda se crea un nuevo archivo temporal volviendo al paso
576 En este punto ya tenemos el buffer vacío y todos los valores del archivo
577 a ordenar repartidos en 1 o más archivos temporales ordenados, sólo queda
578 unir los archivos para volver a un sólo archivo completo y ordenado.
579 El procedimiento es simple:
582 Obtener el mínimo valor de los archivos temporales e insertarlo en el archivo
586 Repetir 1 hasta agotar los registros de todos los archivos temporales.
589 Debe quedar claro que los archivos temporales se comportan como una cola.
590 Es decir que al obtener un registro de un archivo temporal se obtiene el
591 primer registro que se haya insertado (el mínimo por la forma en la que
598 A continuación se presenta un ejemplo para una más fácil comprensión del
602 Supongamos que queremos ordenar un archivo con registros de números enteros
603 (el archivo se lee de izquierda a derecha): 9 6 34 2 8 3 12 43 23 4 19
607 Supongamos que disponemos de un buffer capaz de almacenar 3 registros.
610 Se llena el buffer ordenado
613 Se lee 9 del archivo original y se lo inserta en el buffer ordenado.
617 Se lee 6 del archivo original y se lo inserta en el buffer ordenado.
621 Se lee 34 del archivo original y se lo inserta en el buffer ordenado.
625 Se crea el archivo temporal ordenado 1
628 Se lee el mínimo valor del buffer (6), se lo inserta en el archivo temporal
629 y se carga un nuevo valor del archivo original al buffer (2).
634 Se lee el mínimo valor del buffer mayor al insertado anteriormente (9),
635 se lo inserta en el archivo temporal y se carga un nuevo valor del archivo
636 original al buffer (8).
641 Se lee el mínimo valor del buffer mayor al insertado anteriormente (34),
642 se lo inserta en el archivo temporal y se carga un nuevo valor del archivo
643 original al buffer (3).
648 No hay más valores en el buffer mayores al último insertado (34), fin del
652 Se crea el archivo temporal ordenado 2
655 Se lee el mínimo valor del buffer (2), se lo inserta en el archivo temporal
656 y se carga un nuevo valor del archivo original al buffer (12).
661 Se lee el mínimo valor del buffer mayor al insertado anteriormente (3),
662 se lo inserta en el archivo temporal y se carga un nuevo valor del archivo
663 original al buffer (43).
668 Se lee el mínimo valor del buffer mayor al insertado anteriormente (8),
669 se lo inserta en el archivo temporal y se carga un nuevo valor del archivo
670 original al buffer (23).
675 Se lee el mínimo valor del buffer mayor al insertado anteriormente (12),
676 se lo inserta en el archivo temporal y se carga un nuevo valor del archivo
677 original al buffer (4).
682 Se lee el mínimo valor del buffer mayor al insertado anteriormente (23),
683 se lo inserta en el archivo temporal y se carga un nuevo valor del archivo
684 original al buffer (19).
686 Archivo2: 2 3 8 12 23
689 Se lee el mínimo valor del buffer mayor al insertado anteriormente (43),
690 se lo inserta en el archivo temporal y se carga un nuevo valor del archivo
691 original al buffer (21).
693 Archivo2: 2 3 8 12 23 43
696 No hay más valores en el buffer mayores al último insertado (43), fin del
700 Se crea el archivo temporal ordenado 3
703 Se repite el proceso anterior.
708 Se crea el archivo temporal ordenado 4
711 Se repite el proceso anterior.
713 Archivo4: 1 16 36 42 65
716 Se mezclan los archivos temporales ordenados obteniendo un archivo completo
720 Se obtiene el menor valor de los archivos temporales ordenados (sólo tenemos
721 que elegir entre el primer valor de cada uno).
725 Archivo2: 2 3 8 12 23 43.
726 Archivo3: 4 19 21 87.
727 Archivo4: 1 16 36 42 65
730 Sólo debo comparar y obtener el menor entre 6, 2, 4, y 1.
731 Obtengo el 1, lo saco del archivo temporal y lo agrego al de salida:
735 Archivo2: 2 3 8 12 23 43.
736 Archivo3: 4 19 21 87.
737 Archivo4: 16 36 42 65 Salida: 1
740 Repito hasta que no hayan más valores en los archivos temporales:
744 Archivo2: 3 8 12 23 43.
745 Archivo3: 4 19 21 87.
746 Archivo4: 16 36 42 65.
751 Archivo2: 8 12 23 43.
752 Archivo3: 4 19 21 87.
753 Archivo4: 16 36 42 65.
758 Archivo2: 8 12 23 43.
760 Archivo4: 16 36 42 65.
765 Archivo2: 8 12 23 43.
767 Archivo4: 16 36 42 65.
772 Archivo2: 8 12 23 43.
774 Archivo4: 16 36 42 65.
781 Archivo4: 16 36 42 65.
788 Archivo4: 16 36 42 65.
789 Salida: 1 2 3 4 6 8 9
795 Archivo4: 16 36 42 65.
796 Salida: 1 2 3 4 6 8 9 12
803 Salida: 1 2 3 4 6 8 9 12 16
810 Salida: 1 2 3 4 6 8 9 12 16 19
817 Salida: 1 2 3 4 6 8 9 12 16 19 21
824 Salida: 1 2 3 4 6 8 9 12 16 19 21 23
831 Salida: 1 2 3 4 6 8 9 12 16 19 21 23 34
838 Salida: 1 2 3 4 6 8 9 12 16 19 21 23 34 36
845 Salida: 1 2 3 4 6 8 9 12 16 19 21 23 34 36 42
852 Salida: 1 2 3 4 6 8 9 12 16 19 21 23 34 36 42 43
859 Salida: 1 2 3 4 6 8 9 12 16 19 21 23 34 36 42 43 65
866 Salida: 1 2 3 4 6 8 9 12 16 19 21 23 34 36 42 43 65 87
872 Finalmente, tengo en el archivo de salida el archivo original ordenado.
878 El algoritmo de ordenamiento es completamente genérico, ya que recibe un
879 puntero void como registro, su tamaño (para poder manipularlo sin conocer
880 su tipo) y una función de comparación, para poder comparar dos registros
881 (sin saber su tipo) a través de una relación de orden (descripta por dicha
885 Decisiones de diseño.
888 El algoritmo se eligió en base a una serie de razones y cuenta con una serie
889 de ventajas y desventajas.
892 El algoritmo es simple, tanto teóricamente como para implementar.
895 Tiene la desventaja de que puede llegar a usar muchos archivos temporales
896 y todos abiertos al mismo tiempo, pero considerando que el sistema operativo
897 en el que se utiliza suele manejar bien grandes cantidades de archivos
898 no es una desventaja importante.
901 Al usar un buffer intermedio, se puede controlar muy bien la cantidad de
902 memoria que utiliza y experimentar con distintos valores para analizar
906 El buffer ordenado se implementó con un árbol binario debido a que tiene
907 una buena relación entre velocidad de búsqueda y facilidad de implementación.
908 Al ser el principal determinante de la velocidad los accesos a disco no
909 se creyó necesario buscar una alternativa más rápida para mantener el buffer
910 ordenado en memoria, ya que no cambiaría de forma notable el tiempo total
912 Otras posibilidades hubieran sido cargar todo el buffer en memoria y ordenarlo
913 posteriormente (dependiendo del algoritmo de ordenamiento a utilizar puede
914 ser más o menos rápido que el árbol y más o menos complicado de implementar)
915 o hacer una búsqueda secuencial sobre un buffer desordenado (es más fácil
916 de implementar pero claramente más lento).
917 Una posible ventaja notable de leer el buffer primero y luego ordenarlo
918 en memoria es que se necesita un sólo acceso al disco para llenar el buffer,
919 mientras que al obtener uno a uno los valores puede generar muchos accesos
921 Esto no debería ser muy notable ya que las funciones de acceso a archivos
922 de la biblioteca estándar de C poseen un buffer interno, por lo que los
923 accesos a disco probablemente sea muy poco aún cuando se obtienen uno a
projects / z.facultad / 75.06 / emufs.git / blob