La librería ya esta hecha @AnyPopins y se llama EDB Extendend Data Base
Te dejo sus características en inglés off course
This Arduino Extended Database Library increases the maximum number of records allowed in a database from 256 records (byte) to a theoretical maximum of 4,294,967,295 records (unsigned long). The maximum record size was also increased from 256 bytes (byte) to 65,534 bytes (unsigned int).
You may use this library in conjunction with the standard Arduino EEPROM library, an external EEPROM such as the AT24C1024, or any other platform that supports byte level reading and writing such as an SD card.
El proyecto no ha recibido actualizaciones desde 2017 por lo que ten cuidado si lo usas con el IDE y los errores que ocacione, mi consejo, usa un IDE no mas alla de 2019. Los mas actuales pueden generar problemas pero con probar no se pierde nada.
En los ejemplos tienes desde SD, hasta EEPROM de 1MB como la AT24C1024 asi que cubre con creces tus necesidades y te facilita todo el trabajo.
Los ejemplos son muy simples de usar/entender.