sql - 如何更新嵌套集树结构？

Question

我看过在 MySQL 中管理分层数据，但它实际上只处理在嵌套集模型中添加和删除节点。

我需要能够移动带有和不带有子节点的节点。

我该怎么做？

Answer 1

嵌套集设计不是对树进行这种更改的好选择。在移动节点时重新计算右/左数字真的很复杂。

邻接表是移动子树最简单的树设计：

UPDATE TreeTable
SET parent = $newparent
WHERE id = 123;

路径枚举设计还可以轻松地重新定位节点及其子节点：

UPDATE TreeTable
SET path = REPLACE(path, 'A/B/C/', 'A/D/F/') -- MySQL function
WHERE path LIKE 'A/B/C/%';

Answer 2

与子节点一起移动：

在“left”和“right”值都位于 0..n*2 值的连续块中的经典嵌套集中，将有一系列行将“x”位置移动到左侧或“x”移动子树时向右放置，其中“x”是被移动的左/右值的数量。例如。

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

如果您将带有后代的“A”移动到“D”和“E”之间，则“A”右侧但“E”左侧的所有内容都需要将其左/右索引减少 6（“ A' 与后代）：

UPDATE things
SET nsl=nsl+(
    IF nsl BETWEEN 1 AND 6 THEN 6  -- A-C go forward 6
    ELSE -6                        -- D goes back 6
), nsr=nsr+(                       -- same again
    IF nsl BETWEEN 1 AND 6 THEN 6
    ELSE -6
)
WHERE
    nsl BETWEEN 1 AND 6            -- select A-C
    OR nsl BETWEEN 7 AND 8         -- select D

没有子节点的移动更复杂。包含的节点要后退1，删除节点之后的节点都要后退2，然后新插入点之后的节点要前进2以腾出空间。

虽然您可以以与上述相同的方式执行此操作，但它开始变得非常混乱，您可能需要考虑替代方法，例如手动重写所有左/右值或使用不同的模式类型，使这些操作更简单，例如完整的祖先-后代邻接关系。

Answer 3

这是一个解决方案，可让您将节点移动到树中的任何位置，只需一个输入参数 - 节点的新左侧位置 (newpos)。此方法无法移动没有子节点的节点，但我很想知道您的用例。

基本上分为三组：

• 为子树创建新空间。
• 将子树移动到该空间中。
• 删除子树腾出的旧空间。

在 psuedo-sql 中，它看起来像这样：

//
 *  -- create new space for subtree
 *  UPDATE tags SET lpos = lpos + :width WHERE lpos >= :newpos
 *  UPDATE tags SET rpos = rpos + :width WHERE rpos >= :newpos
 * 
 *  -- move subtree into new space
 *  UPDATE tags SET lpos = lpos + :distance, rpos = rpos + :distance
 *           WHERE lpos >= :tmppos AND rpos < :tmppos + :width
 * 
 *  -- remove old space vacated by subtree
 *  UPDATE tags SET lpos = lpos - :width WHERE lpos > :oldrpos
 *  UPDATE tags SET rpos = rpos - :width WHERE rpos > :oldrpos
 */

:distance 变量是新位置和旧位置之间的距离，:width 是子树的大小，:tmppos 用于跟踪在更新期间移动的子树。这些变量定义为：

// calculate position adjustment variables
int width = node.getRpos() - node.getLpos() + 1;
int distance = newpos - node.getLpos();
int tmppos = node.getLpos();
        
// backwards movement must account for new space
if (distance < 0) {
    distance -= width;
    tmppos += width;
}

有关完整的代码示例，请参阅我的博客：

https://rogerkeays.com/how-to-move-a-node-in-nested-sets-with-sql

如果您喜欢此解决方案，请投票。

Answer 4

考虑移动节点相当于删除该节点及其所有子节点（如果有），并将该节点及其子节点（如果有）插入新位置。

现在重新阅读技术文章，了解在执行删除和插入后整个表的外观，您会发现执行相同操作的更新。