Как лучше хранить рекурсивные структуры?

Ну тебе просто нужно идти в ширину по дереву и вместо указателей в файл писать уникальный id узла и id родителя - генерировать id по мере обхода дерева. При загрузке - заведи себе словарь вида {id, *Tree}, при создании нового узла в памяти пиши в словарь его id и в нём же ищи по id указатель на родителя. Как всё загрузишь - словарь можно грохнуть.

А как лучше? Писать в один файл, при каждом запуске программы загружать его в память? Или разбивать по большому количествую мелких файлов, например <id>.json и хранить в директории. Правда тут можно столкнуться с ограничением на количество файлов.

В первом случае один большой файл сложнее будет апдейтить

Может просто превратить его в lisp (рекурсивно обходя DFS'ом), а потом собрать обратно, при каждой новой скобочке создавая нового child'а. Тут пример: https://www.geeksforgeeks.org/construct-binary-tree-string-bracket-representa... (только по-моему это можно сделать проще).

Для упрощения может описать дерево так? Или сконвертировать его на такой формат (а потом при десериализации можно обратно).

template<class PayloadPlusIdPlusWhatever>
struct Tree {
    PayloadPlusIdPlusWhatever data;
    ListOrVectorOrWhatever<Tree*> children;
}

string tree_to_string(Tree *)
   sstream s;
   ss << data;
   for (Tree* child: children) {
       ss << "("
       ss << tree_to_string(child);
       ss << "(";
   }
   return ss.to_str();
}

Псевдокод десериализации:

// this is pseudocode, don't care about leaks or whatever
// call with curr != null but an allocated root
Tree* string_to_tree(string s, Tree *curr=null)
{
    string data_or_bracket = get_and_remove_data_or_bracket(s);
    if (is_data(data_or_bracket) && curr != null)
    {        
        curr->data = data_or_bracket;        
    }
    else if (is_opening_bracket(data_or_bracket) && curr != null)
    {
        Tree* t = new Tree();
        curr->children.push_back(t);
    }
    else if (is_closing_brackest(data_or_bracket)
    {
        return;
    }
    string_to_tree(s, curr);
}

Disclaimer: не тестировал и даже особо не думал.

PS Если важно, чтобы данные выглядели именно так как выглядят и жалко памяти создавать временные структуры где есть parent и список детей, тогда наверное придется писать как есть, т.е. {id,parent_id},{id,parent_id}, но тогда с другой стороны десериализация будет требовать дополнительных структур как показал MetalBeaver.

PS Если пернул в лужу и это не устраивает требованиям «при учете, что записей может быть неограниченное количество. Например больше миллиона, а так же параметр Payload может меняться» то сорри.

Просто lisp это дерево.

А парсер lisp'а это банально.

Превратить дерево в lisp тоже банально.

Код Прюфера

Мда.. Все гениальное просто.

А я знаю, почему так. Просто в 1918, да и в 1932, да и в 1961 тяжелые наркотики свободно продавались а аптеке, а за тунеядство отправляли в Сибирь или расстреливали. Отсюда и код Прюфера и взлом энигмы и полет человека в космос.

ну и зачем он тут нужен? Это последовательность из тех же самых (n-2) айдишников, так что по занимаемому месту мы не выиграем (по сравнению с банальным «хранить id предка»), только увеличим сложность сериализации/десериализации

Или разбивать по большому количествую мелких файлов

Тогда тебе и айдишники сохранять не надо, просто создавай иерархию каталогов и файлов по образу и подобию твоего дерева, но...

Например больше миллиона

За миллион файлов тебе никто «спасибо» не скажет. В том числе твоя ФС.

Писать в один файл

Я бы писал в БД, если есть такая возможность. Если нет, то - в один файл.

а так же параметр Payload может меняться

На сколько он может меняться? Есть ли вменяемая верхняя граница? Если да, то можно пожертвовать местом ради удобства и скорости обновления... про него, кстати, в исходной задаче ничего сказано небыло:

В первом случае один большой файл сложнее будет апдейтить

пожертвовать местом ради удобства

Я имею в виду под каждый узел выделять фиксированный блок в файле.

Я бы писал в БД, если есть такая возможность.

поддерживаю и уточню: специализированную иерархическую, а не типичную РСУБД

специализированную иерархическую

Например какую?

Вообще я хотел исключить БД из проекта. У баз данных есть проблемы:

1. Пол проекта будет находиться в базе данных - а это не нужное прибивание гвоздями к левому продукту.

2. Базы данных, если не встраиваемые, как правило требуют отдельного от проекта разворачивания, конфигурирования, обслуживания и т.д.

3. Нарушается логика проекта. Если в простом случае я могу обратиться к «родителям» на прямую: Tree.Parent.Parent.Payload - то в случае с БД придется заворачивать это в функции типа Tree.GetParent().GetParent().Payload , а если приводить к нормальному виду - то все равно придется весь объем данных сериализировать/десериализировать и нафиг тогда база данных?

За миллион файлов тебе никто «спасибо» не скажет. В том числе твоя ФС.

В ext4 нет ограничения на кол-во файлов в директории, а максимальное кол-во файлов в системе гораздо больше миллиона, да еще и расширить можно в конфиге ядра

Я имею в виду под каждый узел выделять фиксированный блок в файле.

Хмм, а вот это вполне себе вариант

Хотя не вариант, размер payload может быть вообще разным

Например какую?

Не могу подсказать лучшую, создайте отдельный топик. Вроде, ArangoDB неплоха.

Пол проекта будет находиться в базе данных

ну так не надо так делать

а это не нужное прибивание гвоздями к левому продукту.

написание велосипедов приводит к неоправданному росту трудозатрат

требуют отдельного от проекта разворачивания

это минус, да

Tree.Parent.Parent.Payload - то в случае с БД придется заворачивать это в функции типа Tree.GetParent().GetParent().Payload

если это и нужно (зачем-то) беда небольшая как по мне, благо придумали ORM

нафиг тогда база данных

чтобы с ФС не возиться

размер payload может быть вообще разным

Это весьма паршивая постановка задачи. Поясни, насколько разным он может быть? Есть минимальное/максимальное значение его размера? Можно ли предположить, что будет перевес в какую-то сторону: например, 99% будут до 255 байт, или что-то типа того? Потому что, если известно, что, например, лишь 1% будет огроменным, то его можно вынести в отдельный файл или что-то типа того. Короче, подкинь какой-нибудь инфы насчёт этого payload.

https://github.com/boltdb/bolt

Вот уж чего-чего а это поделие на колбеках советовать не надо.

Поясни, насколько разным он может быть?

От нескольких килобайт, до нескольких мегобайт. По сути в пейлоаде будут храниться медиа-материалы.

то его можно вынести в отдельный файл или что-то типа того

А вот это пожалуй правильно, если вынести в отдельный файл - то пейлоад просто заменю на ссылку на файл. Но с другой стороны опять приходим к директории с файлами

Вроде, ArangoDB неплоха.

Ага, вроде не плохая, только вот библиотека у нее написана инопланетянами для инопланетян.

Вообще если смотреть графовые базы данных - то лучше уж Neo4j, но оно все на Java а это довольно ресурсоемко.

написание велосипедов приводит к неоправданному росту трудозатрат

Не согласен. Порой изучение чьего-то левого «изделия №1» приводит к не менее большим трудозатратам. Особенно когда на пол пути реализации проекта узнается, что «изделие №1» не умеет нужной фичи, или не соответствует требованиям и приходится к нему приделывать костыли. От чего проект и прибивается гвоздями к ненужному поделию. А мне всего-то нужно консистентно хранить и апдейтить инфу

Я бы попросил аргументировать против него, но да ладно, дело твоё.

Я, просто, не знаю других key/value БД на Go с неймпейсами. А это то, что тебе нужно.

Два неймспейса, в одном ID: Payload, а в другом ID: ParentID, ну мб ещё третий под стартовый ID и всякие флаги. Что складывать удобно, что извлекать, абсолбный минимум кода, костылей и велосипедов.

Я бы попросил аргументировать против него

А что тут аргументировать? Любители колбеков пусть на JavaScript кодят, мне нужен нормальный читаемый код.

sqlite

Так себе обоснование. Ты бы лучше оценил практическую сторону этого решения и потенциальную скорость работы.

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

Наркоман штоле.

Я бы попросил аргументировать против него, но да ладно, дело твоё.

Если тебе самоу влом, могу даде заморочиться и набросвть тебе прототип.

Спасибо, но не нужно. У меня не тот кейс, чтобы возможная потенциальная скорость работы превышала читаемость кода. Колбеки - это зло и если их пытаются пихнуть туда, где они не нужны - то такие продукты я не использую.

sqlite

Может еще mssql посоветуешь?

сам наркоман

{id, parentid, data} + иерархические запросы

хочешь кольца - {id, leftid, rightid, data} и выбирай только по уникальным id

Оверкилл. Надо хранить жирные блобы, извлекать будет либо неудобно, либо медленно. Можно, конечно, хранить не данные, а имена файлов, но это костыльно.

Можно, конечно, хранить не данные, а имена файлов, но это костыльно.

а, вот, некотрые большие системы документооборота так не считают

Ибо там действительно нужна реляционная бд, а здесь нет.

{id, parentid, data} + иерархические запросы

хочешь кольца - {id, leftid, rightid, data} и выбирай только по уникальным id

Как лучше хранить рекурсивные структуры? (комментарий) пункт №1

Ибо там действительно нужна реляционная бд, а здесь нет.

откуда ты знаешь, ты же не ТС?

реляционные БД - это унификация структур, автоматическая верификация (реляции), неограниченное количество регулярных данных, оптимизированные процедуры поиска и детерминированное время запроса

или это всё опять «фатальный недостаток»?

Можно, конечно, хранить не данные, а имена файлов, но это костыльно.

до 100кб можно хранить и в блобе (какие там у тса требования?)

https://www.sqlite.org/intern-v-extern-blob.html

пункт №1

удачи

откуда ты знаешь, ты же не ТС?

Ты топик вообще читал?

До мегабайт, миллионы записей.

Кто-то мешает делать DB.Begin() + Tx.Commit()/Tx.Rollback() вручную?

Я в свое время запилил свой бинарный формат. Он умеет всякое в бинарь конвертить. На гитхабе в моих репах найди go-llsn реализацию.

Во, сам нашел https://github.com/allyst/go-llsn . Там же есть тест, в нем смотри как пользоваться

Описание тут http://allyst.org/opensource/llsn/ru/

Какие нафиг иерархии? Какое дерево? Это односвязный список.

Да щё ви говорити

https://play.golang.org/p/k1WMzl6YF-U

Вот от незнания структур, такой треш и пишут. Гнать ссаными тряпками.

Хотя никнейм ТС как бы не отрицает.

Вот от незнания структур, такой треш и пишут. Гнать ссаными тряпками.

Обычно в РСУБД деревья именно так и хранят.

Обычно в РСУБД деревья именно так и хранят.

ТС вроде как это не в бд хранит. С таким подходом все действия кроме доступа к родителю очень медленные.

Если ничего кроме доступа к родителю не нужно, то можно и так, но вчера это было не нужно, а сегодня стало нужно, и пока ТС переписывал, его уволили за профнепригодность.

А что там гениального?

Много воды мало советов. Что подчеркивает твою полную некомпетентность в купе с «Какое дерево? Это односвязный список.»

Будешь дальше воду лить, или блеснешь своими подзнаниями, если такие вообще имеются?