Деревья Nested sets

[Antonariy]

Делал сабж на sql2005 по этой статье. Все работает кроме перемещения ветки (без изменения порядка). Через несколько произвольных перемещений уровни расползаются на недопустимые значения, начинают дублироваться ключи.

Таблица:
NormCatalogID pk
Name varchar
RefID - ссылка на NormCatalogID parent'а
Lk - левый ключ
Rk - правый ключ
Lev - уровень

Код: Выделить всё

ALTER proc [dbo].[procMoveNormCtlg]
@NormCatalogID int,
@ParentID int
as
begin tran
declare @Lev int, @Lk int, @Rk int
declare @LevNew int, @right_key_near int, @PrevID int
declare @skew_level int, @skew_tree int, @skew_edit int

SELECT   @Lev = Lev, @Lk = Lk, @Rk = Rk FROM tblNormCatalog WHERE NormCatalogID = @NormCatalogID
select   @LevNew = Lev, @right_key_near=Rk-1 FROM tblNormCatalog WHERE NormCatalogID = @ParentID

set @skew_level = @LevNew - @Lev + 1
set @skew_tree = @Rk - @Lk + 1
set @skew_edit = @right_key_near - @Lk + 1

print @right_key_near
print @Rk

if @right_key_near>@rk
   UPDATE   tblNormCatalog
   SET      Lk =  case when Rk <= @Rk then Lk +  @skew_edit  else case when Lk > @Rk then Lk - @skew_tree else Lk end end,
         Lev = case when Rk <= @Rk then Lev + @skew_level else Lev end,
         Rk =  case when Rk <= @Rk then Rk +  @skew_edit  else case when Rk <= @right_key_near then Rk - @skew_tree else Rk end end
   WHERE   Rk > @Lk AND
         Lk <= @right_key_near
else
   UPDATE   tblNormCatalog
   SET      Rk =  case when Lk >= @Lk then Rk + @skew_edit else case when Rk < @Lk then Rk + @skew_tree else Rk end end,
         Lev = case when Lk >= @Lk then Lev + @skew_level else Lev end,
         Lk =  case when Lk >= @Lk then Lk + @skew_edit else case when Lk > @right_key_near then Lk + @skew_tree else Lk end end
   WHERE Rk > @right_key_near AND Lk < @Rk

update   tblNormCatalog Set RefID = @ParentID where NormCatalogID = @NormCatalogID

if @@error<>0
   rollback tran
else
   commit tran

Где я накосячил?

[HandKot]

а можно поподробнее
если на примере картинки из статья, то какой узел и куда перетаскивается (что должно получиться в итоге)

[Antonariy]

Пример в аттаче.

[HandKot]

не проверял, но есть подозрение что Вы упустили следующую фразу

Определяем смещение ключей редактируемого узла $right_key_near - $left_key + 1 = $skew_edit;
...
Определяем смещение ключей редактируемого узла $right_key_near - $left_key + 1 - $skew_tree = $skew_edit.

и тогда должно получиться что-то следующее

Код: Выделить всё

IF @right_key_near>@rk
BEGIN
        SET @skew_edit = @right_key_near - @Lk + 1 - @skew_tree
        UPDATE  tblNormCatalog
        SET             Lk =  case when Rk <= @Rk then Lk +  @skew_edit  else case when Lk > @Rk then Lk - @skew_tree else Lk end end,
                        Lev = case when Rk <= @Rk then Lev + @skew_level else Lev end,
                        Rk =  case when Rk <= @Rk then Rk +  @skew_edit  else case when Rk <= @right_key_near then Rk - @skew_tree else Rk end end
        WHERE   Rk > @Lk AND
                        Lk <= @right_key_near
END
else
BEGIN
        SET @skew_edit = @right_key_near - @Lk + 1
        UPDATE  tblNormCatalog
        SET             Rk =  case when Lk >= @Lk then Rk + @skew_edit else case when Rk < @Lk then Rk + @skew_tree else Rk end end,
                        Lev = case when Lk >= @Lk then Lev + @skew_level else Lev end,
                        Lk =  case when Lk >= @Lk then Lk + @skew_edit else case when Lk > @right_key_near then Lk + @skew_tree else Lk end end
        WHERE Rk > @right_key_near AND Lk < @Rk
END

[Antonariy]

В яблочко! Спасибо.

[Antonariy]

Понадобилось таки добавить изменение порядка веток. Для этого нужен @left_key_near:

Код: Выделить всё

SELECT  @LevNew = Lev, @right_key_near=Rk-1, @left_key_near = Lk FROM tblNormCatalog WHERE NormCatalogID = @ParentID

А что с ним делать дальше — не понятно. В статье он больше не упоминается.

[HandKot]

не совсем понятен вопрос.
по возможности, пропишите в виде
вид дерева "до"
1А
2А 2Б 2В
3А 3Б 3В 3Г 3Д 3Е

нужно перенсти ветку 2А в ветку ..., чтобы ...

[Antonariy]

Не совсем понятен хекс
Дерево до:

Код: Выделить всё

Корень
    Ветвь 1
    Ветвь 2
    Ветвь 3

Дерево после:

Код: Выделить всё

Корень
    Ветвь 3
    Ветвь 1
    Ветвь 2

[HandKot]

наконец-то добрался
вот решение, но нужно проверить на реальных данных

@id - что перемещаем
@new_parent_id - родитель (может быть null, когда перемещаем в корень)
@id_befor - узел, что остается слева (если null, то будет первым в род.узле)

Код: Выделить всё

alter procedure move_node(@id int, @new_parent_id int, @id_befor int)
as
begin
SET NOCOUNT ON

  --Ключи и уровень перемещаемого узла
  declare @level int, @leftkey int, @rightkey int
  select @level = level, @leftkey = leftkey, @rightkey = rightkey from nested_sets where id = @id

  --Ключи и уровень нового родительского узла
  declare @level_up int, @parent_leftkey int, @parent_rightkey int, @rightkey_near int
  if @new_parent_id is not null
    select @level_up = level from nested_sets where id = @new_parent_id
  else
    select @level_up = 0
  if @id_befor is null
    select @rightkey_near = leftkey + 1 from nested_sets where id = @new_parent_id
  else
    select @rightkey_near = rightkey from nested_sets where id = @id_befor
  --делаем по необходимости корректировку
  if @rightkey_near is null
    select @rightkey_near = 0

  --Определяем хар-ки перемещения
  declare @skew_level int, @skew_tree int
  set @skew_level = @level_up - @level + 1
  set @skew_tree = @rightkey - @leftkey + 1

  --Перемещаем
  declare @skew_edit int
  if (@rightkey < @rightkey_near)
  begin
    set @skew_edit = @rightkey_near - @leftkey + 1 - @skew_tree
    update nested_sets
      set leftkey = case
                      when rightkey <= @rightkey then leftkey +  @skew_edit 
                      else
                        case
                          when leftkey > @rightkey then leftkey - @skew_tree
                          else leftkey
                        end
                    end,
     [level] = case when rightkey <= @rightkey then [level] + @skew_level else [level] end,
     rightkey = case
                  when rightkey <= @rightkey then rightkey +  @skew_edit 
                  else
                    case
                      when rightkey <= @rightkey_near then rightkey - @skew_tree
                      else rightkey
                    end
               end
    where   
      rightkey > @leftkey and
      leftkey <= @rightkey_near

  end
  else
  begin
    set @skew_edit = @rightkey_near - @leftkey + 1
    update nested_sets
      set rightkey = case
                       when leftkey >= @leftkey then rightkey + @skew_edit
                       else
                         case
                           when rightkey < @leftkey then rightkey + @skew_tree
                           else rightkey
                         end
                     end,
      [level] = case when leftkey >= @leftkey then [level] + @skew_level else [level] end,
      leftkey = case 
                  when leftkey >= @leftkey then leftkey + @skew_edit
                  else
                    case
                      when leftkey > @rightkey_near then leftkey + @skew_tree
                      else leftkey
                    end
                end
    where
      rightkey > @rightkey_near and
      leftkey < @rightkey
  end
end

ЗЫЖ будут нарекания, то представьте данные таблицы и что и куда перемещаем

[Antonariy]

Все отлично, за исключением одной неточности — не работало перемещение ветки в начало уровня*. И почему-то неправильно считался rightkey_near при переносе в другую ветку**. Код ниже рабочий.

Код: Выделить всё

if @id_befor is null and @new_parent_id is null
    *
    select @rightkey_near = leftkey from nested_sets where id = (select ParentID from nested_sets where id= @id)
else if @id_befor is null
    **
    select @rightkey_near = rightkey - 1 from nested_sets where id = @new_parent_id
else
    select @rightkey_near = rightkey from nested_sets where id = @id_befor

[HandKot]

главное что у Вас все получилось