Para el desarrollo del proyecto se utilizó el lenguaje de programación C++ y la librería Qt para la creación de interfaces. Las técnicas de organización que se implementaron fueron Indexed Sequential Access Method (ISAM) y B+ Tree, a continuación se explicarán los conceptos de estas y como fueron desarrolladas.

Ténicas aplicadas

Indexed Sequential Access Method (ISAM)

ISAM es una técnica de organización de archivos creada por IBM con la intención de disminuir el tiempo de acceso a la data. La data es manejada en forma de records de tamaño fijo y usualmente es mantenida de manera desordenada o parcialmente ordenada dentro de los archivos. Esta técnica está basada en la utilización de indices, los cuales almacenan punteros a los diferentes records existentes y pueden ser implementados de multiples formas, sin embargo en todos los casos se deben mantener ordenados con respecto a un campo elegido de la data. La caracteristica principal de ISAM es que mantiene un indice de un tamaño lo suficientemente pequeño como para poder ser utilizado en la memoria principal y realizar operaciones mucho más efectivas.

La implementación que se dió en este proyecto fue la de un ISAM con indice denso. Los indices densos tienen la particularidad de mantener una tupla de [key, dirección] por cada record de la data, de esta forma se puede acceder directamente a cualquier registro desde el indice. Esta manera de implementar permite un acceso bastante rápido, ya que las busquedas se realizan mediante un binary search. Sin embargo la cantidad de espacio que ocupa el indice en la memoria principal es bastante grande comparado con las demás implementaciones como en los casos de sparse y multilevel index.

Funciones principales

Insert

Para la inserción de datos primero se debe realizar una busqueda en el indice del key perteneciente al record que se quiere añadir. Si no se encuentra lo único que es necesario hacer es agregar el registro al final del archivo de datos y agregar un nuevo elemento al indice que contenga como valor la última posición del archivo de datos y la key del record. En caso contrario, si se encuentra dentro del indice se tendrá que cambiar el valor en la tupla identificada y igualmente añadir el elemento al final del archivo de datos.

Para manejar los objetos repetidos entre los datos se puede utilizar una variable global que vaya contando la cantidad de registros duplicados, de esta manera al momento de insertar una tupla en el indice solo se le deberá sumar la cantidad guardada en la variable a la cantidad de elementos en el archivo de datos como en index_record->second = m_index.size() + REPEATED;.

Delete

La funcionalidad de remover registros en ISAM se basa en desenlazar el record del indice. Primero se realiza una busqueda dentro del indice, luego se cambia el valor de la dirección por un valor negativo, lo cual indica que no debe ser tomado en cuenta al momento de reescribir los datos, ya sea por compresión o por dejar de utilizarlo.

Search

La busqueda de records es bastante simplificada en ISAM debido al uso del indice. Primero se realiza una busqueda binaria en la estructura del indice, en el contexto de este proyecto vendría a ser un map. Si se encuentra la key del record en el indice tan solo habría que leer el valor que almacena la tupla identificada e ir directamente a esa posición dentro del archivo de datos para leer el registro que se requiere. En caso no se encuentre el elemento dentro del indice la función debería retornar una exepción como throw std::invalid_argument( "Key value is not found" );.

B+ Tree

Es una extension de los B-Tree que permite insertion, eliminacion y busqueda más eficientes. En un B-tree los Keys y records pueden ser guardados tanto en nodos internos como nodos hoja, mientras que en un B+ Tree, los records solo pueden ser almacenados en nodos hoja y los nodos internos solo almacenan keys. Los nodos hoja son conectados con la misma estructura que una Linked list.

For the implementation we connect the key stored in the B+ Tree with the page-id (position) in the record file. This way we can search for a target key in the index and get the position where the record is stored in the binary file. This implementation uses an iterator class and a PageManager class to read and write on the binary files. It allows for insertion, deletion (using a key) and searching by key or by a range of keys (using iterators).

Funciones Principales

Insert

Se crea un nuevo nodo hoja y se mueven la mitad de los elementos del nodo al nuevo nodo. Se inserta el key más pequeño del nuevo nodo hoja en el padre. Si el padre está lleno, se realiza un split. Se agrega el key del medio al nodo padre. Se repite esta acción hasta que se encuentre un padre que no necesite split. Si se hace un split en el root del árbol, se crea un nuevo root que tiene solo 1 key y 2 punteros.

Delete

Se realiza una búsqueda para encontrar el Key que se quiere eliminar. Luego existen 3 posibles casos:

1. Hay más del mínimo numero de keys en el nodo: se elimina el key simplemente.
2. La key está presente en los nodos internos también. Estas también deben ser borradas, teniendo en cuenta si existe el número mínimo de keys en el nodo que se esta modificando.
3. Se reduce en 1 la altura del árbol y se reordenan los nodos.

Search

Se realiza un binary search en los records del nodo actual. Si se encuentra el key, se retorna. Si el nodo actual es un nodo hoja y no se encontró el key, se retorna nulo. En el caso contrario, se repite el mismo proceso para el siguiente branch del árbol.

Simulación de transacciones

Para simular las transacciones se utilizó std::thread para lanzar procesos de lectura y escritura (a través de alguna estrategia de organización de archivos) en paralelo. Utilizando un std::mutex se pudo realizar un lock en los archivos que estaban siendo escritos o leídos para luego ser escritos.