在MySQL中处理嵌套集合？

Question

在MySQL中处理嵌套集合？

7

我决定跟随http://www.artfulsoftware.com/mysqlbook/sampler/mysqled1ch20.html，现在我正在寻求代码方面的帮助。

我正在使用他们的数据进行测试，所以我将树形结构可视化如下：

    array('value' => 'Richard Shakespeare',
        array('value' => 'Henry',
            array('value' => 'Joan'),
            array('value' => 'Margaret'),
            array('value' => 'William',
                array('value' => 'Susana',
                    array('value' => 'Elizabeth Hall',
                        array('value' => 'John Bernard'))),
                array('value' => 'Hamnet'),
                array('value' => 'Judith',
                    array('value' => 'Shakespeare Quiney'),
                    array('value' => 'Richard Quiney'),
                    array('value' => 'Thomas Quiney'))),
            array('value' => 'Gilbert'),
            array('value' => 'Joan',
                array('value' => 'William Hart'),
                array('value' => 'Mary Hart'),
                array('value' => 'Thomas Hart'),
                array('value' => 'Micheal Hart')),
            array('value' => 'Anne'),
            array('value' => 'Richard'),
            array('value' => 'Edmond')),
        array('value' => 'John'));

所以，如果我们想将其插入到数据库中，我们希望最终得到的是

那么问题来了，如何最好地做到这一点？

我的解决方案是：

$container = array();

function children($item){
  $children = 0;
  foreach($item as $node)
    if(is_array($node))
      $children += children($node)+1;
    return $children;
}

function calculate($item, &$container, $data = array(0,0)){
  //althought this one is actually of no use, it could be useful as it contains a count 
  $data[0]++; //$left

  $right = ($data[0]+(children($item)*2))+1;

  //store the values in the passed container
  $container[] = array(
    'value' => $item['value'],
    'left'  => $data[0],
    'right' => $right,
  );

  //continue looping
  $level = $data[1]++;
  foreach($item as &$node)
    if(is_array($node))
      $data = calculate($node, $container, $data);

    $data[1] = $level;
    $data[0]++;
    return $data;
}

calculate($tree, $container);

我不知道它有多有效率。

现在进入查询。

要选择一个节点的所有后代，我们可以使用：

SELECT child.value AS 'Descendants of William', COUNT(*) AS `Level`
FROM tester AS parent
JOIN tester AS child ON child.`left` BETWEEN parent.`left` AND parent.`right`
WHERE parent.`left` > 7 AND parent.`right` < 24
GROUP BY child.value ORDER BY `level`;

要选择节点的所有后代，到特定深度我们可以使用
请注意，我们选择William的后代，深度为2
William的左侧：7，William的右侧：24，级别：2

SELECT child.value AS 'Descendants of William', COUNT(*) AS `Level`
FROM tester AS parent
JOIN tester AS child ON child.`left` BETWEEN parent.`left` AND parent.`right`
WHERE parent.`left` > 7 AND parent.`right` < 24
GROUP BY child.value HAVING `level` <= 2 ORDER BY `level`;

那么这很容易。

但现在我想了解一些事情，
请注意，在实际数据库中，所有行都有一个唯一的ID和一个“父”列，其中包含他们的邀请者ID，或者如果没有被邀请则为空

假设我想将David插入到Judith的子级，我该如何做？
假设我想获取Mary Hart的父级和父级的父级（array('Henery', 'Joan', 'Mary Hart')），我该如何做？
假设我想从Joan中删除William Hart，我该怎么做？

- Hailwood

你尝试过什么？我很不想问，但嵌套集合很复杂，而且你的问题听起来像是在众包你的工作。此外，你甚至还没有开始浏览问题的难度。例如：“如果我想反转大卫和朱迪思，使朱迪思现在取代大卫成为孩子，反之亦然，我该如何做到这一点[不用两次重新索引树]？” - Denis de Bernardy

3个回答

1

要获取一个节点的父节点，您需要使用具有 left_id < child.left_id 和 right_id > child.right_id 的节点。如果您只想选择直接的祖先，则从前面的集合中选择具有最高 left_id 的那个。

要删除一个节点，请将其删除，然后将所有左/右ID大于已删除元素的右ID的ID降低两次。如果（leftId> deleted.leftId），则leftId-=2同样适用于rightId。

要插入一个节点，请为其添加空间，将 leftId > parent.rightId 的所有节点增加+2，然后 parent.rightId + = 2，然后插入 leftId = parent.rightId-2 和 rightId = parent.rightId-1 的节点。

- malko

0

如果你为每个关系使用深度优先搜索，然后再次使用calculate()函数进行更详细的计算，那么所有问题都可以很容易地解决。

- Micromega

海尔伍德：深度优先搜索。 - Micromega

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- OZ_ · Accepted Answer

要进行更新/删除，您需要增加/减少分支的所有元素的left/right值。
你可以在这里找到一些查询示例。

它的效率有多高我不清楚。

嵌套集在更新/插入/删除大型树时速度非常慢。但在选择方面非常快。
因此，只能将此模型与静态数据一起使用，该数据大部分时间都不会更改，并且该树不会包含数千个节点（否则任何更新将需要几分钟才能完成）。而路径材料化方式的速度更快。