Sobre implementación de archivo base de datos Arduino

Hola a todos.

La pregunta es sencilla: ¿existe ya una librería (para Arduino por supuesto) para manejar archivos como bases de datos? ¿O me puedo dar la libertad de crear una con el fin de dar un aporte?

Debo aclarar que debe tener la capacidad de insertar, sobrescribir (modificar) y eliminar registros individuales (pista: a manera de lista enlazada). El tamaño del archivo puede ser fijo o con capacidad de crecer.

Resumiendo: ¿existe algo así o estaría "reinventando la rueda" si creo mi propia implementación?

No sé si es exactamente lo que preguntas, o tal vez pueda servirte como base; pero tiempo ha hice algo para manejar una tabla con un índice. Gestión e indexación de registros de una tabla en SD. - Proyectos - Arduino Forum

Pero mi pregunta es: ¿hace lo que acabo de describir?

La idea de preguntarlo es para evitar crear algo que se vaya a quedar sólo en lo didáctico y que no tenga mucha utilidad...

Eso deberás decirlo tú, Lucario; que eres quien conoce a fondo tu idea, así que lo siento, pero te toca leer a ti

Ahora en serio, por si no está claro en el hilo que se desarrolló al respecto. La librería que hice, toma como parámetros básicos una struct de datos, que será la definición de los datos de un registro de la tabla, y una función que tome como parámetros dos estructuras de datos del tipo definido, y que haga una comparación y devuelva si el registro a es mayor, menor o igual que el registro b. Permite agregar, insertar o borrar registros y mantiene un índice al principio del propio archivo de la tabla, ordenado según la función de ordenación definida.

Si tienes alguna duda de funcionamiento o planteamiento, te la puedo aclarar; pues recuerdo más o menos los fundamentos que usé. Realmente, se trató más de un divertimento que de algo que considerara que iba a tener una utilidad general; si bien para manejar una tabla de tamaño considerable de forma autónoma puede venir bastante bien.

noter:
La librería que hice, toma como parámetros básicos una struct de datos, que será la definición de los datos de un registro de la tabla, y una función que tome como parámetros dos estructuras de datos del tipo definido, y que haga una comparación y devuelva si el registro a es mayor, menor o igual que el registro b.

¿Y fue difícil? Digo, es que por lo que tenía en mente creí que no era posible comparar sistemáticamente dos registros para hacer posible el ordenamiento.

Un struct ocupará cierta cantidad de bytes, pero cómo están organizados esos bytes depende de la aplicación. Si quiero programar de manera generalizada, la composición no es posible conocerla directamente (podría dar la opción de agregar descripciones de campos en la cabecera del archivo, pero hasta ahí); por eso hablo de registros meramente y no de campos.
Hacer comparación binaria (algo similar a memcmp) podría ser incorrecto dependiendo del contexto que estemos manejando; por ejemplo: se pretende que los registros se ordenen según un campo llamado "Nombre", la comparación binaria no necesariamente lo realiza así.
¿O será que en comparación binaria de struct, el valor del primer campo (variable) declarado siempre se convierte en el criterio de ordenamiento?

Imagínate que al no poder determinar generalizadamente la composición de un registro, tenía pensado que las funciones de lectura/escritura de registros recibieran un puntero de tipo void; que, si no me equivoco, admite punteros de cualquier tipo de dato que al final se va a usar como un vector de bytes. La longitud no es necesario pedirla porque se supone que los registros son de tamaño fijo.

noter:
Permite agregar, insertar o borrar registros y mantiene un índice al principio del propio archivo de la tabla, ordenado según la función de ordenación definida.

Eso no me quedó muy claro.

En lo que tenía planeado, era sólo un índice al primer elemento, otro al último, y un mapa de bits para mantener la pista de cuales espacios (del tamaño del registro + 8 bytes) están libres y cuales realmente están ocupados.
Claro que la cabecera tendrá más información; esa es solo la parte de administración del acceso y del espacio

noter:
Si tienes alguna duda de funcionamiento o planteamiento, te la puedo aclarar; pues recuerdo más o menos los fundamentos que usé.

Creo que aquí te dejé una o un par de preguntas...

noter:
Realmente, se trató más de un divertimento que de algo que considerara que iba a tener una utilidad general

Y en eso acabaría mi creación también si me doy cuenta que algo como esto ya existe.

noter:
si bien para manejar una tabla de tamaño considerable de forma autónoma puede venir bastante bien.

¿En serio?

Si lo tienes como una lista enlazada, la inserción y eliminación son eficientes; pero la debilidad está en el acceso aleatorio.

PD: ¿la librería SD lo trae o solo SdFat? Hablo de algún método de asignación rápida de espacio al crear un archivo nuevo. En una situación donde potencialmente la base de datos puede acercarse al gigabyte, hacer crecer el archivo manualmente con Arduino hasta monstruosamente descomunal tamaño, se tardaría más de 5 horas (asumiendo una velocidad de escritura de 55 KB/s).

Estas hablando en serio Lucario... una base de datos de 1GB manejada por Arduino?
Me pregunto que sentido tiene primero siendo que puedes hacer algo mayor con menos esfuerzo usando Raspberry Pi MySQL etc... o bien un arduino pero con la base de datos en la nube.
En fin... tal vez tenga visión limitada.

surbyte:
En fin... tal vez tenga visión limitada.

No no, entiendo tu punto de vista.

Para el poder de procesamiento de los AVR, 1 GB es descabellado.
Lo que ocurre es que como los índices son de 32 bits, el límite está en el espacio de almacenamiento o el sistema de archivos (una de dos); por eso hablo de un "potencial" caso.

No es tan sofisticado como MySQL, pero debería facilitar aplicaciones más sencillas como manejo de directorios telefónicos (pista de dónde vino la idea), inventarios; en fin, como un vector de objetos almacenados en una tarjeta SD, pero con la capacidad de insertar y eliminar en cualquier punto (índice).

Ahh ya veo tu punto.. y teorizando, una búsqueda en una DB de 1GB cuanto podria demorar?
O porque no probarlo no?

Porque no probamos algo semejante usando un Arduino UNO, un DUE, un nodemcu y algun otro que crean conveniente?

surbyte:
y teorizando, una búsqueda en una DB de 1GB cuanto podria demorar?
O porque no probarlo no?

En MySQL... supongo que un tiempo todavía aceptable.

En un AVR, suponiendo que todos los espacios en una base de datos de 1 GB están ocupados... ¿2 horas en el peor de los casos? (estimación).

Bueno, semejante ineficiencia se debe a la debilidad de la lista enlazada frente al acceso aleatorio: una posición absoluta no necesariamente refleja el índice real del conjunto. Encima si no se tiene definido un algoritmo de comparación, la inserción ordenada no sería posible; y por ende no sería tampoco posible realizar una búsqueda binaria (de todos modos, en listas enlazadas, la búsqueda binaria es peor que la secuencial).
Todavía peor, ejecutar un algoritmo de ordenamiento en esta estructura de datos es un dolor de cabeza.
Ahhhh ya no sé qué es peor: una búsqueda estrepitosamente lenta (debilidad de la lista enlazada), o una eliminación estrepitosamente lenta (debilidad de los vectores de posiciones absolutas contiguas).

Aquí es donde me pregunto: ¿la implementación de noter tiene el mismo problema?

surbyte:
Porque no probamos algo semejante usando un Arduino UNO, un DUE, un nodemcu y algun otro que crean conveniente?

Podría ser, aunque los resultados son un tanto predecibles; pero nunca está de más cuantificarlos. Otro candidato es mi STM32 "Blue Pill" que tardó dos meses en llegar :o

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.

Ahhh ya veo; es justo como los lenguajes orientados a objetos manejan vectores simples de objetos: al intercambiar de posición elementos del mismo vector, sólo intercambias sus referencias (punteros) y no los objetos en sí. Así lo tengo aprendido.
Pues sí, mover punteros es computacionalmente más sencillo que mover bloques enteros de datos.

noter:
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.

A diferencia de tu implementación, yo tenía pensado agregar una sección opcional y dos obligatorias en la cabecera:

Opcional: una descripción de hasta 255 campos, 20 caracteres cada una. Si tu implementación no tiene forma directa de determinar la composición de un registro, entonces esta sección sería meramente de etiquetado, sin verificación y la cantidad determinada en tiempo de creación del archivo (como parámetro de una función).
Es solo una idea, podría expanderse el límite si 20 caracteres no son suficientes; o incluso agregar datos extra como el tipo de dato que se supone que representa.

Obligatorio 1: un "número mágico" que identifique este tipo de archivo. No solo serviría como primer paso de validación; sino que incluso podría ser útil para los software recuperadores de archivos borrados que tengan la opción de insertar un nuevo patrón de reconocimiento de cabecera.

Obligatorio 2: no tan obligatorio, pero se me ocurrió que se podría agregar un identificador de versión. Si alguna eventual revisión implicara modificar la estructura de la cabecera, este identificador inmediatamente nos diría si esta debe leerse de la forma nueva, o de alguna de las formas antiguas (si la retrocompatibilidad no es una opción, entonces sirve para detectar un archivo "incompatible").

Y luego se me vino a la mente que si agregarle una bandera de "histórico"; si está activa, entonces la base de datos se finaliza y a partir de ahí considera histórica; por lo tanto, de solo lectura.
Si los AVR fueran lo suficientemente potentes, también agregaría sumas de verificación (checksums) para robustecer más el formato del archivo.

Pero bueno, al ser una implementación cuya utilidad aún se cuestiona, todavía hay que pensar detenidamente qué vale la pena agregar y qué no.

noter:
Para buscar un determinado índice, se cargarían en una estructura de datos busqueda los valores de índice buscados

Si el tamaño del registro se declara excesivo, esto no sería posible cuando estamos apretados en RAM.

noter:
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

Explícate bien esa parte, que de primera impresión me pareció contradictorio.

Si modifico un registro ya existente, entonces podría deliberadamente arruinar el orden (a menos que se esté aplicando un algoritmo de ordenamiento en cada intento). Para evitar la situación anterior, se lanza un error; por lo tanto... ¿no se pueden modificar registros existentes?

noter:
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.

Y supongo que, al ser las operaciones con tarjeta SD bajo buffer, desplazar punteros tampoco se tarda mucho (se pueden desplazar hasta 127 sin tener que mandar a escribir el bloque completo).

noter:
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?.

Es lo que acabo de decir...

noter:
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

Este siempre está después del último puntero válido del vector, ¿o no?. Si están mezclados, ¿cómo vas a determinar un puntero inválido?

noter:
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).

Entonces haces crecer el archivo según la demanda; en vez de fijar su tamaño inicialmente.

En ese caso se me ocurre que la cabecera acabe en un puntero a la tabla de índices; así lo podrás ubicar dinámicamente junto con los demás registros. Es la misma técnica que utiliza NTFS (o FAT con los subdirectorios de la raíz): tiene una tabla con los metadatos de todos los archivos, la "Master File Table" o MFT, la cual en sí también es un archivo.

Para esto tendrías que decidir si los registros deben tener una longitud múltiplo de 4, o la tabla deber ser múltiplo del tamaño de los registros; ya que, así como la MFT es un archivo en NTFS, la tabla de índices se tendrá que almacenar como uno o múltiples registros.
Conviene nunca fragmentarla; de lo contrario la tabla pasará a ser una lista enlazada.

Lucario448:
A diferencia de tu implementación, yo tenía pensado agregar una sección opcional y dos obligatorias en la cabecera: . . . . .
. . . .
Pero bueno, al ser una implementación cuya utilidad aún se cuestiona, todavía hay que pensar detenidamente qué vale la pena agregar y qué no.

Ten en cuenta que esto sería interesante si quieres realizar algún tipo de estándar para poder leerlo desde un ordenador o de forma genérica desde otro arduino. En un arduino la utilidad que puede tener una "base de datos" (la llamaremos así, aunque sabemos que está lejos de serlo) a mi entender, es como forma de guardar y poder rescatar de una forma efectiva una determinada información entre un conjunto grande. Si deseo que esa información sea generable o importable desde un ordenador, por ejemplo; tengo dos opciones: hacer un programa para ordenador que entienda mi estructura de datos, o estudiar e intentar ceñir mi archivo a algún tipo de estructura conocida (dbf, mdb...). Tal vez la segunda opción sería más "rentable", aunque a primera vista parezca más difícil.

Lucario448:
Si el tamaño del registro se declara excesivo, esto no sería posible cuando estamos apretados en RAM.

Ten en cuenta que lo habitual es que al menos tengas una estructura de ese tipo para guardar y/o recuperar registros. Puedes utilizar la misma para poner unos datos de índice, ejecutar búsqueda sobre ella y recuperar los datos del registro. Vamos; que es bastante "reciclable".

Lucario448:
Explícate bien esa parte, que de primera impresión me pareció contradictorio.

Si modifico un registro ya existente, entonces podría deliberadamente arruinar el orden (a menos que se esté aplicando un algoritmo de ordenamiento en cada intento). Para evitar la situación anterior, se lanza un error; por lo tanto... ¿no se pueden modificar registros existentes?

Supon que tienes como campos de índice (único, no lo olvidemos) Apellido-Nombre-Teléfono. Creas una función que compare esos tres campos y devuelva mayor, menor o igual. El resto de campos no afectan a la ordenación.
Ahora; recuperamos el registro Zutano-Fulano-12345 y cambiamos su dirección, correo electrónico, etc... Guardamos y sobreescribimos sin problema. Sin embargo, ahora tras recuperarlo modificamos, por ejemplo su nombre: Zutano-Mengano-12345. Esto afecta al índice y potencial posición en la ordenación. Entonces, calcula la nueva posición, modifica el registro y mueve el índice a su posión pero, ¿Y si ya existía previamente un Zutano-Mengano-12345? En ese caso no toco nada y retorno error.

Lucario448:
Este siempre está después del último puntero válido del vector, ¿o no?. Si están mezclados, ¿cómo vas a determinar un puntero inválido?

Porque no están mezclados. En la cabecera indico el número de registros válidos y el de registros borrados. Pongamos que tengo 6 índices a válidos y 3 a borrados. Primero calculo en qué posición tiene que ir el índice. Supongamos que tiene que ir a la posición 3. Miro si hay borrados (sí) tomo el primer índice borrado, que estaría en la posición 6 (posición inicio de índices + 6*sizeof(puntero)). Lo leo y veo dónde apuntaba. Escribo la información donde apuntaba este índice, y a continuación tengo que desplazar el índice borrado desde la posición 6 (primer borrado) hasta la posición 3 (lugar que le corresponde por ordenación). Ya sólo queda modificar la información de cabecera (+1Válido, -1Borrado). Del mismo modo, si borro un registro válido, tengo que desplazar su índice hasta el final de los índices válidos, y alterar la cabecera en sentido inverso (-1válido, +1 borrado). Como digo, estas son las operaciones más "penosas" si hay un gran número de registros. Por ejemplo un desplazamiento de 100000 registros arriba o abajo requeriría desplazar cuatro veces (unsigned long) dicha información.

Lucario448:
Entonces haces crecer el archivo según la demanda; en vez de fijar su tamaño inicialmente.

Efectivamente, va creciendo a demanda. Lo que no hace es decrecer a demanda. Implementé el sistema de mover el primer registro de datos al final cuando necesito más espacio para los índices; pero no implementé el método opuesto; es decir, que si creo mil registros y borro quinientos, la tabla no decrecerá de tamaño, aunque los nuevos registros tampoco la harán crecer mientras tenga borrados que machacar.

Lucario448:
En ese caso se me ocurre que la cabecera acabe en un puntero a la tabla de índices

No es necesario en mi caso, porque la posición de la tabla de índices es fija y conocida, a continuación del header. Si quisieras implementar un descriptor de campos sí tendrías que almacenar de alguna manera el inicio de dicha tabla.

Lucario448:
Para esto tendrías que decidir si los registros deben tener una longitud múltiplo de 4, o la tabla deber ser múltiplo del tamaño de los registros

Los registros pueden tener el tamaño que quieras, siempre que sea fijo. Los índices sí tienen tamaño de cuatro bytes.

Lucario448:
Conviene nunca fragmentarla; de lo contrario la tabla pasará a ser una lista enlazada.

Los índices están consecutivos y ordenados (y a continuación los borrados) y no permito fragmentación. Sin embargo los bloques de datos, aunque consecutivos, están desordenados.

noter:
Ten en cuenta que esto sería interesante si quieres realizar algún tipo de estándar para poder leerlo desde un ordenador o de forma genérica desde otro arduino.

Para algo así serviría, de hecho.

noter:
Puedes utilizar la misma para poner unos datos de índice, ejecutar búsqueda sobre ella y recuperar los datos del registro. Vamos; que es bastante "reciclable".

El problema estaba en que la estructura sí entrara en el código principal, pero no en el atributo del objeto. Mira que al final es reservar espacio, en memoria RAM, para al menos dos estructuras iguales (sólo la operación de obtener un registro por índice no requiere del espacio temporal).

noter:
Sin embargo, ahora tras recuperarlo modificamos, por ejemplo su nombre: Zutano-Mengano-12345. Esto afecta al índice y potencial posición en la ordenación. Entonces, calcula la nueva posición, modifica el registro y mueve el índice a su posión pero, ¿Y si ya existía previamente un Zutano-Mengano-12345? En ese caso no toco nada y retorno error.

Entonces el método de la modificación se basa en: búsqueda (aquí es donde lanzas el error si una coincidencia existe), sobrescritura, y la etapa de ordenamiento de la inserción (salvo que el desplazamiento llega hasta la posición antigua del registro, y su dirección depende de si el nuevo es mayor o menor que el antiguo).

También he notado que lo tuyo no es una lista, sino un conjunto.
Matemáticamente, un "conjunto" se define como una colección de objetos llamados "elementos"; dónde estos no pueden repetirse (o sólo se considera una vez). La repetición consiste en tener al menos dos elementos iguales; la definición de igualdad depende de los elementos en sí. Lo que no recuerdo, es si, en los conjuntos, el "orden natural" de los elementos es relevante o no.

noter:
Por ejemplo un desplazamiento de 100000 registros arriba o abajo requeriría desplazar cuatro veces (unsigned long) dicha información.

Sería interesante poner a prueba esa limitante pero en un entorno más realista.

¿Recuerdas cuando discutíamos sobre el funcionamiento de la librería SD? Según mis cálculos, cada 127 desplazamientos (o 128 índices si se está creando un archivo nuevo) se tiene que actualizar un bloque/sector; tan rápido como SRAM jamás, pero tampoco va a ser estrepitosamente lento.

noter:
Lo que no hace es decrecer a demanda.

Y además la librería no lo soporta, no sin antes realizar el truncado a 0 bytes; aunque técnicamente es posible encoger un archivo existente, sin truncar totalmente ni crear otro.

noter:
Implementé el sistema de mover el primer registro de datos al final cuando necesito más espacio para los índices

Por eso hablaba de un puntero a la tabla de índices; con esa característica ya no se puede asumir que siempre va a estar ubicada contiguo a la cabecera.

Si el tamaño de los registros estuviera "alineado" a la tabla de índices siendo múltiplo de 4 (a nivel estructural del archivo, a nivel lógico sigue siendo el especificado), se podría aprovechar fácilmente el espacio que ocupaba(n) la(s) antigua(s) tabla(s) de índices. ¿No lo habías pensado así verdad?.
Esa es una de las razones por la cuál la tabla de metadatos en NTFS, y los subdirectorios de la raíz en FAT, son archivos; porque cuando son eliminados, reducidos en tamaño o desplazados, ese sobrante se puede aprovechar.

noter:
pero no implementé el método opuesto

Ni te molestes en hacerlo. Para el manejador de volúmenes FAT, hacer crecer un archivo es un trabajo laborioso; por lo tanto, es más eficiente reutilizar espacio asignado que volverlo a asignar. Lo mismo se puede decir de la tabla de índices: cuando urge no queda de otra; pero en la medida de lo posible, evitar reubicar y hacer crecer toda la tabla (ya me imagino el dolor de cabeza que representa ese proceso).

noter:
No es necesario en mi caso, porque la posición de la tabla de índices es fija y conocida, a continuación del header.

Pero si la necesitas expandir... ¿no la mueves del todo? Si me dices que la nueva ubicación es la "segunda parte", estás cometiendo fragmentación; y por ende, forzado a recurrir a la lista enlazada.

noter:
Si quisieras implementar un descriptor de campos sí tendrías que almacenar de alguna manera el inicio de dicha tabla.

Si la longitud del registro está fijada, ¿porqué debería preocuparme por que la composición cambie?
Si asumo que la composición no cambia porque la longitud tampoco, entonces los descriptores perfectamente pueden formar una sección de la cabecera.

noter:
Los registros pueden tener el tamaño que quieras, siempre que sea fijo. Los índices sí tienen tamaño de cuatro bytes.

Eso sí lo sabía. El detalle está cuando se quiere mezclar una cosa con la otra: los espacios (bloques) deben "alinearse" para un acceso siempre homogéneo.

noter:
Los índices están consecutivos y ordenados (y a continuación los borrados) y no permito fragmentación.

Si no permites fragmentación, entonces explica con más detalle qué le ocurre a la tabla de índices cuando tiene que expandirse.

Intento explicar lo de la expansión, porque creo que es donde radica la diferencia de concepto.

BBDD.png776×366 10.6 KB

BBDD.png776×366 10.6 KB

Jeje, usando Excel y todo; con tal de que la representación quede a escala.

Pues más claro no me pudo haber quedado . Tan cierta que es la frase de "una imagen vale más que mil palabras".

Entonces, de lo que acabo de entender: la tabla de índices es inamovible; para hacerla crecer hay que desplazar los registros próximos al final del archivo (lo complicado es buscar a cuál índice le corresponde).

Si se te hace difícil determinar cuándo corresponde repetir este proceso, es porque el tamaño del registro no es múltiplo de 4 (para efectos de almacenamiento en el archivo).
En el peor de los casos se desperdiciarían 3 bytes por registro; pero con tal de que todo esté "alineado", se vuelve mucho más sencillo predecir cuánto espacio se libera por registro desplazado.

Para la lógica de la aplicación, el registro sigue teniendo una longitud arbitraria; sin embargo, para su almacenamiento, debe tener una longitud múltiplo de 4. Dicho en otras palabras: el registro debe ocupar un espacio medido en índices, con redondeo en función techo. Esta sería la forma de calcularlo:

tamanioFisico = tamanioRegistro / 4 + (tamanioRegistro % 4 ? 1 : 0);

Al ser un "valor derivado", es innecesario especificarlo explícitamente en la cabecera, pero sí se puede almacenar como atributo de la instancia para calcularlo sólo una vez en tiempo de creación o apertura del archivo.

PD: ¿me parece a mi, o si el registro es pequeño, cabe la posibilidad de que se ejecute este proceso constantemente?

Bueno. Si ha quedado ilustrativo mereció la pena el esfuerzo de hacerlo en excel ;).
Efectivamente, la tabla de índices está es inamovible. El proceso de aumentar espacio para índices no es difícil de dirimir, ya que tenemos almacenada la posición de inicio de bloques de datos, y sabiendo el número de índices válidos:

  if ( (_head.dataStart - HEAD_SIZE - (FPOINTER_SIZE * _head.filledRecords)) < FPOINTER_SIZE ) {
    _AumentaEspacioIndex();
  }

Evidentemente, para un tamaño pequeño de registro, este proceso se va a repetir con más frecuencia al agregar registros. Incluso ahora me doy cuenta de que si el tamaño registro es menor a cuatro bytes (lo que sería un mal uso de la librería por otra parte) se corromperían los datos al no abrirse suficiente espacio para un índice con una sola operación _AumentaEspacioIndex. La solución sería cambiar if por while, aunque como digo, usar la librería en esa situación sería un contrasentido. En cuanto a localizar el índice correspondiente al registro que vamos a mover, hay que hacer una búsqueda de dicho índice.

noter:

  if ( (_head.dataStart - HEAD_SIZE - (FPOINTER_SIZE * _head.filledRecords)) < FPOINTER_SIZE ) {

_AumentaEspacioIndex();
  }

Ya veo... basta con que la distancia entre último índice de la tabla y primer registro sea menor a FPOINTER_SIZE (supongo que son 4 bytes); también funciona.
Aunque si se hubiera querido, se podría llegar a lo mismo pero con menos cálculos matemáticos; sin embargo no estoy seguro si optimizar eso nos daría un rendimiento significativamente mejorado.

Eventualmente llegamos al punto en donde el rendimiento recae solamente en la RAM; para reducir su consumo, ciertos datos se tendrían que consultar con cálculos matemáticos que posiblemente se tengan que repetir múltiples veces (menor rendimiento). O podríamos hacer que dichos cálculos solo se ejecuten una vez (mayor rendimiento), pero eso implica consumir más RAM.
Al querer optimizar ambas cosas, ahí es donde quedamos "entre la espada y la pared"

noter:
Evidentemente, para un tamaño pequeño de registro, este proceso se va a repetir con más frecuencia al agregar registros.

Entonces habrá que buscar el balance entre el tiempo que se tarda el proceso vs la reducción de la probablidad que se vuelva a ejecutar.

noter:
Incluso ahora me doy cuenta de que si el tamaño registro es menor a cuatro bytes (lo que sería un mal uso de la librería por otra parte) se corromperían los datos al no abrirse suficiente espacio para un índice con una sola operación _AumentaEspacioIndex. La solución sería cambiar if por while, aunque como digo, usar la librería en esa situación sería un contrasentido.

O haces eso, o agregas a la cabecera, el dato del tamaño "lógico" del registro; para forzar los registros a ocupar al menos 4 bytes.

Aunque, según la respuesta anterior, ejecutar un proceso complejo para obtener apenas un índice de espacio, también sería contraproducente.

noter:
En cuanto a localizar el índice correspondiente al registro que vamos a mover, hay que hacer una búsqueda de dicho índice.

Toma en cuenta que hay que buscar incluso en los índices de punteros inválidos; ya que dices que para insertar un registro nuevo, el puntero inválido aún debe apuntar al espacio libre.

Creo que ya me quedó claro: no me molestaré en crear algo que ya existe; lo que noter ha hecho no solo cumple, sino que ha superado mis expectativas de lo que tenía en mente (pero en cierto momento se me había venido una idea similar a la de la tabla de índices en vez de la lista enlazada, solo que él ya la había concretado).
Por supuesto que tiene sus desventajas, que (según la teoría) podrían echarte para atrás; pero su aplicación en un entorno más realista, muy posiblemente no sea gran cosa (y sobre todo si se admiten y reconocen las limitaciones de la implementación).

Donde esta implementación brilla más, es en la operación de búsqueda: si todos los elementos (registros) están posicionados según la definición del ordenamiento, se puede aplicar el algoritmo de la búsqueda binaria; la cuál presenta un buen rendimiento incluso en listas/conjuntos relativamente grandes.

PD: ahora que lo pienso, si en la operación de sobreescribir un registro no puedes permitir que hayan dos "iguales" (por definición), ¿será que en la operación de inserción tampoco?

Toma en cuenta que hay que buscar incluso en los índices de punteros inválidos; ya que dices que para insertar un registro nuevo, el puntero inválido aún debe apuntar al espacio libre.

Por una parte me has demostrado que has entendido perfectamente el funcionamiento de la librería. Por otro lado... ¡Houston! ¡Tenemos un problema! Habrá que buscar una solución razonable, aunque tal vez suponga un cambio profundo en algún planteamiento.

PD: ahora que lo pienso, si en la operación de sobreescribir un registro no puedes permitir que hayan dos "iguales" (por definición), ¿será que en la operación de inserción tampoco?

Por supuesto; entendiendo dos registros iguales los que sean así considerados por la función de comparación. Visto como base de datos, que tengan misma clave primaria. De hecho la operación de inserción es donde primero verificaba ese punto. Con las modificaciones, la primera opción fue que si alteraba el índice, devolvería error; pero después pensé que entonces rectificar un registro afectando algún campo de la clave requeriría eliminarlo y volver a crearlo, así que opté por permitir dicha modificación comprobando primero la no duplicidad.

Gracias por tu atención, Lucario. Respecto del bug que has descubierto, si tienes alguna idea, será muy tenida en cuenta.

Saludos.

noter:
Respecto del bug que has descubierto, si tienes alguna idea, será muy tenida en cuenta.

¿Cual de todos? ¿El de los registros menores a 4 bytes? ¿El de desplazar punteros inválidos?

Evidentemente al segundo. El primero, además de que hay que hacer "mal uso de la librería" para provocarlo, pues usarla con registros menores de cuatro bytes es un contrasentido; es muy fácil de salvar sin grandes modificaciones.