Для второй задачи кстати внаверное можно нестед сетс (правые и левые ключи) применить, как раз учитывая что дерево ролей все же апдейтиться довльно редко и перестройки ключей каждый раз для всего дерева не сожрут много ресурсов
Право лево не поможет, оно же не бинарное Мой вариант с рангами и массивами родителей рабочий, будет сложность о(1) просто требует х2 памяти и перестройки дерева при добавлении роли.
1. Взвешиваем ранг каждой вершины. Корень 0, его потомки 1, и т.д. Чем выше ранг, тем ниже роль. 1.1. Для каждой вершины создаем массив родительских. По индексу 0 лежит родитель, 1 -- родитель родителя и т.д. до корня вверх
2. На юзере роль U(g), как узнать, есть ли U(r)? Если ранг r < g, роли нет, не смотрим. R старше g и проверять нечего. Если ранг r = g, роли тоже нет, разные узлы дерева на одном уровне. Если ранг r > g. Берем разницу рангов r и g = n и в массиве родителей r берем элемент с индексом n и сравниваем с g. Если равны, то есть роль.
Погугли таки Nested Sets, там и ветка парентов и все потомки получаются простым селектом с двумя сравнениями интов. Единственный минус такой иерархии долгтие апдейты и удаления
Reply
Мой вариант с рангами и массивами родителей рабочий, будет сложность о(1) просто требует х2 памяти и перестройки дерева при добавлении роли.
1. Взвешиваем ранг каждой вершины. Корень 0, его потомки 1, и т.д.
Чем выше ранг, тем ниже роль.
1.1. Для каждой вершины создаем массив родительских. По индексу 0 лежит родитель, 1 -- родитель родителя и т.д. до корня вверх
2. На юзере роль U(g), как узнать, есть ли U(r)?
Если ранг r < g, роли нет, не смотрим. R старше g и проверять нечего.
Если ранг r = g, роли тоже нет, разные узлы дерева на одном уровне.
Если ранг r > g.
Берем разницу рангов r и g = n и в массиве родителей r берем элемент с индексом n и сравниваем с g. Если равны, то есть роль.
Reply
Reply
Reply
Select * from NestedTable where parLeft > NestedTable.Left and parRight < NestedTable.Right
Reply
Reply
Leave a comment