Представим, что есть массив из 8 элементов (может быть больше/меньше), каждый элемент - строка произвольной длины.
Каким образом можно его записать в файл таким образом, чтобы в дальнейшем можно было, скажем, убрать элемент с индексом 4. Или изменить строку, которая там содержится.
Нужен вариант, который обеспечит максимально быстрое чтение и надежную запись (в плане - без потерь данных, хоть и медленную)...
Как я это вижу:
будет 2 файла, первый - непосредственно данные, а второй файл - маппинг, который содержит в себе инфу о том, с каким смещением начинается строка в файле и какой размер она имеет.
Также в планах разбить файл с данными на блоки по 16 байт и во втором файле хранить только ID записи и блоки, в которых она записана.
То есть, получается 1 файл с данными: db.dat и db.map
Первый размечен на блоки по 16 байт
Второй файл содержит recordId + blockOffsets
Далее вычитывается ID записи и выбираются нужные смещения блоков, далее fopen(db.dat) и вычитываются эти блоки и строка конкатезируется в исходную. При перезаписи - сносятся блоки и аллоцируются по новой... Возможно необходимо сохранять пустые блоки в файле... При этом варианте получается, что если ID заранее известен - скорость чтения будет нормальная, но если читать все строки сразу, будет беда.. А особенно, если их удалять из базы..то блоки пустые останутся, а это влияет на размер файла... В общем, помогите, плиз)
Готовые варианты (SQLite) не предлагайте плиз, нужен свой велосипед.
Исходя из задачи:
Вы храните KEY - VALUE. Нам заренее не изветен ни KEY (тип и формат данных - строка или число) ни VALUE (его размер)
1) так как запрос на "чтение\запись" будет идти по ключу - высчитываем хеш ключа (sha256), берем несколько "октет" (у меня они так в голове называются) от хеша и дописываем\создаем файл с таким именем (это будет наш индекс ключей)
2) пишем VALUE в преобразованном формате (base64 или еще как) в файл данных в строку соотвествующую следующему индексу
Получается следующий фарш:
--------------
Создание записи:
Принмаем что БД пуста.
KEY = test
VALUE = datastring
HASH = sha256(KEY) = 9f86d081884c7d659a2feaa0c55ad015a3bf4f1b2b0b822cd15d6c15b0f00a08
OCTET = HASH[1-6] = 9f86d0 (три пары)
файл индекса = [OCTET].map (mapper)
файл последовательности записи = [OCTET].pnt (pointer)
файл данных = [OCTET].dat (data)
Читаем:
PNT (последовательный указатель - номер строки в файле данных) = read([OCTET].pnt)+1 = 1
Пишем:
[OCTET].map =>
9f86d081884c7d659a2feaa0c55ad015a3bf4f1b2b0b822cd15d6c15b0f00a08 = [PNT]
[OCTET].pnt = [PNT]
[OCTET].dat[PNT] = VALUE (предварительно преобразовываем - base64 или иное) = Пишем в строку равную PNT в файл [OCTET].dat - это сразу дает и запись и обновление данных
--------------
Чтение записи:
KEY = test
HASH = sha256(KEY) = 9f86d081884c7d659a2feaa0c55ad015a3bf4f1b2b0b822cd15d6c15b0f00a08
OCTET = HASH[1-6] = 9f86d0 (три пары)
файл индекса = [OCTET].map (mapper)
файл данных = [OCTET].dat (data)
Читаем файл [OCTET].map и ищем HASH = получаем указатель строки в файле данных = PNT
Читаем файл [OCTET].dat[PNT] (читаем строку PNT) = VALUE (преобразовываем в исходный формат)
=============
Думаю, если даже моя идея бред - то по крайней мере даст вам почву для размышления.
PS\ как более оптимальный вариант - хранить каждый блок данных в отдельном файле с именем = хешу от ключа.
Еще раз прочитал что написал Я и автор - у меня вариант построчного хранения, что конечно выходит за суть проблемы\вопроса автора.
Тогда делаем так: в mapper пишем попарно два указателя старт и длинна записи, при этом таких указателей может быть много: 0,100,500,20 = что говорит что данные находяться с 0 байта длинной 100 и с 500 длиной 20 (дефрагментация данных - как на дисках). Это позволит писать новые данные в конец файла, а в случаи обновления записи - заполнять ранее занятое место и писать опять в конце. Так же можно вести маппинг освобидившихся мест и использовать их повторно.
ЗЫ ну и конечно нужно думать о дефрагментации что бы собирать данные в целое (например отдельный метод который будет это делать во время простоя БД, или по пинку пользователя)
я не могу сделать так как вы предлагаете, необходимо сохранять бинарно.... В примере 8 строк, на деле будет 18.4 млн
Сам элемент массива и представляет сериализованный в JSON объект... Просто их нужно как-то сохранить в файле так, чтобы была возможность их изменения и удаления в дальнейшем.
Просто представте, был элемент 10 байт, его изменили и он стал 17 байт... Как сдвинуть содержимое всего файла, чтобы получить еще 7 байт на сохранение?... а никак, поидее..
Если дописывать в конец файла, то получается 10 байт там будут стоять себе забитые нулями и жрать размер файла неоправданно...
Или же был размер 500 байт, строку изменили, теперь она 5 байт
Куда девать 495 байт файла? по сути, туда ведь можно еще писать инфу
В файл пишете блоки определенного размера (например 2-4 Мб). В блок пишете:
1.байт флагов записи (флаг удаления записи или признак конца блока)
2.ID записи фиксированного размера
3.длину последующей строки фиксированного размера
4.строку данных
так до конца блока, в конце блока в п.1 выставляете признак конца блока и смещение следующего блока фиксированного размера.
Можно сделать так, что бы блок забивался до отказа, а остатки последней записи, которая не влезла в блок переносить в другой блок, можно оставлять пустые куски блоков. Кроме того этот механизм будет необходим, если 1 запись может быть размером больше 1 блока.
При добавлении записи - добавляете в конец последнего блока (так же можно искать блок с необходимым количеством свободного места в конце), если места не хватает, добавляете новый блок.
При удалении записи - выставляете флаг удаления.
При изменении записи - существующую удаляете, новую добавляете.
Почему нужно работать с большими блоками - так гораздо быстрее читать/писать - сразу целый блок, даже если вам нужна одна запись из него.
Кроме базового функционала нужно предусмотреть операцию сжатия, которая бы физически удаляла удаленные записи.
Для быстрого поиска нужен индексный файл. Индекс содержит в себе отсортированный список ID и адрес блока и смещение в блоке записи.
Так же можно индекс и данные объединить в один файл.
Для этого нужно предусмотреть заголовок файла, содержащий смещение первого блока данных и смещение первого блока индекса.
В заголовке можно держать смещения не только первых блоков, но сделать таблицу блоков данных и таблицу блоков индексов, конечно фиксированного размера. В конце заголовка смещение на блок следующего заголовка.
При старте вам нужно будет полностью прочитать индекс, а данные по мере необходимости.
При изменении записи, меняете блок в памяти и целиком его перезаписываете по тому же смещению где он и находился в файле.
В блоке можно предусмотреть заголовок блока, в который можно писать служебную информацию, например было бы полезно писать туда размер свободного места в конце блока.
Может быть что-то еще.
PS: не стоит изобретать велосипед, возьмите готовую СУБД.
Простой
