处理mysql中的嵌套集？

Question

我决定关注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'));

因此,如果我们想将其插入数据库中,我们希望最终得到它

Array
(
    [0] => Array
        (
            [value] => Richard Shakespeare
            [left] => 1
            [right] => 46
        )

    [1] => Array
        (
            [value] => Henry
            [left] => 2
            [right] => 43
        )

    [2] => Array
        (
            [value] => Joan
            [left] => 3
            [right] => 4
        )

    [3] => Array
        (
            [value] => Margaret
            [left] => 5
            [right] => 6
        )

    [4] => Array
        (
            [value] => William
            [left] => 7
            [right] => 24
        )

    [5] => Array
        (
            [value] => Susana
            [left] => 8
            [right] => 13
        )

    [6] => Array
        (
            [value] => Elizabeth Hall
            [left] => 9
            [right] => 12
        )

    [7] => Array
        (
            [value] => John Bernard
            [left] => 10
            [right] => 11
        )

    [8] => Array
        (
            [value] => Hamnet
            [left] => 14
            [right] => 15
        )

    [9] => Array
        (
            [value] => Judith
            [left] => 16
            [right] => 23
        )

    [10] => Array
        (
            [value] => Shakespeare Quiney
            [left] => 17
            [right] => 18
        )

    [11] => Array
        (
            [value] => Richard Quiney
            [left] => 19
            [right] => 20
        )

    [12] => Array
        (
            [value] => Thomas Quiney
            [left] => 21
            [right] => 22
        )

    [13] => Array
        (
            [value] => Gilbert
            [left] => 25
            [right] => 26
        )

    [14] => Array
        (
            [value] => Joan
            [left] => 27
            [right] => 36
        )

    [15] => Array
        (
            [value] => William Hart
            [left] => 28
            [right] => 29
        )

    [16] => Array
        (
            [value] => Mary Hart
            [left] => 30
            [right] => 31
        )

    [17] => Array
        (
            [value] => Thomas Hart
            [left] => 32
            [right] => 33
        )

    [18] => Array
        (
            [value] => Micheal Hart
            [left] => 34
            [right] => 35
        )

    [19] => Array
        (
            [value] => Anne
            [left] => 37
            [right] => 38
        )

    [20] => Array
        (
            [value] => Richard
            [left] => 39
            [right] => 40
        )

    [21] => Array
        (
            [value] => Edmond
            [left] => 41
            [right] => 42
        )

    [22] => Array
        (
            [value] => John
            [left] => 44
            [right] => 45
        )

)

所以问题是,如何最好地做到这一点？

我的解决方案是:

$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 Williams 的深度
:7,Williams右:24,Levels: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,如果没有邀请则为null

• 让我们说我想插入David一个孩子Judith,我该怎么做？
• 让我们说我想得到Mary Hart's父母和父母家长(array('Henery', 'Joan', 'Mary Hart')),我该怎么做？
• 比方说,我想删除William Hart从Joan我该怎么办呢？

Answer 1

要更新/删除，您将需要增加/减少left分支right所有元素的值。您可以在此处
找到查询示例。

效率如何我不知道。

嵌套集在更新/插入/删除时与大树一起工作非常缓慢。而且选择速度非常快。
因此，仅将此模型用于静态数据，这些数据在大多数情况下将不进行更改地存储，并且该树不会包含数千个节点（或者任何更新都需要几分钟才能完成）。物化路径的工作速度要快得多。