Можно и в одном файле.
В файл пишете блоки определенного размера (например 2-4 Мб). В блок пишете:
1.байт флагов записи (флаг удаления записи или признак конца блока)
2.ID записи фиксированного размера
3.длину последующей строки фиксированного размера
4.строку данных
так до конца блока, в конце блока в п.1 выставляете признак конца блока и смещение следующего блока фиксированного размера.
Можно сделать так, что бы блок забивался до отказа, а остатки последней записи, которая не влезла в блок переносить в другой блок, можно оставлять пустые куски блоков. Кроме того этот механизм будет необходим, если 1 запись может быть размером больше 1 блока.
При добавлении записи - добавляете в конец последнего блока (так же можно искать блок с необходимым количеством свободного места в конце), если места не хватает, добавляете новый блок.
При удалении записи - выставляете флаг удаления.
При изменении записи - существующую удаляете, новую добавляете.
Почему нужно работать с большими блоками - так гораздо быстрее читать/писать - сразу целый блок, даже если вам нужна одна запись из него.
Кроме базового функционала нужно предусмотреть операцию сжатия, которая бы физически удаляла удаленные записи.
Для быстрого поиска нужен индексный файл. Индекс содержит в себе отсортированный список ID и адрес блока и смещение в блоке записи.
Так же можно индекс и данные объединить в один файл.
Для этого нужно предусмотреть заголовок файла, содержащий смещение первого блока данных и смещение первого блока индекса.
В заголовке можно держать смещения не только первых блоков, но сделать таблицу блоков данных и таблицу блоков индексов, конечно фиксированного размера. В конце заголовка смещение на блок следующего заголовка.
При старте вам нужно будет полностью прочитать индекс, а данные по мере необходимости.
При изменении записи, меняете блок в памяти и целиком его перезаписываете по тому же смещению где он и находился в файле.
В блоке можно предусмотреть заголовок блока, в который можно писать служебную информацию, например было бы полезно писать туда размер свободного места в конце блока.
Может быть что-то еще.
PS: не стоит изобретать велосипед, возьмите готовую СУБД.
