Hola.
Gracias por la colaboración. Respecto de tus preguntas, te respondo.
La librería guarda los datos en formato binario. Hay que definir una estructura que representará los datos de un registro, pudiendo ésta contener cualquier tipo de dato numérico o array de datos de tamaño definido. Hay que tener en cuenta que no debes incluir en tu estructura punteros, pues sólo guardará el propio puntero y no los datos a los que apunta; es decir, que para cadenas por ejemplo deberás declararlas en formato char cadena[LONGITUD_FIJA] (guardará LONGITUD_FIJA caracteres) y no en formato char *cadena (sólo guardaría los dos bytes que apuntan a la cadena). Respetando esto, creo que tiene capacidad para guardar estructuras de datos complejas (subestructuras, arrays, etc...).
Está pensada (otra cosa es que cumpla lo esperado

) para gran cantidad de registros y/o tamaño grande de registro; por lo que para cien usuarios (salvo que se guarden muchos datos por usuario) tal vez no notes beneficio con respecto al acceso secuencial, y sí notes retraso en la escritura de un nuevo registro (no es lo mismo escribir directamente al final del archivo que andar buscando, recolocando y escribiendo datos de un lugar a otro para mantener el orden. Todo es cuestión de probar en cada caso y usar lo que mejor convenga.
Respecto a lo de quitar la indexación, es precisamente la parte que me ha dado casi todo el trabajo. Para guardar estructuras sin indexar, te puede valer la
Extended Database Library, aunque requiere una pequeña adaptación para utilizarla con SD (inicialmente estaba pensada para EEPROMs y demás). No obstante miraré si puedo sacar una versión "downgraded" (sin índices).