Comments 11
Любое добавление некоторой структуры нужны только для улучшения производительности.
Из моего опыта, лучшие решение с точки зрения чтения — это «вложеные множества». Неплохобы сравнтить с ними
Также, учытывая что Вы используете PostgreSQL, неплохобы попробовать ее встроеные возможности
Из моего опыта, лучшие решение с точки зрения чтения — это «вложеные множества». Неплохобы сравнтить с ними
Также, учытывая что Вы используете PostgreSQL, неплохобы попробовать ее встроеные возможности
Тут фактически тоже «вложенные множества». По производительности чтения отличия от оригинального nested sets не будет. Будет выигрыш при изменениях иерархии, причем существенный. Расплата за это — указанные в статье ограничения.
Вы правы, конечно, в PostgreSQL есть встроенный механизм для иерархии.
Я написал о более «общем» методе. Его можно применять в любой БД.
Вы правы, конечно, в PostgreSQL есть встроенный механизм для иерархии.
Я написал о более «общем» методе. Его можно применять в любой БД.
Для любой БД есть как миниум 3 вида хорошо описанной иерархии.
habrahabr.ru/post/46659/#habracut
habrahabr.ru/post/46659/#habracut
Nested Sets очень неповоротливы при простой операции удаление/перемещение листа или узла. Затраты на обновление всей ветки при изменении одного узла просто неэффективны. Причём, не только перемещения веток будут вызывать перестройку лево-правых ключей, но и удаление как узла, так и листа. А вот это уже роскошь.
Предлагаю посмотреть на Path: при разумном количестве уровней (пара сотен) пути не сильно-то и большие получаются. Выбор ветки, узла, детей и родителя — операции тривиальные и происходят в один запрос. Хуже — перемещения веток, но я не вижу сильной необходимости оптимизировать столь редкую операцию. Удаление всей ветки — операция также тривиальная в один запрос.
П.С. Каждой задаче по своему алгоритму — может, для кого-то скорость изменения структуры дерева важна. Тут уж Id-Pid будет рулить.
П.П.С. Реквестирую хоть какие-нибудь тесты — ради чего это писалось, есть ли выигрыш (и по сравнению с чем).
Предлагаю посмотреть на Path: при разумном количестве уровней (пара сотен) пути не сильно-то и большие получаются. Выбор ветки, узла, детей и родителя — операции тривиальные и происходят в один запрос. Хуже — перемещения веток, но я не вижу сильной необходимости оптимизировать столь редкую операцию. Удаление всей ветки — операция также тривиальная в один запрос.
П.С. Каждой задаче по своему алгоритму — может, для кого-то скорость изменения структуры дерева важна. Тут уж Id-Pid будет рулить.
П.П.С. Реквестирую хоть какие-нибудь тесты — ради чего это писалось, есть ли выигрыш (и по сравнению с чем).
Сорри, это ответ на habrahabr.ru/post/166699/#comment_5758337
Можно запутаться в иерархии Ваших комментов :)
Получилась адская смесь Adjacency List, Nested Set, ограничений и избыточности.
Adjacency List — наличие прямой ссылки на родителя.
Nested Set напоминает упорядочением id элементов. Так, поле right для классического NS можно вычислить, используя ID, LEVEL и константы CH и LV. Но так как они константы, хранить поле right не имеет смысла.
Очень много избыточности. Так, например, можно отказаться от PARENT. ID родителя находится в диапазоне от ID — ((CH+1)^(LV-LEVEL-1)) до ID и уровнем ниже. Либо аналогично отказаться от LEVEL. COUNT_CHILDS — кол-во узлов со ссылкой на текущий, либо кол-во узлов на следующем уровне в определенном диапазоне ID. Все эти показатели связаны. Понятно, что избыточность дает дополнительную гибкость при выборках. Но это же замедляет при изменении дерева, появляется необходимость апдейтить значения соседей, родителей, детей.
Для выборки дерева, как в NS, используется сортировка, что очень хорошо. Но все же хуже (теоретически), чем в NS, так как сортировки только по ID не достаточно, нужен LEVEL.
Adjacency List — наличие прямой ссылки на родителя.
Nested Set напоминает упорядочением id элементов. Так, поле right для классического NS можно вычислить, используя ID, LEVEL и константы CH и LV. Но так как они константы, хранить поле right не имеет смысла.
Очень много избыточности. Так, например, можно отказаться от PARENT. ID родителя находится в диапазоне от ID — ((CH+1)^(LV-LEVEL-1)) до ID и уровнем ниже. Либо аналогично отказаться от LEVEL. COUNT_CHILDS — кол-во узлов со ссылкой на текущий, либо кол-во узлов на следующем уровне в определенном диапазоне ID. Все эти показатели связаны. Понятно, что избыточность дает дополнительную гибкость при выборках. Но это же замедляет при изменении дерева, появляется необходимость апдейтить значения соседей, родителей, детей.
Для выборки дерева, как в NS, используется сортировка, что очень хорошо. Но все же хуже (теоретически), чем в NS, так как сортировки только по ID не достаточно, нужен LEVEL.
Про смесь Вы подметили верно.
Про избыточность тоже. Но хранение дополнительных полей упрощает реализацию. С PARENT, например, очень удобно добавлять новый элемент в админке Django, можно еще прикрутить какой-нибудь готовый плагин отображения и работы с Деревом. Без КоличестваДетей будет трудно понять какой ID добавлять — придется делать запрос.
Можно обойтись без Уровня. Но в конкретно этой реализации решил его оставить.
Про избыточность тоже. Но хранение дополнительных полей упрощает реализацию. С PARENT, например, очень удобно добавлять новый элемент в админке Django, можно еще прикрутить какой-нибудь готовый плагин отображения и работы с Деревом. Без КоличестваДетей будет трудно понять какой ID добавлять — придется делать запрос.
Можно обойтись без Уровня. Но в конкретно этой реализации решил его оставить.
Написал приложение treensl для Django (django-treensl).
Исходники на github
Логика работы с первичным ключом вынесена в БД.
Пока реализовано только для PostgreSQL 9.1 и выше.
В PyPi пока не выложил.
Исходники на github
Логика работы с первичным ключом вынесена в БД.
Пока реализовано только для PostgreSQL 9.1 и выше.
В PyPi пока не выложил.
Sign up to leave a comment.
Степени — ключ к быстрой иерархии в реляционной БД