Сохранение древовидной структуры в файл, best way?

Question

[Илья Павловский]

Всем доброго дня, столкнулся с проблемой выбора структуры данных и файла для хранения N-дерева.
Обьект, по факту из себя представляет из себя следующее:

class Node{
   int data;
   Node[] childArray;
}

Вот и столкнулся с проблемами:
a) Такая структура, как обьект в памяти, при количестве узлов от ~10^6, потребляет изрядно памяти ОЗУ. При переделке обьекта на примитивы и работы уже с массивом данных со смещениями, проблема решается и память не так сильно кушается(примерно раза в 3-5). т/е/ что-то подобное:

int node = 0b1111111111_00000000_11111111;
// 1ые 8 бит отвечают за данные
// 2ые 8 бит child_size
// 3ие 8 бит информируют о необходимом смещении в массиве, чтобы дойти к следующему элементу на текущем уровне

б) Запись дерева в файл. При сохранении обьекта в XML / JSON на выходе получаем весьма весомый файл от 50мб при N=~10^6. При создании собственного велосипеда и переделки дерева на линейную запись в файле, получаем весьма удвлтворительный вариант с 6-8мб на выходе, но появляется проблема с масштабируемостью. Т/е/ для добавления произвольного узла в дерева, следует пройтись по всем узлам для коррекции смещений узлов в файле и перезаписать. Существуют ли непрожорливые форматы данных для хранения N-нарного дерева с возможностью масштабирования?

Answer 1

[nirvimel]

для добавления произвольного узла в дерева, следует пройтись по всем узлам для коррекции смещений узлов в файле и перезаписать.

Это в любом случае неизбежно. Единственно что можно сделать для сокращения дискового I/O - это, вместо записи множества кусков (через seek->write->seek->write), использовать встроенные в ОС механизм memory mapping (в Java он реализован через MappedByteBuffer), тогда проблема оптимизации кеширования и сброса буферов на диск ложится полностью на ОС.

Comments

[Илья Павловский]

Спасибо за совет, проблему прохода по всему дереву действительно можно решить относительным смещением и таким образом сократить проход по дереву не до TreeSize а до глубины вставляемого узла.

А встречный вопрос - т/е/ обработку файла делать через потоковое чтение со смещениями или же выгружать весь файл в память и там работать со смещениями, т/е/ вопрос такого характера - насколько по скорости это будет более затратно(работа с файлом через поток) чем с памятью?

[nirvimel]

Илья Павловский: Если читать весь файл (или большой его кусок) целиком за один вызов, то скорость будет одинаковая. Но когда нужно работать с мелкими фрагментами (вплоть до байт), то, чем больше мелких операций, тем значительные преимущество memory mapping над seek->reed операциями. Еще значительнее разница в скорости при записи. Вообще memory mapping создан для произвольного доступа (random access) на скоростях доступа к памяти (а не дискового I/O), то есть можно обновлять древовидные структуры и писать на лету в MemoryByteBuffer мелкие изменения во множество разных мест в файле на огромной скорости не дожидаясь дисковых операций, ОС потом сама скинет буфера на диск когда ей удобно.