Con la autorización de los ayudantes de la cátedra decidimos que el árbol
B+ sólo pueda ser utilizado para índices principal ya que de otra manera
- no tiene sentido el set secuencial (para una justificación más detallada
- ver FIXME: REFERENCIA A EXPLICACION DE B+)3.
+ no tiene sentido el set secuencial.
\layout Standard
Finalmente, para obtener listados basados en campos de los cuales no se
\family typewriter
INDICE_DATO
\family default
-: usado para representar el conjunto de un ID más la ubicación del dato
- asociado.
+: usado para representar el conjunto de un ID más su dato.
\layout Itemize
\emph default
es la estructura principal que encapsula todas las funciones para el manejo
de un índice.
- Posee punteros a funciones que permite utilizar la misma interface para
+ Posee punteros a funciones que permite utilizar la misma interfaz para
distintas implementaciones de árboles.
\layout Standard
Integración con
\family typewriter
EMUFS
+\family default
+.
\layout Standard
Para integrar la utilización de índices a
fueron necesarios los siguientes cambios:
\layout Paragraph
-Nuevos tipos de archivo
+Nuevos tipos de archivo.
\layout Standard
Se incluyen dos tipos de archivo nuevos T4 y T5, que representan, respectivament
ya que al saber que es T4 o T5 siempre se inserta de forma ordenada.
\layout Paragraph
-Puntero a un arreglo de índices
+Puntero a un arreglo de índices.
\layout Standard
Se agrega a la estructura
, donde el primero es siempre el índice principal.
\layout Chapter
-Implementación
+Especificaciones de índices
\layout Section
-Árbol B
+Indice B
\layout Section
-Árbol B*
+Indice B*
+\layout Subsection
+
+Decisiones de diseño
+\layout Standard
+
+Una de las pocas decisiones 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
+ hubiéramos 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
+
+Además 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
-Árbol B+
+Indice B+ Secuencial Indexado
+\layout Standard
+
+Se ha implementado un índice secuencial indexado utilizando un árbol B+,
+ el cual tiene la particularidad de tener en sus hojas todas las claves
+ que se han insertado.
+\layout Standard
+
+La estructura de un nodo del árbol es la siguiente:
+\layout Itemize
+
+Nivel
+\layout Itemize
+
+Cantidad de claves
+\layout Itemize
+
+Arreglo de claves
+\layout Itemize
+
+Arreglo de hijos
+\layout Standard
+
+Esta estructura se encuentra en el archivo
+\family typewriter
+indice_bplus.h
+\layout Standard
+
+Esta organización permite, con la ayuda del árbol, mantener el archivo de
+ datos ordenado por la clave principal.
+\layout Standard
+
+Para lograr esto, el árbol nos indicará donde (en qué bloque) debe insertarse
+ un registro.
+ (ver 3.3.1 Inserción)
+\layout Standard
+
+En el caso de una hoja, dado que cada nodo posee un hijo mas que la cantidad
+ de claves, el hijo que sobra será utilizado como referencia al nodo
+\begin_inset Quotes eld
+\end_inset
+
+hermano
+\begin_inset Quotes erd
+\end_inset
+
+, lo cual constituye el
+\begin_inset Quotes eld
+\end_inset
+
+set secuencial
+\begin_inset Quotes erd
+\end_inset
+
+ del índice.
+ Para un nodo que no sea hoja el hijo será el número de nodo correspondiente
+ según la clave, es decir, para la clave
+\series bold
+\emph on
+n
+\series default
+\emph default
+el hijo
+\series bold
+\emph on
+n
+\series default
+\emph default
+ contiene claves menores y el hijo
+\series bold
+\emph on
+n+1
+\series default
+\emph default
+ contiene las claves mayores.
+ En el caso particular del nivel 1 el hijo
+\series bold
+\emph on
+n+1
+\series default
+\emph default
+ contiene las claves mayores o iguales ya que el
+\begin_inset Quotes eld
+\end_inset
+
+secuence set
+\begin_inset Quotes erd
+\end_inset
+
+ debe contener todas las claves insertadas, esto produce que exista una
+ repetición de las claves entre el nivel 1 y el 0.
+\layout Standard
+
+En nuestro caso hemos implementado un Secuencial Indexado tipo ISAM (Indexed
+ Sequential Access Method) el cual posee en sus hojas las anclas de cada
+ bloque en el archivo de datos, es decir, solo se guardan en los nodos del
+ árbol la menor de las claves de un bloque del archivo de datos, acompañada
+ cada clave por el numero de bloque al cual pertenece.
+\layout Subsection
+
+Inserción
+\layout Standard
+
+Para realizar una inserción en el archivo de datos se debe realizar una
+ consulta en el árbol, la cual nos indicará el número de bloque donde debemos
+ insertar el nuevo registro.
+\layout Standard
+
+Las consultas se realizan a través de una estructura INDEX_DAT que posee:
+\layout Itemize
+
+Clave
+\layout Itemize
+
+Número de Bloque
+\layout Standard
+
+Esta estructura se encuentra en el archivo
+\family typewriter
+indice_bplus.h
+\layout Standard
+
+El modo de uso es el siguiente:
+\layout Standard
+
+En primer lugar se carga la clave a insertar en el campo Clave, y en el
+ campo Número de Bloque se almacena un número de bloque válido, mas adelante
+ se explica el por qué.
+\layout Standard
+
+Luego se invoca a la función
+\family typewriter
+int emufs_b_plus_get_bloque(INDICE, INDEX_DAT)
+\family default
+la cual recibe como parámetro una estructura de índice y un INDEX_DAT para
+ realizar la consulta.
+\layout Standard
+
+Esta función recorre recursivamente el árbol y busca una clave mayor inmediata
+ a la enviada, siempre culminando la búsqueda en una hoja.
+ Al encontrar la clave mayor inmediata, el resultado de la búsqueda será
+ la clave anterior en el nodo, pues cada clave en el nodo es un ancla de
+ bloque de datos, de esta manera la clave anterior será menor a la clave
+ enviada, pues las claves en las hojas están ordenadas.
+
+\layout Standard
+
+En este paso pueden suceder dos cosas:
+\layout Enumerate
+
+Que exista una clave menor a la enviada.
+\layout Enumerate
+
+Que la clave enviada sea menor a todas las claves del árbol.
+\layout Standard
+
+En el primer caso, se ha encontrado la clave y se carga la estructura con
+ el hijo de esa clave, que será el número de bloque donde debe insertarse
+ el nuevo registro (por el cual se realizó la consulta), sobreescribiendo
+ el valor que almacenaba al ingresar, y la función retornará código 0 que
+ indica que se ha encontrado un bloque donde insertar.
+\layout Standard
+
+En el segundo caso, puede darse que la clave enviada sea menor a todas las
+ claves del árbol, por lo cual no es posible encontrar un ancla de bloque
+ para esa clave.
+ Aquí la función retornará código -1 lo cual indica que no se ha encontrado
+ 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 orden (descripta por dicha
+ función).
\layout Section
-Ordenamiento externo
+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.
\the_end
projects / z.facultad / 75.06 / emufs.git / blobdiff