Las técnicas de organización que implementaremos son el Static Hash y el Sequential File. La estructura básica de ambas técnicas así como las operaciones implementadas se describen a continuación.

Static hash

El Static Hash manejará dos archivos. Uno para los índices y otro como archivo principal. Se guardarán los registros en buckets, estos buckets estarán en el índice. El índice almacena como máximo 100 buckets y los buckets almacenan como máximo 10 registros. A diferencia del Sequential File, en el Static Hash los registros no necesitarán un puntero al siguiente registro, razón por la que se manejan estructuras diferentes para estos. Sin embargo, los buckets sí tendrán una variable llamada next donde guardarán la posición del siguiente bucket. Las operaciones implementadas en el Static Hash son las siguientes:

• Inserción: Para insertar un registro este primero se escribe al final del datafile y se guarda su posición, luego se halla el hashkey de su llave. El valor que retorne la función se usara como dirección lógica del bucket en el que se ubicará nuestro registro. Si el bucket está lleno, se crea un nuevo bucket y se escribe donde estaba el bucket lleno. En este bucket se pone nuestro registro. El bucket lleno se moverá hacia el final del index file (LIFO).
• Eliminación: Para eliminar un registro primero se pasa la llave de este por nuestra función remove, la cual obtiene el hashkey de la llave. Una vez obtenemos la posición lógica buscamos el primer bucket no vacío (puede que el primer bucket no tenga elementos por constantes removes) y guardamos la posición de este bucket. Luego tenemos 2 casos: El registro a eliminar está en este bucket o está en uno de los que le siguen (en caso no exista no se realiza ningún cambio). Si la llave está en el bucket, se hace un swap de el último elemento del bucket actual con el que se desea eliminar y se reduce el tamaño del bucket en 1. En caso no esté en este bucket, revisamos los siguientes y también realizamos un swap de el último elemento del primer bucket no vacío y el elemento que tiene la llave del registro que deseamos eliminar, para posteriormente reducir el tamaño del primer bucket no vacío en 1 de igual manera. Una vez realizados estos cambios cambios sobrescribimos ambos buckets en el index.dat.
• Búsqueda Puntual: Para buscar un registro se necesita su llave pues con esta se halla el bucket donde está ubicado (el que tenga el hashkey y los desbordados). Ya en el bucket, lo recorremos buscando la key solicitada, si no la encontramos la función retorna false, caso contrario lee la posición que indica el elemento del bucket en el data file y retorna el registro.
• Búsqueda por rango: La búsqueda por rango en un hash es por fuerza bruta, pues un hash no tiene noción de orden y no podemos asegurar que los keys solicitados se encuentren en un rango de buckets. Recorremos todos los buckets del indexfile (también los desbordados), y si la key se encuentra en el rango solicitado, se añade el registro de la posición que indique el elemento del bucket a una estructura vector que posteriormente será retornada por esta función.

Sequential file

Nuestra implementación del sequential file maneja dos archivos, uno principal de data y otro binario donde se ejecutan las operaciones. No usamos un archivo auxiliar para manejar nuevos registros, pues los insertamos al final del archivo donde van los registros válidos. Para hacer esto y seguir cumpliendo las propiedades del sequential file, se guarda el numero de registros validos y auxiliares para ejecutar las operaciones del sequential como el binary search solo con los registros válidos. Los registros validos están ordenados físicamente mientras los auxiliares no necesariamente. Nuestro sequential file maneja solo archivos de longitud fija debido a que usa binary search para la mayoría de sus métodos. Adicionalmente, puede trabajar con cualquier clase de record debido al uso de los templates T, siendo el tipo de dato de la llave del registro, y Record, siendo la clase del registro. Los registros deberían tener al menos 2 atributos llamados llave (identificador del registro) y next (posición del siguiente registro), siendo este ultimo de tipo long. Las operaciones implementadas en el Sequential hash son las siguientes:

• Inserción: Los registros se insertan al final del archivo como registros auxiliares. Estos registros no estarán necesariamente ordenados. Se ordenarán cuando lleguen a un limite que nosotros pondremos (auxFactor). Cuando la cantidad de registros auxiliares llega a este límite el archivo es reconstruido poniendo los registros auxiliares en orden y contándolos ahora como registros válidos. Entonces, antes de insertar un registro se verifica si los registros auxiliares han pasado su límite o no. Luego, se lee el archivo binario y se busca la posición previa a donde se deba insertar el nuevo registro, para esto se usa el binary search. Si el registro debe ser insertado al inicio del archivo, se lee el primer registro y se escribe al final del archivo, en la parte auxiliar, y se escribe el nuevo registro al principio del archivo de modo que el registro con la menor llave siempre se mantenga en la sección de registros válidos y las demás operaciones se ejecuten correctamente. En cualquier caso, la inserción consiste en leer el registro en la posición previa a la que se debería insertar el nuevo, copiar su valor de next (posición del siguiente registro) en el next del nuevo registro, actualizar el valor de next en el registro previo para que apunte a la posición donde se inserta el nuevo (al final del archivo) y, finalmente, escribir ambos registros con las modificaciones respectivas.
• Eliminación: Los registros son eliminados lógicamente, más no físicamente. Asimismo, se eliminan los registros por su llave. Entonces, primero se abre el archivo binario y se busca la posición del registro a eliminar. Luego se comprueba si se encontró la posición del registro. Si no se encontró y la posición retornada es menor a cero, significa que el registro no esta en el dataset. Si no se encontró y la posición es mayor a cero se lee el registro en esa posición. Si ese registro es el ultimo entonces el registro no esta en el dataset. Si no es ultimo se lee el siguiente registro a este. Ahora, mientras el siguiente registro este entre los registros auxiliares, seguimos buscando el registro a eliminar. Si el registro es encontrado, se elimina colocándole -2 a su atributo next y el next de su registro previo tendra el a anterior next del registro a eliminar. Después, simplemente se escriben estos registros. Sin embargo, si el registro no esta entre los registros auxiliares, simplemente no esta en el dataset. Ahora bien, si la posición del registro que se quiere eliminar sí es encontrada leemos su registro físicamente anterior y el registro siguiente a este. Seguidamente, se leen los registros desde el ultimo leído buscando el que se quiere eliminar. Finalmente, cuando se encuentre el registro a eliminar, se cambia su next a -2 y el next de su registro previo se cambia al next anterior del registro a eliminar y se escriben estos cambios.
• Búsqueda puntual: Para buscar un registro por su llave (key), leemos el archivo binario y aplicamos binary search para hallar la posición del registro. Si el registro no es encontrado, lo leemos y mientras el siguiente registro este entre los auxiliares, se sigue buscando la llave. Por otro lado, si sí hallamos la posición del registro, leemos esa posición y retornamos el registro.
• Búsqueda por rango: Se usa un binary search, aprovechando que el archivo esta ordenado físicamente. Primero, verificaremos que el ultimo valor del rango sea mayor al valor inicial de este. Si no es así, retornaremos error, si sí es así continuamos. Leemos el archivo binario y hacemos binary search para encontrar la posición del primer valor del rango. Si la posición no es encontrada se verifica si es menor a cero o mayor. Si es menor, vamos a la posición del primer registro, de lo contrario, vamos a la posición del registro siguiente. Si la posición sí fue encontrada simplemente vamos hacia esa posición. Después, se lee la posición en la que se este en el archivo y mientras no se este al final del file y la llave del registro que se lee sea menor o igual que el valor final del rango se inserta este registro a un vector. Cuando se termine de leer todos los registros encontrados que estén dentro del rango, se retorna el vector con todos estos registros.