处理mysql中的嵌套集?

时间:2022-03-06 08:23:28

I have decided to follow http://www.artfulsoftware.com/mysqlbook/sampler/mysqled1ch20.html

我决定关注http://www.artfulsoftware.com/mysqlbook/sampler/mysqled1ch20.html

So now I am looking for some help with the code.

所以现在我正在寻找代码的一些帮助。

I am using their data for my testing, So, I visualized the tree being like so:

我正在使用他们的数据进行测试,因此,我将树可视化为:

    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'));

So if we want to insert that into the database we want to end up with

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

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
        )

)

So the issue comes to mind of, How best to do this?

所以我想到了这个问题,如何最好地做到这一点?

My solution was:

我的解决方案是:

$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);

How efficient it is I do not know.

效率如何我不知道。

But now onto the queries.

但现在进入查询。

To select all descendants of a node we can use

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

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`;

To select all descendants of a node, to a specific depth we can use
Note that we are selecting Descendants of William to a depth of 2
Williams left: 7, Williams right: 24, Levels: 2

要选择一个节点的所有后代,我们可以使用特定的深度注意我们选择威廉的后代到2威廉姆斯的深度:7,威廉姆斯右: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`;

So that's easy enough.

所以这很容易。

But now I want to know a few things,
Note that in the actual database as well as left/right all rows have a unique id, and a "parent" column containing their inviteers id, or null if not invited

但是现在我想知道一些事情,请注意,在实际数据库中以及左/右所有行都有唯一的id,以及包含其邀请者id的“父”列,如果没有邀请则为null

  • Lets say I want to insert David as a child of Judith, How do I do that?
  • 让我们说我想把大卫作为朱迪思的孩子插入,我该怎么做?

  • Lets say I want to get Mary Hart's Parent, and the Parents Parent (array('Henery', 'Joan', 'Mary Hart')), How do I do that?
  • 让我们说我想得到玛丽哈特的父母和父母的父母(阵容('Henery','琼','玛丽哈特')),我该怎么做?

  • Lets say I want to delete William Hart from Joan How so I do that?
  • 让我们说我想从Joan删除William Hart我是怎么做到的?

3 个解决方案

#1


1  

To update/delete you will need to increase/decrease left/right values of all elements of branch.
Examples of queries you can find here.

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

How efficient it is I do not know.

效率如何我不知道。

Nested sets works VERY slowly with big trees on update/insert/delete. And very fast to select.
So use this model only with static data, which will be stored without changes most of the time, and this tree will not contain thousands of nodes (or any update will take minutes to complete). Materialized path works much faster.

嵌套集在更新/插入/删除时使用大树非常缓慢地工作。并且选择速度非常快。因此,仅将此模型与静态数据一起使用,静态数据将在大多数情况下无需更改即可存储,并且此树将不包含数千个节点(或任何更新将需要几分钟才能完成)。物化路径的工作速度要快得多。

#2


1  

  • to get the parents of a node you need nodes with left_id < child.left_id and right_id > child.right_id, if you only want the direct ancestor choose the one from previous set with the highest left_id.

    要获取节点的父节点,您需要具有left_id child.right_id的节点,如果您只希望直接祖先选择具有最高left_id的先前集合中的节点。 和right_id>

  • to delete a node remove it and then lower twice all left/right ids that are greater than deleted element right id. if( leftId > deleted.leftId ) leftId-=2 same for rightId

    删除一个节点删除它然后降低两次大于删除元素右id的所有左/右id。对于rightId,if(leftId> deleted.leftId)leftId- = 2相同

  • to insert a node make some space for it adding+2 to all nodes with leftId > parent.rightId then parent.rightId += 2 then insert node with leftId = parent.rightId-2 and rightId=parent.rightId-1

    插入一个节点为它创建一些空间为所有节点添加+ 2,其中leftId> parent.rightId然后parent.rightId + = 2然后使用leftId = parent.rightId-2和rightId = parent.rightId-1插入节点

#3


0  

All of your questions can be solved very easy if you use a DFS for each relationship and then use your function calculate() again if you want it more detailed.

如果您为每个关系使用DFS,那么您的所有问题都可以轻松解决,如果您想要更详细,请再次使用函数calculate()。

#1


1  

To update/delete you will need to increase/decrease left/right values of all elements of branch.
Examples of queries you can find here.

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

How efficient it is I do not know.

效率如何我不知道。

Nested sets works VERY slowly with big trees on update/insert/delete. And very fast to select.
So use this model only with static data, which will be stored without changes most of the time, and this tree will not contain thousands of nodes (or any update will take minutes to complete). Materialized path works much faster.

嵌套集在更新/插入/删除时使用大树非常缓慢地工作。并且选择速度非常快。因此,仅将此模型与静态数据一起使用,静态数据将在大多数情况下无需更改即可存储,并且此树将不包含数千个节点(或任何更新将需要几分钟才能完成)。物化路径的工作速度要快得多。

#2


1  

  • to get the parents of a node you need nodes with left_id < child.left_id and right_id > child.right_id, if you only want the direct ancestor choose the one from previous set with the highest left_id.

    要获取节点的父节点,您需要具有left_id child.right_id的节点,如果您只希望直接祖先选择具有最高left_id的先前集合中的节点。 和right_id>

  • to delete a node remove it and then lower twice all left/right ids that are greater than deleted element right id. if( leftId > deleted.leftId ) leftId-=2 same for rightId

    删除一个节点删除它然后降低两次大于删除元素右id的所有左/右id。对于rightId,if(leftId> deleted.leftId)leftId- = 2相同

  • to insert a node make some space for it adding+2 to all nodes with leftId > parent.rightId then parent.rightId += 2 then insert node with leftId = parent.rightId-2 and rightId=parent.rightId-1

    插入一个节点为它创建一些空间为所有节点添加+ 2,其中leftId> parent.rightId然后parent.rightId + = 2然后使用leftId = parent.rightId-2和rightId = parent.rightId-1插入节点

#3


0  

All of your questions can be solved very easy if you use a DFS for each relationship and then use your function calculate() again if you want it more detailed.

如果您为每个关系使用DFS,那么您的所有问题都可以轻松解决,如果您想要更详细,请再次使用函数calculate()。