Как сортировать дерево, хранящееся с помощью модели вложенного набора?

Ответ 1

Я думаю, что это действительно ограничение вложенной модели набора. Вы не можете легко сортировать дочерние узлы в своем родительском node, потому что упорядочение набора результатов имеет важное значение для восстановления древовидной структуры.

Я думаю, что это, вероятно, лучший способ сохранить дерево, отсортированное при вставке, обновлении или удалении узлов. Это даже делает запросы очень быстрыми, что является одной из основных целей этой структуры данных. Если вы реализуете хранимые процедуры для всех операций, их очень легко использовать.

Вы также можете отменить порядок сортировки предварительно отредактированного дерева. Вам просто нужно использовать ORDER BY node.rgt DESC вместо ORDER BY node.lft ASC.

Если вам действительно нужно поддерживать другие критерии сортировки, вы можете реализовать его, добавив второй индекс lft и rgt к каждому node и сохраните его в соответствии с другими критериями при каждом вставке/обновлении/удалении.

Ответ 2

Я много использовал Nested Sets и часто сталкивался с той же проблемой. Что я делаю, и что бы я рекомендовал, просто не сортировать элементы в базе данных. Вместо этого сортируйте их в пользовательском интерфейсе. После того, как вы вытащили все узлы из БД, вам, вероятно, придется преобразовать их в некоторую иерархическую структуру данных. В этой структуре отсортируйте все массивы, содержащие дочерние элементы node.

Например, если ваш интерфейс - это приложение Flex, а дочерние элементы node хранятся в ICollectionView, вы можете использовать свойство sort, чтобы они отображались так, как вы хотите.

Другой пример: если ваш внешний интерфейс - это какой-то вывод из PHP script, вы можете иметь дочерние элементы каждого node в массиве и использовать функции сортировки массива PHP для выполнения сортировки.

Конечно, это работает только в том случае, если вам не нужны фактические записи db для сортировки, но вы?

Ответ 3

Я только что закончил писать следующее, которое работает для меня при сортировке всего дерева вложенных множеств.

Сортировка (в идеале) требует представления, которое отображает текущий уровень каждого node в дереве и процедуру для обмена двумя узлами - оба они включены ниже, код свопинга swib происходит от дерева и иерархии Joe Celkos ' который я настоятельно рекомендую всем, кто использует вложенные наборы.

Сорт может быть изменен в инструкции "INSERT INTO @t", здесь это простой буквенно-цифровой вид в поле "Имя"

Это может быть плохой способ сделать это, особенно с помощью курсора для кода на основе набора, но поскольку я говорю, что это работает для меня, надеюсь, что это поможет.

UPDATE:

В приведенном ниже коде показана версия без использования cusor. Я вижу примерно 10-кратное повышение скорости

CREATE VIEW dbo.tree_view

AS

SELECT t2.NodeID,t2.lft,t2.rgt ,t2.Name, COUNT(t1.NodeID) AS level  
FROM dbo.tree t1,dbo.tree t2
WHERE t2.lft BETWEEN t1.lft AND t1.rgt
GROUP BY t2.NodeID,t2.lft,t2.rgt,t2.Name

GO

----------------------------------------------

  DECLARE @CurrentNodeID int
DECLARE @CurrentActualOrder int
DECLARE @CurrentRequiredOrder int
DECLARE @DestinationNodeID int
DECLARE @i0 int
DECLARE @i1 int
DECLARE @i2 int
DECLARE @i3 int

DECLARE @t TABLE (TopLft int,NodeID int NOT NULL,lft int NOT NULL,rgt int NOT NULL,Name varchar(50),RequiredOrder int NOT NULL,ActualOrder int NOT NULL)


INSERT INTO @t (toplft,NodeID,lft,rgt,Name,RequiredOrder,ActualOrder)
    SELECT tv2.lft,tv1.NodeID,tv1.lft,tv1.rgt,tv1.Name,ROW_NUMBER() OVER(PARTITION BY tv2.lft ORDER BY tv1.ColumnToSort),ROW_NUMBER() OVER(PARTITION BY tv2.lft ORDER BY tv1.lft ASC)
    FROM dbo.tree_view tv1 
    LEFT OUTER JOIN dbo.tree_view tv2 ON tv1.lft > tv2.lft and tv1.lft < tv2.rgt and tv1.level = tv2.level+1
    WHERE tv2.rgt > tv2.lft+1

    DELETE FROM @t where ActualOrder = RequiredOrder


WHILE EXISTS(SELECT * FROM @t WHERE ActualOrder <> RequiredOrder)
BEGIN


    SELECT Top 1 @CurrentNodeID = NodeID,@CurrentActualOrder = ActualOrder,@CurrentRequiredOrder = RequiredOrder
    FROM @t 
    WHERE ActualOrder <> RequiredOrder
    ORDER BY toplft,requiredorder

    SELECT @DestinationNodeID = NodeID
    FROM @t WHERE ActualOrder = @CurrentRequiredOrder AND TopLft = (SELECT TopLft FROM @t WHERE NodeID = @CurrentNodeID) 

    SELECT @i0 = CASE WHEN c.lft < d.lft THEN c.lft ELSE d.lft END,
            @i1 =  CASE WHEN c.lft < d.lft THEN c.rgt ELSE d.rgt END,
            @i2 =  CASE WHEN c.lft < d.lft THEN d.lft ELSE c.lft END,
            @i3 =  CASE WHEN c.lft < d.lft THEN d.rgt ELSE c.rgt END
    FROM dbo.tree c
    CROSS JOIN dbo.tree d
    WHERE c.NodeID = @CurrentNodeID AND d.NodeID = @DestinationNodeID

    UPDATE dbo.tree
    SET lft = CASE  WHEN lft BETWEEN @i0 AND @i1 THEN @i3 + lft - @i1
                    WHEN lft BETWEEN @i2 AND @i3 THEN @i0 + lft - @i2
            ELSE @i0 + @i3 + lft - @i1 - @i2
            END,
        rgt = CASE  WHEN rgt BETWEEN @i0 AND @i1 THEN @i3 + rgt - @i1
                    WHEN rgt BETWEEN @i2 AND @i3 THEN @i0 + rgt - @i2
            ELSE @i0 + @i3 + rgt - @i1 - @i2
            END
    WHERE lft BETWEEN @i0 AND @i3 
    AND @i0 < @i1
    AND @i1 < @i2
    AND @i2 < @i3

    UPDATE @t SET actualorder = @CurrentRequiredOrder where NodeID = @CurrentNodeID
    UPDATE @t SET actualorder = @CurrentActualOrder where NodeID = @DestinationNodeID

    DELETE FROM @t where ActualOrder = RequiredOrder

END

Ответ 4

Да, это ограничение вложенной модели набора, так как вложенные наборы являются предзаказанным представлением иерархии. Этот предварительный заказ является причиной того, что он так быстро читает. Модель смежности, также описанная на странице, на которую вы ссылаетесь, обеспечивает наиболее гибкую сортировку и фильтрацию, но со значительным воздействием на производительность.

Мой предпочтительный подход для вставок и перемещений во вложенном наборе - это обработать затронутую ветку, как в модели смежности: получить список новых братьев и сестер; найти нужное место в списке для нового node; и создайте необходимые операторы обновления (это бит, где вам действительно нужно быть осторожным). Что касается изменения ваших критериев заказа: это одноразовое задание, поэтому вы можете позволить себе нанести на него некоторую оперативную память и центральный процессор, самым гибким ответом было бы разбить представление вложенного набора вниз на представление смежности и перестроить вложенный набор из смежность, основанная на новых критериях.

Ответ 5

Я считаю, что в вашем случае, когда узлы, которые вы хотите обменять, не имеют потомков, вы можете просто поменять значения lft и rgt. Рассмотрим это дерево:

   A
 /   \
B     C
     / \
    D   E

Это может превратиться в эту группу вложенных множеств:

1 A 10 
2 B 3  
4 C 9
5 D 6
7 E 8

Теперь рассмотрим, что вы хотите поменять местами D и E. Имеются следующие вложенные наборы, а D и E меняются местами:

1 A 10
2 B 3 
4 C 9 
7 D 8
5 E 6 

Перемещение узлов, которые имеют поддеревья, не может быть сделано таким образом, конечно, потому что вам также нужно будет обновить значения lft и rgt для детей.

Ответ 6

Вы можете сортировать их при рендеринге. Я объяснил, как сделать здесь Как сделать все записи из вложенного набора в реальное дерево html

Ответ 7

См. мое простое решение из метода моего класса. $this- > table- > order - это код сети Nette для получения данных из БД.

$tree = Array();
$parents = Array();
$nodes = $this->table->order('depth ASC, parent_id ASC, name ASC');
$i = 0;
$depth = 0;
$parent_id = 0;

foreach($nodes as $node) {
    if($depth < $node->depth || $parent_id < $node->parent_id) {
        $i = $parents["{$node->parent_id}"] + 1;
    }
    $tree[$i] = $node;
    $parents["{$node->id}"] = $i;
    $depth = $node->depth;
    $parent_id = $node->parent_id;
    $i += (($node->rgt - $node->lft - 1) / 2) + 1;
}
ksort($tree);

Ответ 8

Сортировка вложенных наборов не имеет границ, и это не сложно. Просто попробуйте LEFT bower (якорь, что бы там ни было), и все сделано. Если у вас есть УРОВЕНЬ для каждого node, вы также можете выставить правильный отступ на основе уровня.