Infinite classification left and right value implementation algorithm

1. Introduction

In product classification, multi-level tree-structured forums, mailing lists and many other places we will encounter such problems: How to store multi-level structured data? In PHP applications, the backend data storage is usually a relational database, which can save large amounts of data and provide efficient data retrieval and update services. However, the basic form of relational data is a criss-crossed table, which is a flat structure. If you want to store a multi-level tree structure in a relational database, you need to perform reasonable translation work. Next, I will discuss with you what I have seen and heard and some practical experiences:
There are basically two common design methods for storing hierarchical data in flat databases:
* Adjacency list model
* Modified preorder tree traversal algorithm

2. Model

Here I use a simple food directory as our example data.
Our data structure is like this, the following is the code:

<code>Food
<span>|</span><span>|---Fruit</span><span>|    |</span><span>|    |---Red</span><span>|    |    |</span><span>|    |    |--Cherry</span><span>|    |</span><span>|    +---Yellow</span><span>|          |</span><span>|          +--Banana</span><span>|</span>
+---Meat
      <span>|--Beef</span>
      +--Pork</code>

In order to take care of those PHP enthusiasts who are messed up in English

<code>Food  : 食物
Fruit : 水果
Red   : 红色
<span>Cherry:</span> 樱桃
<span>Yellow:</span> 黄色
<span>Banana:</span> 香蕉
Meat  : 肉类
Beef  : 牛肉
Pork  : 猪肉</code>

3. Implementation

1. Adjacency list model (adjacency list model)

We often use this model Yes, it has been introduced in many tutorials and books. We describe the entire tree structure through a flat table by adding an attribute parent to each node to represent the parent node of this node. According to this principle, the data in the example can be transformed into the following table:
The following is the code:

<code><span>+-----------------------+</span><span>|   parent |    name    |
+-----------------------+</span>
|          |    Food    |
|   Food   |   Fruit    |
|   Fruit  |    Green   |
|   Green  |    Pear    |
|   Fruit  |    Red     |
|   Red    |    Cherry  |
|   Fruit  |    Yellow  |
|   Yellow |    Banana  |
|   Food   |    Meat    |
|   Meat   |    Beef    |
<span>|   Meat   |    Pork    |
+-----------------------+</span></code>

We see that Pear is a child node of Green, and Green is a child node of Fruit. The root node 'Food' has no parent node. In order to describe this problem simply, only name is used to represent a record in this example. In an actual database, you need to use a numeric ID to identify each node. The table structure of the database should probably look like this: id, parent_id, name, descrīption.
With such a table we can save the entire multi-level tree structure through the database.

Display multi-level trees. If we need to display such a multi-level structure, we need a recursive function.
The following is the code:

<code><span><span><?php</span><span>// $parent is the parent of the children we want to see</span><span>// $level is increased when we go deeper into the tree,</span><span>//        used to display a nice indented tree</span><span><span>function</span><span>display_children</span><span>(<span>$parent</span>, <span>$level</span>)</span> {</span><span>// 获得一个 父节点 $parent 的所有子节点</span><span>$result</span> = mysql_query(<span>"
        SELECT name
        FROM tree
        WHERE parent = '"</span> . <span>$parent</span> . <span>"'
        ;"</span>
    );
    <span>// 显示每个子节点</span><span>while</span> (<span>$row</span> = mysql_fetch_array(<span>$result</span>)) {
        <span>// 缩进显示节点名称</span><span>echo</span> str_repeat(<span>'  '</span>, <span>$level</span>) . <span>$row</span>[<span>'name'</span>] . <span>"\n"</span>;
        <span>//再次调用这个函数显示子节点的子节点</span>
        display_children(<span>$row</span>[<span>'name'</span>], <span>$level</span>+<span>1</span>);
    }
}
<span>?></span></span></code>

Use this function on the root node (Food) of the entire structure to print out the entire multi-level tree structure. Since Food is the root node and its parent node is empty, call it like this: display_children(", 0). Will display the contents of the entire tree:

<code>Food
    Fruit
        <span>Red</span>
            Cherry
        <span>Yellow</span>
            Banana
    Meat
        Beef
        Pork</code>

If you only want to display a part of the entire structure, such as the fruit part, you can call it like this: display_children('Fruit',0);

Almost use the same method We can know the path from the root node to any node. For example, the path of Cherry is "Food >; Fruit >; Red". In order to get such a path, we need to start from the deepest level "Cherry" and query it. The parent node "Red" adds it to the path, and then we query the parent node of Red and add it to the path, and so on until the top-level "Food", the following is the code:

<code><span><span><?php</span><span>// $node 是那个最深的节点</span><span><span>function</span><span>get_path</span><span>(<span>$node</span>)</span> {</span><span>// 查询这个节点的父节点</span><span>$result</span> = mysql_query(<span>"
        SELECT parent
        FROM tree
        WHERE name = '"</span> . <span>$node</span> .<span>"'
        ;"</span>
    );
    <span>$row</span> = mysql_fetch_array(<span>$result</span>);
    <span>// 用一个数组保存路径</span><span>$path</span> = <span>array</span>();
    <span>// 如果不是根节点则继续向上查询</span><span>// (根节点没有父节点)</span><span>if</span> (<span>$row</span>[<span>'parent'</span>] != <span>''</span>) {
        <span>// the last part of the path to $node, is the name</span><span>// of the parent of $node</span><span>$path</span>[] = <span>$row</span>[<span>'parent'</span>];
        <span>// we should add the path to the parent of this node</span><span>// to the path</span><span>$path</span> = array_merge(get_path(<span>$row</span>[<span>'parent'</span>]), <span>$path</span>);
    }
    <span>// return the path</span><span>return</span><span>$path</span>;
}
<span>?></span></span></code>

If yes "Cherry" uses this function: print_r(get_path('Cherry')), and you will get an array like this:

<code><span>Array</span> (
    [<span>0</span>] => Food
    [<span>1</span>] => Fruit
    [<span>2</span>] => Red
)</code>

How to print it into the format you want is up to you

Disadvantages. :
This method is simple, easy to understand, and easy to use. But there are some disadvantages. Mainly because the running speed is very slow, because each node requires a database query, and when the amount of data is large, many queries are required to complete a tree. In addition, due to the need for recursive operations, each level of recursion needs to occupy some memory, so the space utilization efficiency is relatively low.

2. Preorder tree traversal algorithm

Now let us take a look at another faster method that does not use recursive calculations. This is the modified preorder tree traversal algorithm (modified preorder tree traversal algorithm)
You may have less contact with this method, and it is not as easy to understand as the above method when you use it for the first time. However, because this method does not use a recursive query algorithm, it has higher query efficiency.

We first draw the multi-level data on paper as follows, write 1 on the left side of the root node Food, then continue down the tree, write 2 on the left side of Fruit, and then continue moving along the entire The edges of the tree label each node with numbers on the left and right. The last number is 18 marked to the right of Food. In the picture below you can see the entire multi-level structure marked with numbers. (Don’t understand? Point to the numbers with your fingers and count from 1 to 18 and you will understand. If you still don’t understand, count again and pay attention to moving your fingers).
These numbers indicate the relationship between each node. The numbers of "Red" are 3 and 6, which are the descendant nodes of "Food" 1-18. Similarly, we can see that all nodes with left values ​​greater than 2 and right values ​​less than 11 are descendant nodes of "Fruit" 2-11.
The following is the code:

<code><span>1</span> Food <span>18</span><span>|</span>
            +------------------------------+
            <span>|                              |</span><span>2</span> Fruit <span>11</span><span>12</span> Meat <span>17</span><span>|                              |</span>
    +-------------+                 +------------+
    <span>|             |                 |            |</span><span>3</span> Red <span>6</span><span>7</span> Yellow <span>10</span><span>13</span> Beef <span>14</span><span>15</span> Pork <span>16</span><span>|             |</span><span>4</span> Cherry <span>5</span><span>8</span> Banana <span>9</span></code>

In this way, the entire tree structure can be stored in the database through the left and right values. Before continuing, let's take a look at the compiled data table below.
Here is the code:

<code><span>+----------+</span>------------<span>+-----+</span>-----+
<span>|  parent  |    name    | lft | rgt |
+----------+------------+-----+-----+</span>
|          |    Food    | 1   | 18  |
|   Food   |   Fruit    | 2   | 11  |
|   Fruit  |    Red     | 3   |  6  |
|   Red    |    Cherry  | 4   |  5  |
|   Fruit  |    Yellow  | 7   | 10  |
|   Yellow |    Banana  | 8   |  9  |
|   Food   |    Meat    | 12  | 17  |
|   Meat   |    Beef    | 13  | 14  |
<span>|   Meat   |    Pork    | 15  | 16  |
+----------+------------+-----+-----+</span></code>

注意：由于”left”和”right”在 SQL中有特殊的意义，所以我们需要用”lft”和”rgt”来表示左右字段。 另外这种结构中不再需要”parent”字段来表示树状结构。也就是 说下面这样的表结构就足够了。
以下是代码：

<code><span>+------------+</span>-----<span>+-----+</span><span>|    name    | lft | rgt |
+------------+-----+-----+</span>
|    Food    | 1   | 18  |
|    Fruit   | 2   | 11  |
|    Red     | 3   |  6  |
|    Cherry  | 4   |  5  |
|    Yellow  | 7   | 10  |
|    Banana  | 8   |  9  |
|    Meat    | 12  | 17  |
|    Beef    | 13  | 14  |
<span>|    Pork    | 15  | 16  |
+------------+-----+-----+</span></code>

好了我们现在可以从数据库中获取数据了，例如我们需要得到”Fruit”项下的所有所有节点就可以这样写查询语句：

<code><span><span>SELECT</span> * <span>FROM</span> tree <span>WHERE</span> lft BETWEEN <span>2</span><span>AND</span><span>11</span>;</span></code>

这个查询得到了以下的结果。
以下是代码：

<code><span>+------------+</span>-----<span>+-----+</span><span>|    name    | lft | rgt |
+------------+-----+-----+</span>
|    Fruit   | 2   | 11  |
|    Red     | 3   |  6  |
|    Cherry  | 4   |  5  |
|    Yellow  | 7   | 10  |
<span>|    Banana  | 8   |  9  |
+------------+-----+-----+</span></code>

看到了吧，只要一个查询就可以得到所有这些节点。为了能够像上面的递归函数那样显示整个树状结构，我们还需要对这样的查询进行排序。用节点的左值进行排序：

<code><span><span>SELECT</span> * <span>FROM</span> tree <span>WHERE</span> lft BETWEEN <span>2</span><span>AND</span><span>11</span><span>ORDER</span><span>BY</span> lft <span>ASC</span>;</span></code>

剩下的问题如何显示层级的缩进了。
以下是代码：

<code><span><span><?php</span><span><span>function</span><span>display_tree</span><span>(<span>$root</span>)</span> {</span><span>// 得到根节点的左右值</span><span>$result</span> = mysql_query(<span>"
        SELECT lft, rgt
        FROM tree
        WHERE name = '"</span> . <span>$root</span> . <span>"'
        ;"</span>
    );
    <span>$row</span> = mysql_fetch_array(<span>$result</span>);
    <span>// 准备一个空的右值堆栈</span><span>$right</span> = <span>array</span>();
    <span>// 获得根基点的所有子孙节点</span><span>$result</span> = mysql_query(<span>"
        SELECT name, lft, rgt
        FROM tree
        WHERE lft BETWEEN '"</span> . <span>$row</span>[<span>'lft'</span>] . <span>"' AND '"</span> . <span>$row</span>[<span>'rgt'</span>] .<span>"'
        ORDER BY lft ASC
        ;"</span>
    );
    <span>// 显示每一行</span><span>while</span> (<span>$row</span> = mysql_fetch_array(<span>$result</span>)) {
        <span>// only check stack if there is one</span><span>if</span> (count(<span>$right</span>) > <span>0</span>) {
            <span>// 检查我们是否应该将节点移出堆栈</span><span>while</span> (<span>$right</span>[count(<span>$right</span>) - <span>1</span>] < <span>$row</span>[<span>'rgt'</span>]) {
                array_pop(<span>$right</span>);
            }
        }
        <span>// 缩进显示节点的名称</span><span>echo</span> str_repeat(<span>'  '</span>,count(<span>$right</span>)) . <span>$row</span>[<span>'name'</span>] . <span>"\n"</span>;
        <span>// 将这个节点加入到堆栈中</span><span>$right</span>[] = <span>$row</span>[<span>'rgt'</span>];
    }
}
<span>?></span></span></code>

如果你运行一下以上的函数就会得到和递归函数一样的结果。只是我们的这个新的函数可能会更快一些，因为只有2次数据库查询。
要获知一个节点的路径就更简单了，如果我们想知道Cherry 的路径就利用它的左右值4和5来做一个查询。

<code><span>SELECT</span> name <span>FROM</span> tree <span>WHERE</span> lft < <span>4</span><span>AND</span> rgt >; <span>5</span><span>ORDER</span><span>BY</span> lft <span>ASC</span>;</code>

这样就会得到以下的结果：
以下是代码：

<code><span>+------------+</span><span>|    name    |
+------------+</span>
|    Food    |
|    Fruit   |
<span>|    Red     |
+------------+</span></code>

那么某个节点到底有多少子孙节点呢？很简单，子孙总数=(右值-左值-1)/2

<code>descendants = (<span>right</span> – <span>left</span> - <span>1</span>) / <span>2</span></code>

不相信？自己算一算啦。
用这个简单的公式，我们可以很快的算出”Fruit 2-11”节点有4个子孙节点，而”Banana 8-9”节点没有子孙节点，也就是说它不是一个父节点了。
很神奇吧？虽然我已经多次用过这个方法，但是每次这样做的时候还是感到很神奇。
这的确是个很好的办法，但是有什么办法能够帮我们建立这样有左右值的数据表呢？这里再介绍一个函数给大家，这个函数可以将name和parent结构的表自动转换成带有左右值的数据表。
以下是代码：

<code><span><?php</span><span><span>function</span><span>rebuild_tree</span><span>(<span>$parent</span>, <span>$left</span>)</span> {</span><span>// the right value of this node is the left value + 1</span><span>$right</span> = <span>$left</span>+<span>1</span>;
    <span>// get all children of this node</span><span>$result</span> = mysql_query(<span>"
        SELECT name
        FROM tree
        WHERE parent = '"</span> . <span>$parent</span> . <span>"'
        ;"</span>
    );
    <span>while</span> (<span>$row</span> = mysql_fetch_array(<span>$result</span>)) {
        <span>// recursive execution of this function for each</span><span>// child of this node</span><span>// $right is the current right value, which is</span><span>// incremented by the rebuild_tree function</span><span>$right</span> = rebuild_tree(<span>$row</span>[<span>'name'</span>], <span>$right</span>);
    }
    <span>// we've got the left value, and now that we've processed</span><span>// the children of this node we also know the right value</span>
    mysql_query(<span>"
        UPDATE tree
        SET
            lft = '"</span> . <span>$left</span> . <span>"',
            rgt= '"</span> . <span>$right</span> . <span>"'
        WHERE name = '"</span> . <span>$parent</span> . <span>"'
        ;"</span>
    );
    <span>// return the right value of this node + 1</span><span>return</span><span>$right</span> + <span>1</span>;
}
<span>?></span></code>

当然这个函数是一个递归函数，我们需要从根节点开始运行这个函数来重建一个带有左右值的树

<code><span>rebuild_tree(<span>'Food'</span>,<span>1</span>)</span>;</code>

这个函数看上去有些复杂，但是它的作用和手工对表进行编号一样，就是将立体多层结构的转换成一个带有左右值的数据表。

那么对于这样的结构我们该如何增加，更新和删除一个节点呢？
增加一个节点一般有两种方法：
第一种，保留原有的name 和parent结构，用老方法向数据中添加数据，每增加一条数据以后使用rebuild_tree函数对整个结构重新进行一次编号。
第二种，效率更高的办法是改变所有位于新节点右侧的数值。举例来说：我们想增加一种新的水果”Strawberry”（草莓）它将成为”Red”节点的最后一个子节点。首先我们需要为它腾出一些空间。”Red”的右值应当从6改成8，”Yellow 7-10 “的左右值则应当改成 9-12。依次类推我们可以得知，如果要给新的值腾出空间需要给所有左右值大于5的节点 （5 是”Red”最后一个子节点的右值） 加上2。所以我们这样进行数据库操作：

<code><span><span>UPDATE</span> tree <span>SET</span> rgt = rgt + <span>2</span><span>WHERE</span> rgt > <span>5</span>;</span><span><span>UPDATE</span> tree <span>SET</span> lft = lft + <span>2</span><span>WHERE</span> lft > <span>5</span>;</span></code>

这样就为新插入的值腾出了空间，现在可以在腾出的空间里建立一个新的数据节点了， 它的左右值分别是6和7

<code><span><span>INSERT</span><span>INTO</span> tree <span>SET</span> lft=<span>6</span>, rgt=<span>7</span>, name=<span>'Strawberry'</span>;</span></code>

再做一次查询看看吧！怎么样？很快吧。

四、结语

好了，现在你可以用两种不同的方法设计你的多级数据库结构了，采用何种方式完全取决于你个人的判断，但是对于层次多数量大的结构我更喜欢第二种方法。如果查询量较小但是需要频繁添加和更新的数据，则第一种方法更为简便。
另外，如果数据库支持的话 你还可以将rebuild_tree()和 腾出空间的操作写成数据库端的触发器函数， 在插入和更新的时候自动执行， 这样可以得到更好的运行效率， 而且你添加新节点的SQL语句会变得更加简单。

http://www.cnblogs.com/guowei1027/archive/2009/12/14/1623507.html

以上就介绍了无限分类左右值实现算法，包括了方面的内容，希望对PHP教程有兴趣的朋友有所帮助。