Хранение и работа с тегированным деревом записей

[shau-kote]

Всем доброго времени суток.

Возникла у меня при написании одной программы, тривиальная, казалось бы, задача.
Есть довольно большое количество некоторых записей. Текстовое значение, потенциально текстовые же параметры.
Необходимо из них организовать в дерево (т.е. дать возможность пользователю их организовывать в дерево), и, к тому же, дать тому же пользователю на каждый элемент навесить произвольное количество тегов.
Соответственно, необходимо эту структуру как-то хранить (как в памяти, так и на диске), и как-то с ней работать - производить поиск записей, поиск по набору тегов, получать список всех тегов etc. Причём желательно производить все операции максимально быстро и эффективно даже при большом количестве записей.

И если вопрос сохранения не вызывает у меня особых сомнений - JSON:

Используется синтаксис Javascript

[ ...
    {
        "value": "foo",
        "param1": "bar",
        "param2": 13,
        "path": "/dir/dir2",
        "tags": [ "tag1", "tag2", "tag3" ]
    }
...
]
 

То вот со всем остальным я нахожусь в некотором затруднении. Можно, конечно, считать JSON в аналогичную структуры и перебором искать по ней, но скорость такого решения будет оставлять желать лучшего.
Почему я говорю, что задача вроде бы тривиальная? Просто подобное хранение данных довольно распространено. Те же блог-движки подобным образом хранят заметки в блоге. Однако я нигде не смог неайти информации по реализации подобного хранения данных.

Буду очень благодарен, если более опытные форумчане подскажут, "куда рыть".
Спасибо.

[Xaositect]

shau-kote в сообщении #740538 писал(а):

Просто подобное хранение данных довольно распространено. Те же блог-движки подобным образом хранят заметки в блоге. Однако я нигде не смог неайти информации по реализации подобного хранения данных.

В базе данных их хранят. Можно в реляционной (таблица для статей, таблица для тэгов, таблица для отношения предок-потомок в дереве, таблица для отношения статья-тэги), можно в документо-ориентированной - там что-то более близкое к JSON.

[Joker_vD]

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

Хранить же в текстовом виде... большой объем данных, который руками из текстового редактора все равно править не придется... как вы представляете себе процедуру "перейти к следующей записи"? В обычных БД это что-то вроде "увеличить счетчик на размер записи, если вышли за пределы загруженной страницы — догрузить с диска следующую страницу, выгрузить нынешнюю". В вашем же случае это "парсинг на лету". Это сложно, я пытался когда-то делать нечто подобное, чтобы не держать в памяти все дерево разбора — но решил, что проще и эффективнее будет использовать имеющиеся СУБД. Если же вы можете себе позволить держать в памяти всю распарсенную структуру — ну, ради бога. Парсьте целиком, но если вам нужен эффективный поиск, то вам от индексации не отвертеться.

[shau-kote]

Xaositect, да, пожалуй, если взять маленькую документо-ориентированную СУБД (наподобие Mongo, только поменьше и в виде "движка", а не сервера), то может получится весьма неплохо.
Единственное, что смущает, что хороших маленьких движков таких не особо найдёшь.

Joker_vD, безусловно, при загрузке данных в память необходимо их как-то более хитро организовывать, строить индексы, деревья для поиска. Собственно, мой изначальный вопрос и был в области подобных структур/алгоритмов.

[Joker_vD]

"Все уже украдено до нас". Я вас уверяю, возьмите SQLite3, набросайте реляционную БД по советам Xaositect, сформулируйте, какие запросы/действия вы хотите выполнять с вашими сущностями, переведите это на язык SQL, подумайте, какие индексы стоит построить. Все, в принципе.