Ahora me doy cuenta de que estás hablando de una lista enlazada, y no es eso lo que he hecho, pues como dices, no podrías realizar un acceso aleatorio. A ver si soy capaz de explicarlo.
En primer lugar; la librería construye mediante una plantilla alrededor de una estructura que se le pasa como registro. Esa estructura deberá tener un índice único, aunque no necesariamente en un solo campo. Además hay que proporcionar una función comparadora de tipo CompResult nombrefuncion(const &estructuraA, const &estructuraB) que sea capaz de comparar dos datos de tipo estructura y devuelva FDB_MINOR, FDB_MAJOR o FDB_EQUAL, según el índice del dato A sea menor o menor que el índice del dato B (o sea el mismo registro).
El archivo que creo tiene tres partes:
- Una cabecera de tamaño fijo en la que se indican el tamaño de la estructura o registro, número de registros válidos, número de registros borrados (físicamente siguen estando en la tabla, pero su espacio será utilizado en primer lugar para nuevas inserciones), y posición del archivo en la que comienzan los datos propiamente dichos, pues antes de ellos está la siguiente sección.
- Índice ordenado según el criterio que hemos proporcionado. Aquí es donde realmente trabajan las operaciones. Es una lista consecutiva (y ordenada según el criterio de índice) de punteros (unsigned long) a los registros propiamente dichos en sección de datos. Es decir, el primer unsigned long apunta al primer registro según el orden (aunque el registro esté físicamente al final del archivo), el segundo al segundo, y así sucesivamente hasta el número de registros válidos indicado en la cabecera. A continuación están tantos punteros a registros borrados como indica la cabecera.
- Finalmente están los registros propiamente dichos, sin orden específico.
Para acceder a un determinado número aleatorio de registro hay que hacerlo en dos pasos. Primero habría que utilizar la función IrRegistro(número de registro), que establecería la variable privada _registroActual con dicho valor (o devolvería error). A continuación, la función leerRegistro(miestructura), toma busca el índice _registroActual en la sección anterior, lee la posición donde se encuentran esos datos, y carga los datos en miestructura.
Para buscar un determinado índice, se cargarían en una estructura de datos busqueda los valores de índice buscados, y la función EncuentraIndex(busqueda, id_registro) cargará en id_registro el id de registro que coincide con los valores de índice que tiene busqueda y devolverá FDB_OK, o devuelve ERR y cargará en id_registro la posición potencial de dicho índice (primer registro mayor). Cada paso de la búsqueda también requiere dos accesos (índice y datos), pero como son datos ordenados, el número de pasos es "lorarítmico" respecto del número de registros (con 16 pasos podríamos encontrar un registro entre 65536). Con el índice devuelto podríamos acceder aleatoriamente a dicho registro de la forma indicada anteriormente.
Modificar un registro existente es también una operación rápida. Una vez posicionado _registroActual en el registro a actualizar, y una estructura con los nuevos datos, dado que los datos son de tamaño uniforme se sobreescriben los datos directamente en la posición que estaban. Lo único a tener en cuenta es que las modificaciones no afecten al índice (posición), en cuyo caso opté por devolver error si coincide con otro índice existente, o actualizarlo y desplazarlo a la posición ordenada correspondiente en otro caso.
Y ahora vienen las operaciones que pueden llegar a gastar más tiempo, ya que requieren desplazamiento de datos. La única ventaja es que sólo se desplazan los datos de índice (unsigned long), no los datos en sí, que pueden ser bastante más pesados. Por ello decía que la ventaja de este sistema la proporciona cuando el tamaño de registro es "grande". Para un listado de números de teléfono, que se pueden guardar como unsigned long, no merece la pena; pero para número de teléfono+nombre, ya empieza a ser ventajoso, si vamos a "atacar" la tabla de forma indexada.
Borrar un registro requiere desplazar el puntero a datos desde la posición indexada que tenía hasta el final del índice (zona de punteror a registros borrados), y a continuación indicarle a la cabecera los nuevos datos (-1 registro lleno, +1 registro borrado). Así que hay que reescribir los índices desde la posición de borrado hasta el final de los índices; si el índice a borrar es el primero, deberemos reescribir tooodo el índice (4bytes*número de registros). Aún así, es mejor que reescribir todos los datos, ¿no?.
Para agregar un nuevo registro, primero buscamos la posición en la que debe ir su índice. A continuación, si hay punteros a registros borrados, aprovechamos el primero, sobreescribimos sus datos, y desplazaremos ese índice hasta la posición correspondiente. De nuevo, si resulta que tiene que ir al principio del índice, mala suerte; aunque seguirá siendo mejor mover un unsigned long por registro que los registros enteros. Si no existen registros borrados, tomaremos la siguiente posición de índice disponible y agregaremos los datos al final del archivo y bajaremos el índice hasta la posición correspondiente. Se presenta un problemazo: ¿qué pasa si no hay espacio para el nuevo índice, porque comenzaría a machacar la sección de datos? Pues que hay que mover el primer bloque de datos al final para hacer hueco a nuevos índices (y actualizar su nueva posición en el índice correspondiente y los datos de cabecera para indicar dónde empiezan ahora los datos).
Bueno. Reconozco que puede resultar un poco lioso, y no he documentado la librería apenas, dado el uso limitado que puede tener; pero estoy abierto a preguntas.