Порадьте фреймворк для ієрархічних структур

Потрібно побудувати і впорядкувати ієрахічну структуру (з ~10 мілліонів дата рекордів) і алгоритмом пошуку по дереву і місця в структурі.

Після добалення ноди буде потрібна оптимізацiя і впорядкування дерева.

Бажана паралельність, можна розпреділеність на декілька серверів для побудови структури.

Після побудови треба буде забезпечити пошук, відображення нодів, добавлення нових елементів в структуру.

Не хочется платити за суперкомп чи хмару (шкільний проект), хочется проранати локально і деплойнути для демо

Який фреймворк краще використати?
Хтось робив щось подібне?

Ctrl + Enter

Vitaliy Fedoriv Java Developer 09.07.2018 23:19

берете якусь реалізацію b-tree і будуєте. нічого принципово відмінного не видумали ж. можна це засунути в реляційку або nosql, в основі буде те ж b-tree лежати у вигляді індексу.
ну і розмір ноди, глибину дерева, необхідну швидкодію ви не вказали (може у вас глибина в 1млн., на кой тоді дерево)

Відповісти

Підтримати

Roman Gorel Ruby developer в Drooms 09.07.2018 17:57

попробуйте ltree в постгресе www.postgresql.org/...ocs/9.6/static/ltree.html

Леонид Мартынюк инженер-программист в 1World online R&D Сenter 09.07.2018 13:00

фреймвркам все равно какая там структура. Вообще на таксономию заточен друпал.
Что касается монго и прочего nosql барахла с всякими json — оно просто ляжет на больших данных — уже такое проходил на CouchDB.
Использую в таких случаях обычную таблицу в mysql например, организованую по materialized path. Позволяет делать любые манипуляции с деревом одним sql запросм

Valeriy Zamarayev (junior lisper) 09.07.2018 18:20

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

Леонид Мартынюк

Леонид Мартынюк инженер-программист в 1World online R&D Сenter 09.07.2018 18:45

потому и materialized path чтобы ничего не перестраивть а просто вставлять запись.

Valeriy Zamarayev

Denys Poltorak Embedded | C++ (opentowork) 09.07.2018 12:49

library.bagrintsev.me/CPP/Sedzhvik.pdf
11.3 внешняя сортировка
16 внешний поиск

anonymous 09.07.2018 02:57

Volodymyr Spodaryk Solutions Architect в SPsoft 09.07.2018 13:51

На фронтенді можна відобразити все, що завгодно, але за умови, що воно десь збережено і видається по АПІ :)

anonymous

Victor Musienkо Senior Engineer 09.07.2018 00:48

mongo, postgres вміє в json теж, треба дивитись наскільки глибока структура, можливо нормалізувати вийде в реляційну
ще можна графову бд спробувати, але не рекомендую neo4j, бо вона повільна на джоінах. en.wikipedia.org/wiki/OrientDB чув непогана (orientdb.com/orientdb-vs-neo4j)

Andrii Batyiev Senior Expert C++ Developer 07.07.2018 15:59

Иерархическая база данных — это внезапно файловая система. Попробуйте btrfs

anonymous 07.07.2018 15:32

MongoDB внезапно. Там можно поддеревья вырезать в запросе.

Олексій Пєніє 07.07.2018 13:19

Неочевидне рішення: не будувати ієрархічну структуру. Будувати лінійну, із створенням звичайного собі індексу, або декількох.

Чому так: бо єдина причина створення ієрархії — це наслідування реальної (природної) ієрархії даних. І не знаючи нічого про ті дані, не можна створити ефективної ієрархічної моделі. Тому краще збудувати лінійне сховище та індекс.

Оптимізація має бути окремою процедурою. Щоб додавання даних не породжувало складну перебудову всього індексу, а видалення — тяжкого переносу всіх даних.

Якщо дослідження не є теоретичним, тупо постав MySQL, створи звичайну таблицю із полем «ParentID» можеш навіть без ForeignKey (значення цією фічі значно перебільшене). Для перших рівнів ієрархії (груп), які зазвичай дуже стабільні, краще створити окрему таблицю — вона буде словником. Чому так: в ній не має бути елементів, по яких робиться пошук, лише групи. Наприклад, категорії товару — вони слугують лише рівнями ієрархії, саму категорію не шукають, шукають товар.

PS. Проблематика значно ширша за шкільний проект. Бази даних десятками років ці проблеми вирішують, і я б не сказав що результати вражають. Просуваються маленькими кроками, на кшталт таких.

Порадьте фреймворк для ієрархічних структур

12 коментарів

Підписатись на коментарі

Новини