Perdona, que se me había traspapelado la respuesta a esto. El código está todo en la propia librería. Las declaraciones en FDB.h y las definiciones en FDB_DEF.h (no funciona con las plantillas el hacer la definición en un .cpp).
En cuanto al "problema" que se nos había planteado, lo he tenido que "rememorar" y era:
Cuando necesitamos espacio para nuevos índices, movemos el primer bloque de datos al final, y hay que indicar la nueva ubicación al índice que lo apuntaba. Para localizar dicho índice hay que lanzar una búsqueda. A lo que agregaste, que hay que buscar también entre los inválidos (que para más complicación no están ordenados). Peeeeeero.... nos habíamos olvidado que, precisamente, si recurrimos a la acción de desplazar bloque de datos para ubicar nuevos índices es porque previamente hemos "fulminado" todos los índices inválidos (registros "borrados") disponibles y no nos queda ninguno que aprovechar.