Для исследования и мониторинга распространения ipv6 сетей, а так же выполнения автоматическоего детектирование подсетей, необходимо хранить очень большое количество деревьев (деревья с высотой максимум 8 (сжатые)). В данной статье я приведу некоторые варианты как можно будет хранить эти деревья сетей в РСУБД
1. Списки смежности на таблицах
В теории графов списки смежности - один из способов представления графа, в котором для каждой вершины хранится список смежных с ней вершин. Этот способ хранения является самым часто встречающимся и интуитивно понятным: таблица ссылается сама на себя. Возможно дополнительно хранить ссылки на детей в случае с бинарным деревом, это будет приемлимо, но в случае с N-арным деревом, такой вариант не подойдет.
Рис 1. На изображении хранится дерево с ссылками на родителя.
Преимущества такого вида хранения:
1. Интуитивно понятное представление данных.
2. Уровень вложенности не ограничен.
3. Быстрая вставка чтение и обновление.
Недостатки такого вида хранения:
1. Иногда сложные запросы на выборку потомков.
В этом способе хранения дерево представляется в виде вложенных подмножеств, корневой узел содержит в себе все подмножества первого уровня, которые в свою очередь включают подмножества второго уровня, и так далее. Для хранения дерева таким способом понадобятся две таблицы: в одну таблицу записываются все подмножества, а во вторую - список вхождений каждого подмножества в другие, а также их уровни. В данном случае для N-арного дерева не будет почти никаких отличий в хранении.
Рис 2. На изображении хранится дерево ввиде подмножеств.
Преимущества такого вида хранения:
1. Быстрая и простая выборка потомков дерева.
Недостатки такого вида хранения:
1. Триггеры для поддержки целостности.
2. Мутабельные операции довольно сложные и затрагивают не один узел.
3. Избыточность хранения.
3. Модуль ltree в PostreSQL.
В PostgreSQL есть специализированный модуль для работы с деревьями ltree, который позволяет использовать метод материализованных путей более эффективно и удобно. Этот модуль реализует тип данных ltree для представления меток данных label, хранящихся в иерархической древовидной структуре, и средства для поиска по дереву.
Довольно много про него рассказывать, в данной статье это все не поместится, поэтому оставлю ссылку на документацию https://postgrespro.ru/docs/postgresql/9.6/ltree
Выводы:
- Не очень удобно если необходимо ходить вверх вниз по деревьям и делать вставки. Но можно на хранимые процедуры перенести, что в целом будет немного удобнее.
- Появилось желание рассмотреть графовые СУБД, в надежде некоторого более удоного синтаксиса для обходов, изменения графов нежели SQL.