LINUX.ORG.RU

Дерево с быстрым доставанием родителей ноды

 , , математика.,


0

2

Дерево произвольного количества нод на каждой ветке. Допустим, у каждой ноды есть какой-то набор какого-то добра, т.е. добро ноды на уровне k + 1 состоит из ее добра и добра всех ее предков.

Еще нужно эту структуру хранить как какую-то персистентнуюю опердень, но нет условия на конкретную реализацию - т.е., если будет удобно в mysql, то mysql, если имеется какое-то дерево, которое может быть персистентным, было бы отлично. Еще (опционально) было бы неплохо иметь возможность шардить.

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

(добавил в теги «математика», ибо математики обычно и подстказывают годные идеи, но если вас зацепило - простите)

★★★★★

Последнее исправление: cdshines (всего исправлений: 1)

Дерево — одна из наиболее широко распространённых структур данных в информатике, эмулирующая древовидную структуру в виде набора связанных узлов. Является связанным графом, не содержащим циклы.

Более одного родителя это ведь цикл ?

hidden_4003
()
Ответ на: комментарий от hidden_4003

Я некорректно сказал - имелось в виду «всех предков при уловии, что на каждом уровне один предок». Вношу исправления.

cdshines ★★★★★
() автор топика

OODB? Когда-то были популярными. Может быть, и сейчас используются в системах CAD/CAM, но это - не моя область.

dave ★★★★★
()

В нормальных базах есть рекурсивные запросы, одним запросом достанешь всех предков, если это единственное, что тебя не устраивает в самом простом и наглядном способе хранения.

Legioner ★★★★★
()
Ответ на: комментарий от cdshines

Про мускуль не знаю, погугли, постгрес, оракл и дб2 точно умеют.

А на СО фигню написали. Все хранят в реляционных базах иерархию и никаких особых проблем не возникает.

http://stackoverflow.com/questions/4048151/what-are-the-options-for-storing-h... тут ещё поботай, он там много способов написал разных, Nested Sets любопытный, возможно подойдёт, сейчас вспоминать, как он устроен, не хочу.

Legioner ★★★★★
()
Ответ на: комментарий от cdshines

в постгресе есть (также можно разрулить анонимной или не очень процедурой),

с другой стороны, если ноды жирные, то как вариант отделить структуру от данных - отдельно таблица nodes с (id, data) отдельно structure (id, parentId) и тут, значит финт ушами - таблицу structure грузишь одним запросом в память и там выбираешь что тебе хочется, выборка данных по вкусу - запросами с кешированием, генерацией временных таблиц или как еще, зависит от объемов данных

с другой стороны http://www.codeproject.com/Articles/521713/Storing-Tree-like-Hierarchy-Struct...

Deleted
()
Ответ на: комментарий от Legioner

Все хранят в реляционных базах иерархию и никаких особых проблем не возникает.

Эти убогие все в реляционках и произвольные объекты хранят, графы и все что угодно, а потом это пыхтит и тормозит, просто альтернативы нема 8)

Deleted
()
Ответ на: комментарий от Deleted

Там и так от нод отделены сущности, которые юзают их пейлод. В ноде лежит строка, по сути. Я вот раздумывают над чем-то типа nested sets, ибо как раз же такая функциональность. Тогда У меня чем ниже нода в дереве, тем она представляет собой большее множество (много добра), и ее родители имею его меньше, поэтому они как бы ее вложенные подмножества. Но тогда встает проблема с хранением вообще всего множества (дерево здесь уже никуда не налазит вообще), а также с переносами. Но если подобрать подходящее представление, то это будет просто. Только я не могу его подобрать:/

Может, jackrabbit?

cdshines ★★★★★
() автор топика
Ответ на: комментарий от Deleted

Насколько я понял из сказанного - совершенно произвольный, т.е. такое дерево может быть вообще поставлено в соответствие ФС (не факт, что просто локальной) (в смысле, по ноде на файл). И да, желательно еще иметь хотя бы базовые возможности для шардинга или какого-то другого способа масштабировать.

тоже субд

Так мне не обязательно не пользоваться обертками.

cdshines ★★★★★
() автор топика
Ответ на: комментарий от Deleted

https://wiki.apache.org/jackrabbit/PersistenceManagerFAQ

Jackrabbit uses the org.apache.jackrabbit.core.fs.FileSystem interface as a file system abstraction.

Вот, я посмотрел - там есть обертки поверх дерби, оракла и т.д. Думаю, там свелосипедили получше, чем я смогу. По крайней мере, у ноды есть метод getParent() :), и я не думаю, что если я напишу что-то вроде того, что ниже, оно развернется в 100500 вызовов к бд на каждую ноду.

for(Node pNode = currwntNode; !pNode.hasParent(), pNode = pNode.next() {
    nodes.add(pNode);
} 

Можно потестить, в любом случае.

cdshines ★★★★★
() автор топика
Ответ на: комментарий от Deleted

В некоторых модулях проекта уже есть MySQL, не думаю, что все будут рады видеть мою инициативу по повышению гетерогенности)

cdshines ★★★★★
() автор топика

Уж не альтернативу ли биткоинам ты задумал?

Adonai ★★★
()

Это дерево ведь надо ещё как-то создавать и модифицировать, не? Плясать нужно именно от набора операций. Может, тебе вообще подойдёт хранить таблицу пар вида (node, ancestor). Ну да, при добавлении элемента на уровне 1k придётся вставить в эту таблицу 1k записей. Но в твоей задаче это может быть разумно.

Miguel ★★★★★
()
Ответ на: комментарий от Miguel

Ну да, при добавлении элемента на уровне 1k придётся вставить в эту таблицу 1k записей.

http://stackoverflow.com/questions/20382012/a-rather-specific-design-for-a-cu...

я вот здесь описал операции. попробую еще sudo cast Reset

cdshines ★★★★★
() автор топика

Не очень просто шардить эффективное дерево. Это делают крайне редко. Обычно граф представляют в виде какого-то key-value и следят чтобы запросов приходилось делать не много.

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

Базы есть, Neo4j, но не уверен что они вот так прямо супер будут шардиться. Там профиты в хранении прямых адресов элементов в образе на одной машине, потому вместо В+ индекса получаешь О(1)

Реальные размеры, описание задачи в студию. Бизнес задачи

vertexua ★★★★★
()
Последнее исправление: vertexua (всего исправлений: 1)
Ответ на: комментарий от vertexua

Шардинг - это опционально. Насчет реальной задачи - не могу распространяться, к сожалению. Neo4j - тоже смотрел. Размеры уже сказал - потенциально каждая нода может представлять некую сущность, поставленную в соответствие, например, каждому файлу из (может быть и) распределенной ФС. (это вырожденный асимптотически крайний случай, но все же)

Я не знаю, как конкретнее описать, чтобы не выложить все вообще) Суть в том, что для получения полной информации по ноде к ней нужно дойти, как в префиксном дереве, по пути. Хм, может, подумать в эту сторону? Завтра, если получится, постараюсь подробнее описать.

А что ты думаешь про уже упомянутый jackrabbit?

cdshines ★★★★★
() автор топика

должна присутствовать возможность получить для ноды список всех предков при уловии, что у каждой ноды один родитель, что очевидно, до корня

если в рел.базе нет отдельных фич для работы с деревьями, то делают через nested-sets - храниться компактно, наборы из «предков» или «детей» реализуются одним запросом.

добавил в теги «математика»

добавь ещё «русский язык» и «поток сознания» - очень тяжело читать ваш текст :-)

MKuznetsov ★★★★★
()
Ответ на: комментарий от MKuznetsov

Да, я уже заметил, но мне что-то лень переписывать по-человечески. Я что, становлюсь как qulinxao?

cdshines ★★★★★
() автор топика

и чтоб при этом их добро менялось в соответствии с новым положением, в т.ч. и добро их детей.

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

dikiy ★★☆☆☆
()
Последнее исправление: dikiy (всего исправлений: 1)
Ответ на: комментарий от cdshines

Ещё такой момент — как ты собираешься адресовать ноды?

Если, например, ты будешь ходить по дереву как по файловой системе и иногда восклицать «а подать мне всех предков текущей ноды!», то будет иметь смысл просто хранить список предков и инкрементально его апдейтить при смене ноды.

Или у тебя будет какой-то внешний способ адресации нод, т.е., они шарятся между деревом и чем-то ещё?

Miguel ★★★★★
()
Ответ на: комментарий от Miguel

На ноды будут ссылки извне от тех объектов, которым как раз и нужна информация из нод.

cdshines ★★★★★
() автор топика
Ответ на: комментарий от vertexua

Я щас сравниваю neo4j, jackrabbit, mysql и orientdb на предмет этой фигни на дереве примерно 1м. нод, и прикидываю, что это составляет какие-то жалкие проценты от реальной задачи.

cdshines ★★★★★
() автор топика
Ответ на: комментарий от cdshines

120КК нод в jackrabbit льются уже полчаса и нет ни намека на счастливый конец.

cdshines ★★★★★
() автор топика
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.