hegz
- 浏览: 436293 次
- 性别:
- 来自: 茂名
-
文章分类
最新评论
-
zenmshuo：
不错不错，总结的很详细，不知道这个控件和FlexGrid比起来 ...
jQuery EasyUI教程之datagrid应用（三） -
我是你们的爹：
文章里太多错误了，容易误导新手
jQuery EasyUI教程之datagrid应用（三） -
我是你们的爹：
...
jQuery EasyUI教程之datagrid应用（一） -
zhehen123：
你傻啊,json_decode后面跟一个参数就可以转成普通数组 ...
如何将PHP对象数组转换成普通数组？ -
lai3221：
hegz,为什么做了没有任何效果呢？
jQuery EasyUI教程之datagrid应用（二）
文章来源：http://bbs.phpchina.com/viewthread.php?tid=92550&extra=page%3D1%26amp%3Bfilter%3Ddigest
（其
实也是转的
）
一、引言
产品分类，多级的树状结构的论坛 ，邮件列表等许多地方我们都会遇到这样的问题 ：如何存储多级结构的数据 ？在PHP 的应用中，提供后台数据存储的通常是关系型数据库 ，它能够保存大量的数据，提供高效的数据检索和更新 服务。然而关系型数据的基本形式是纵横交错的表，是一个平面的结构，如果要将多级树状结构存储在关系型数据库里就需要进行合理的翻译工作。接下来我会将自 己的所见所闻和一些实用的经验和大家探讨一下：
层级结构的数据保存在平面的数据库中基本上有两种常用设计 方法：
我不是计算机专业的，也没有学过什么数据结构的东西，所以这两个名字都是我自己按照字面的意思翻的，如果说错了还请多多指教。这两个东西听着好像很吓人， 其实非常容易理解。
二、模型
这里我用一个简单食品目录作为我们的示例数据。
我们的数据结构是这样的，以下是代码 ：
Food
|
|---Fruit
| |
| |---Red
| | |
| | |--Cherry
| |
| +---Yellow
| |
| +--Banana
|
+---Meat
|--Beef
+--Pork
为
了照顾那些英文一塌糊涂的PHP爱好者
Food : 食物
Fruit : 水果
Red : 红色
Cherry: 樱桃
Yellow: 黄色
Banana: 香蕉
Meat : 肉类
Beef : 牛肉
Pork : 猪肉
三、
实现
1、毗邻目录模式(adjacency list model)
这种模式我们经常用到，很多的教程 和书中也介绍过。我们通过给每个节点增加一个属性 parent 来表示这个节点的父节点从而将整个树状结构通过平面的表描述出来。根据这个原则，例子中的数据可以转化成如下的表：
以下是代码：
+-----------------------+
| parent | name |
+-----------------------+
| | Food |
| Food | Fruit |
| Fruit | Green |
| Green | Pear |
| Fruit | Red |
| Red | Cherry |
| Fruit | Yellow |
| Yellow | Banana |
| Food | Meat |
| Meat | Beef |
| Meat | Pork |
+-----------------------+
我
们看到 Pear 是Green的一个子节点，Green是Fruit的一个子节点。而根节点'Food'没有父节点。 为了简单地描述这个问题，
这个例子中只用了name来表示一个记录。 在实际的数据库中，你需要用数字的id来标示每个节点，数据库的表结构大概应该像这样：id,
parent_id, name, descrīption。
有了这样的表我们就可以通过数据库保存整个多级树状结构了。
显示多级树， 如果我们需要显示这样的一个多级结构需要一个递归函数 。
以下是代码：
<?php
// $parent is the parent of the children we want to see
// $level is increased when we go deeper into the tree,
// used to display a nice indented tree
function display_children ( $parent , $level ) {
// 获得一个 父节 点 $parent 的所有子节点
$result = mysql _query ( "
SELECT name
FROM tree
WHERE parent = '" . $parent . "'
;"
);
// 显示每个子节点
while ( $row = mysql_fetch_array ( $result )) {
// 缩进显示节点名称
echo str_repeat ( ' ' , $level ) . $row [ 'name' ] . "\n" ;
//再次调用这个函数显示子节 点的子节点
display_children ( $row [ 'name' ], $level + 1 );
}
}
?>
对整个结构的根节点（Food）使用这个
函数就可以打印出整个多级树结构，由于Food是根节点它的父节点是空的，所以这样调用:
display_children('',0)。将显示整个树的内容：
Food
Fruit
Red
Cherry
Yellow
Banana
Meat
Beef
Pork
如果你只想显示整个结构中的一部分，比如说水果部分，就可以这样
调用：display_children('Fruit',0);
几乎使用同样的方法我们可以知道从根节点到任意节点的路径。比如 Cherry 的路径是 "Food >; Fruit >; Red"。 为了得到这样的一个路径我们需要从最深的一级"Cherry"开始， 查询 得到它的父节点"Red"把它添加到路径中， 然后我们再查询Red的父节点并把它也添加到路径中，以此类推直到最高层的"Food",以下是代码：
<?php
// $node 是那个最深的节点
function get_path ( $node ) {
// 查询这个节点的父节点
$result = mysql_query ( "
SELECT parent
FROM tree
WHERE name = '" . $node . "'
;"
);
$row = mysql_fetch_array ( $result );
// 用一个数组保存路径
$path = array();
// 如果不是根节点则继续向上查询
// (根节点没有父节点)
if ( $row [ 'parent' ] != '' ) {
// the last part of the path to $node, is the name
// of the parent of $node
$path [] = $row [ 'parent' ];
// we should add the path to the parent of this node
// to the path
$path = array_merge ( get_path ( $row [ 'parent' ]), $path );
}
// return the path
return $path ;
}
?> ;
如果对"Cherry"使用这个
函数：print_r(get_path('Cherry'))，就会得到这样的一个数组了：
Array (
[0] => Food
[1] => Fruit
[2] => Red
)
接下来如何把它打印成你希望的格式，就是你的事情了。
缺点：
这种方法很简单，容易理解，好上手。但是也有一些缺点。主要是因为运行速度很慢，由于得到每个节点都需要进行数据库查询，数据量大的时候要进行很多查询才 能完成一个树。另外由于要进行递归运算，递归的每一级都需要占用一些内存所以在空间 利用上效率也比较低。
2、预排序遍历树算法
现在让我们看一看另外一种不使用递归计算，更加快速的方法，这就是预排序遍历树算法(modified preorder tree traversal algorithm)
这种方法大家可能接触的比较少，初次使用也不像上面的方法容易理解，但是由于这种方法不使用递归查询算法，有更高的查询效率。
我们首先将多级数据按照下面的方式画在纸上，在根节点Food的左侧写上 1 然后沿着这个树继续向下 在 Fruit 的左侧写上 2 然后继续前进，沿着整个树的边缘给每一个节点都标上左侧和右侧的数字。最后一个数字是标在Food 右侧的 18。 在下面的这张图中你可以看到整个标好了数字的多级结构。（没有看懂？用你的手指指着数字从1数到18就明白怎么回事了。还不明白，再数一遍，注意移动你的 手指）。
这些数字标明了各个节点之间的关系，"Red"的号是3和6，它是 "Food" 1-18 的子孙节点。 同样，我们可以看到 所有左值大于2和右值小于11的节点 都是"Fruit" 2-11 的子孙节点
以下是代码：
1 Food 18
|
+------------------------------+
| |
2 Fruit 11 12 Meat 17
| |
+-------------+ +------------+
| | | |
3 Red 6 7 Yellow 10 13 Beef 14 15 Pork 16
| |
4 Cherry 5 8 Banana 9
这样整个树状结构可以通过左右值来存储到数据库中。继续之前，我
们看一看下面整理过的数据表。
以下是代码：
以下是代码：
+------------+-----+-----+
| name | lft | rgt |
+------------+-----+-----+
| Food | 1 | 18 |
| Fruit | 2 | 11 |
| Red | 3 | 6 |
| Cherry | 4 | 5 |
| Yellow | 7 | 10 |
| Banana | 8 | 9 |
| Meat | 12 | 17 |
| Beef | 13 | 14 |
| Pork | 15 | 16 |
+------------+-----+-----+
好了我们现在可以从数据库中获取数据了，例如我们需要得
到"Fruit"项下的所有所有节点就可以这样写查询语句
：
SELECT * FROM tree WHERE lft BETWEEN 2 AND 11;
这个查询得到了以下的结果。
以下是代码：
+------------+-----+-----+
| name | lft | rgt |
+------------+-----+-----+
| Fruit | 2 | 11 |
| Red | 3 | 6 |
| Cherry | 4 | 5 |
| Yellow | 7 | 10 |
| Banana | 8 | 9 |
+------------+-----+-----+
看到了吧，只要一个查询就可以得到所有这些节点。为了能够像上
面的递归函数那样显示整个树状结构，我们还需要对这样的查询进行排序。用节点的左值进行排序：
SELECT * FROM tree WHERE lft BETWEEN 2 AND 11 ORDER BY lft ASC;
剩下的问题如何显示层级的缩进了。
以下是代码：
<?php
function display_tree ( $root ) {
// 得到根节点的左右值
$result = mysql_query ( "
SELECT lft, rgt
FROM tree
WHERE name = '" . $root . "'
;"
);
$row = mysql_fetch_array ( $result );
// 准备一个空的右值堆栈
$right = array();
// 获得根基点的所有子孙节点
$result = mysql_query ( "
SELECT name, lft, rgt
FROM tree
WHERE lft BETWEEN '" . $row [ 'lft' ] . "' AND '" . $row [ 'rgt' ] . "'
ORDER BY lft ASC
;"
);
// 显示每一行
while ( $row = mysql_fetch_array ( $result )) {
// only check stack if there is one
if ( count ( $right ) > 0 ) {
// 检查我们是否应 该将节点移出堆栈
while ( $right [ count ( $right ) - 1 ] < $row [ 'rgt' ]) {
array_pop ( $right );
}
}
// 缩进显示节点的名称
echo str_repeat ( ' ' , count ( $right )) . $row [ 'name' ] . "\n" ;
// 将这个节点加入到堆栈中
$right [] = $row [ 'rgt' ];
}
}
?>
如果你运行一下以上的函数就会得到和递归
函数一样的结果。只是我们的这个新的函数可能会更快一些，因为只有2次数据库查询。
要获知一个节点的路径就更简单了，如果我们想知道Cherry 的路径就利用它的左右值4和5来做一个查询。
SELECT name FROM tree WHERE lft < 4 AND rgt >; 5 ORDER BY lft ASC;
这样就
会得到以下的结果：
以下是代码：
+------------+
| name |
+------------+
| Food |
| Fruit |
| Red |
+------------+
那么某个节点到底有多少子孙节点呢？很简单，子孙总数=(右
值-左值-1)/2
descendants = (right – left - 1) / 2
不相
信？自己算一算啦。
用这个简单的公式，我们可以很快的算出"Fruit 2-11"节点有4个子孙节点，而"Banana 8-9"节点没有子孙节点，也就是说它不是一个父节点了。
很神奇吧？虽然我已经多次用过这个方法，但是每次这样做的时候还是感到很神奇。
这的确是个很好的办法，但是有什么办法能够帮我们建立这样有左右值的数据表呢？这里再介绍一个函数给大家，这个函数可以将name和parent结构的表 自动转换成带有左右值的数据表。
以下是代码：
<?php
function rebuild_tree ( $parent , $left ) {
// the right value of this node is the left value + 1
$right = $left + 1 ;
// get all children of this node
$result = mysql_query ( "
SELECT name
FROM tree
WHERE parent = '" . $parent . "'
;"
);
while ( $row = mysql_fetch_array ( $result )) {
// recursive execution of this function for each
// child of this node
// $right is the current right value, which is
// incremented by the rebuild_tree function
$right = rebuild_tree ( $row [ 'name' ], $right );
}
// we've got the left value, and now that we've processed
// the children of this node we also know the right value
mysql_query ( "
UPDATE tree
SET
lft = '" . $left . "',
rgt= '" . $right . "'
WHERE name = '" . $parent . "'
;"
);
// return the right value of this node + 1
return $right + 1 ;
}
?>
当然这个函数是一个递归函数，我们需要从
根节点开始运行这个函数来重建一个带有左右值的树
rebuild_tree( 'Food' , 1 );
这个函数看上去有些复杂，但是它的作用和
手工对表进行编号一样，就是将立体多层结构的转换成一个带有左右值的数据表。
那么对于这样的结构我们该如何增加，更新和删除一个节点呢？
增加一个节点一般有两种方法：
第一种，保留原有的name 和parent结构，用老方法向数据中添加数据，每增加一条数据以后使用rebuild_tree函数对整个结构重新进行一次编号。
第二种，效率更高的办法是改变所有位于新节点右侧的数值。举例来说：我们想增加一种新的水果"Strawberry"（草莓）它将成为"Red"节点的最 后一个子节点。首先我们需要为它腾出一些空间。"Red"的右值应当从6改成8，"Yellow 7-10 "的左右值则应当改成 9-12。 依次类推我们可以得知，如果要给新的值腾出空间需要给所有左右值大于5的节点 （5 是"Red"最后一个子节点的右值） 加上2。 所以我们这样进行数据库操作：
UPDATE tree SET rgt = rgt + 2 WHERE rgt > 5;
UPDATE tree SET lft = lft + 2 WHERE lft > 5;
这样就为新插入的值腾出了空间，现在可以在腾出的空间
里建立一个新的数据节点了， 它的左右值分别是6和7
INSERT INTO tree SET lft=6, rgt=7, name='Strawberry';
一、引言
产品分类，多级的树状结构的论坛 ，邮件列表等许多地方我们都会遇到这样的问题 ：如何存储多级结构的数据 ？在PHP 的应用中，提供后台数据存储的通常是关系型数据库 ，它能够保存大量的数据，提供高效的数据检索和更新 服务。然而关系型数据的基本形式是纵横交错的表，是一个平面的结构，如果要将多级树状结构存储在关系型数据库里就需要进行合理的翻译工作。接下来我会将自 己的所见所闻和一些实用的经验和大家探讨一下：
层级结构的数据保存在平面的数据库中基本上有两种常用设计 方法：
- 毗邻目录 模式(adjacency list model)
- 预排序遍历树算法(modified preorder tree traversal algorithm)
我不是计算机专业的，也没有学过什么数据结构的东西，所以这两个名字都是我自己按照字面的意思翻的，如果说错了还请多多指教。这两个东西听着好像很吓人， 其实非常容易理解。
二、模型
这里我用一个简单食品目录作为我们的示例数据。
我们的数据结构是这样的，以下是代码 ：
Food
|
|---Fruit
| |
| |---Red
| | |
| | |--Cherry
| |
| +---Yellow
| |
| +--Banana
|
+---Meat
|--Beef
+--Pork
Food : 食物
Fruit : 水果
Red : 红色
Cherry: 樱桃
Yellow: 黄色
Banana: 香蕉
Meat : 肉类
Beef : 牛肉
Pork : 猪肉
1、毗邻目录模式(adjacency list model)
这种模式我们经常用到，很多的教程 和书中也介绍过。我们通过给每个节点增加一个属性 parent 来表示这个节点的父节点从而将整个树状结构通过平面的表描述出来。根据这个原则，例子中的数据可以转化成如下的表：
以下是代码：
+-----------------------+
| parent | name |
+-----------------------+
| | Food |
| Food | Fruit |
| Fruit | Green |
| Green | Pear |
| Fruit | Red |
| Red | Cherry |
| Fruit | Yellow |
| Yellow | Banana |
| Food | Meat |
| Meat | Beef |
| Meat | Pork |
+-----------------------+
有了这样的表我们就可以通过数据库保存整个多级树状结构了。
显示多级树， 如果我们需要显示这样的一个多级结构需要一个递归函数 。
以下是代码：
<?php
// $parent is the parent of the children we want to see
// $level is increased when we go deeper into the tree,
// used to display a nice indented tree
function display_children ( $parent , $level ) {
// 获得一个 父节 点 $parent 的所有子节点
$result = mysql _query ( "
SELECT name
FROM tree
WHERE parent = '" . $parent . "'
;"
);
// 显示每个子节点
while ( $row = mysql_fetch_array ( $result )) {
// 缩进显示节点名称
echo str_repeat ( ' ' , $level ) . $row [ 'name' ] . "\n" ;
//再次调用这个函数显示子节 点的子节点
display_children ( $row [ 'name' ], $level + 1 );
}
}
?>
Food
Fruit
Red
Cherry
Yellow
Banana
Meat
Beef
Pork
几乎使用同样的方法我们可以知道从根节点到任意节点的路径。比如 Cherry 的路径是 "Food >; Fruit >; Red"。 为了得到这样的一个路径我们需要从最深的一级"Cherry"开始， 查询 得到它的父节点"Red"把它添加到路径中， 然后我们再查询Red的父节点并把它也添加到路径中，以此类推直到最高层的"Food",以下是代码：
<?php
// $node 是那个最深的节点
function get_path ( $node ) {
// 查询这个节点的父节点
$result = mysql_query ( "
SELECT parent
FROM tree
WHERE name = '" . $node . "'
;"
);
$row = mysql_fetch_array ( $result );
// 用一个数组保存路径
$path = array();
// 如果不是根节点则继续向上查询
// (根节点没有父节点)
if ( $row [ 'parent' ] != '' ) {
// the last part of the path to $node, is the name
// of the parent of $node
$path [] = $row [ 'parent' ];
// we should add the path to the parent of this node
// to the path
$path = array_merge ( get_path ( $row [ 'parent' ]), $path );
}
// return the path
return $path ;
}
?> ;
Array (
[0] => Food
[1] => Fruit
[2] => Red
)
缺点：
这种方法很简单，容易理解，好上手。但是也有一些缺点。主要是因为运行速度很慢，由于得到每个节点都需要进行数据库查询，数据量大的时候要进行很多查询才 能完成一个树。另外由于要进行递归运算，递归的每一级都需要占用一些内存所以在空间 利用上效率也比较低。
2、预排序遍历树算法
现在让我们看一看另外一种不使用递归计算，更加快速的方法，这就是预排序遍历树算法(modified preorder tree traversal algorithm)
这种方法大家可能接触的比较少，初次使用也不像上面的方法容易理解，但是由于这种方法不使用递归查询算法，有更高的查询效率。
我们首先将多级数据按照下面的方式画在纸上，在根节点Food的左侧写上 1 然后沿着这个树继续向下 在 Fruit 的左侧写上 2 然后继续前进，沿着整个树的边缘给每一个节点都标上左侧和右侧的数字。最后一个数字是标在Food 右侧的 18。 在下面的这张图中你可以看到整个标好了数字的多级结构。（没有看懂？用你的手指指着数字从1数到18就明白怎么回事了。还不明白，再数一遍，注意移动你的 手指）。
这些数字标明了各个节点之间的关系，"Red"的号是3和6，它是 "Food" 1-18 的子孙节点。 同样，我们可以看到 所有左值大于2和右值小于11的节点 都是"Fruit" 2-11 的子孙节点
以下是代码：
1 Food 18
|
+------------------------------+
| |
2 Fruit 11 12 Meat 17
| |
+-------------+ +------------+
| | | |
3 Red 6 7 Yellow 10 13 Beef 14 15 Pork 16
| |
4 Cherry 5 8 Banana 9
以下是代码：
+----------+------------+-----+-----+
| parent | name | lft | rgt |
+----------+------------+-----+-----+
| | 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 |
| Meat | Pork | 15 | 16 |
+----------+------------+-----+-----+
注意：由于"left"和"right"在 SQL
中有特殊的意义，所以我们需要用"lft"和"rgt"来表示左右字段。
另外这种结构中不再需要"parent"字段来表示树状结构。也就是 说下面这样的表结构就足够了。| parent | name | lft | rgt |
+----------+------------+-----+-----+
| | 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 |
| Meat | Pork | 15 | 16 |
+----------+------------+-----+-----+
以下是代码：
+------------+-----+-----+
| name | lft | rgt |
+------------+-----+-----+
| Food | 1 | 18 |
| Fruit | 2 | 11 |
| Red | 3 | 6 |
| Cherry | 4 | 5 |
| Yellow | 7 | 10 |
| Banana | 8 | 9 |
| Meat | 12 | 17 |
| Beef | 13 | 14 |
| Pork | 15 | 16 |
+------------+-----+-----+
SELECT * FROM tree WHERE lft BETWEEN 2 AND 11;
以下是代码：
+------------+-----+-----+
| name | lft | rgt |
+------------+-----+-----+
| Fruit | 2 | 11 |
| Red | 3 | 6 |
| Cherry | 4 | 5 |
| Yellow | 7 | 10 |
| Banana | 8 | 9 |
+------------+-----+-----+
SELECT * FROM tree WHERE lft BETWEEN 2 AND 11 ORDER BY lft ASC;
以下是代码：
<?php
function display_tree ( $root ) {
// 得到根节点的左右值
$result = mysql_query ( "
SELECT lft, rgt
FROM tree
WHERE name = '" . $root . "'
;"
);
$row = mysql_fetch_array ( $result );
// 准备一个空的右值堆栈
$right = array();
// 获得根基点的所有子孙节点
$result = mysql_query ( "
SELECT name, lft, rgt
FROM tree
WHERE lft BETWEEN '" . $row [ 'lft' ] . "' AND '" . $row [ 'rgt' ] . "'
ORDER BY lft ASC
;"
);
// 显示每一行
while ( $row = mysql_fetch_array ( $result )) {
// only check stack if there is one
if ( count ( $right ) > 0 ) {
// 检查我们是否应 该将节点移出堆栈
while ( $right [ count ( $right ) - 1 ] < $row [ 'rgt' ]) {
array_pop ( $right );
}
}
// 缩进显示节点的名称
echo str_repeat ( ' ' , count ( $right )) . $row [ 'name' ] . "\n" ;
// 将这个节点加入到堆栈中
$right [] = $row [ 'rgt' ];
}
}
?>
要获知一个节点的路径就更简单了，如果我们想知道Cherry 的路径就利用它的左右值4和5来做一个查询。
SELECT name FROM tree WHERE lft < 4 AND rgt >; 5 ORDER BY lft ASC;
以下是代码：
+------------+
| name |
+------------+
| Food |
| Fruit |
| Red |
+------------+
descendants = (right – left - 1) / 2
用这个简单的公式，我们可以很快的算出"Fruit 2-11"节点有4个子孙节点，而"Banana 8-9"节点没有子孙节点，也就是说它不是一个父节点了。
很神奇吧？虽然我已经多次用过这个方法，但是每次这样做的时候还是感到很神奇。
这的确是个很好的办法，但是有什么办法能够帮我们建立这样有左右值的数据表呢？这里再介绍一个函数给大家，这个函数可以将name和parent结构的表 自动转换成带有左右值的数据表。
以下是代码：
<?php
function rebuild_tree ( $parent , $left ) {
// the right value of this node is the left value + 1
$right = $left + 1 ;
// get all children of this node
$result = mysql_query ( "
SELECT name
FROM tree
WHERE parent = '" . $parent . "'
;"
);
while ( $row = mysql_fetch_array ( $result )) {
// recursive execution of this function for each
// child of this node
// $right is the current right value, which is
// incremented by the rebuild_tree function
$right = rebuild_tree ( $row [ 'name' ], $right );
}
// we've got the left value, and now that we've processed
// the children of this node we also know the right value
mysql_query ( "
UPDATE tree
SET
lft = '" . $left . "',
rgt= '" . $right . "'
WHERE name = '" . $parent . "'
;"
);
// return the right value of this node + 1
return $right + 1 ;
}
?>
rebuild_tree( 'Food' , 1 );
那么对于这样的结构我们该如何增加，更新和删除一个节点呢？
增加一个节点一般有两种方法：
第一种，保留原有的name 和parent结构，用老方法向数据中添加数据，每增加一条数据以后使用rebuild_tree函数对整个结构重新进行一次编号。
第二种，效率更高的办法是改变所有位于新节点右侧的数值。举例来说：我们想增加一种新的水果"Strawberry"（草莓）它将成为"Red"节点的最 后一个子节点。首先我们需要为它腾出一些空间。"Red"的右值应当从6改成8，"Yellow 7-10 "的左右值则应当改成 9-12。 依次类推我们可以得知，如果要给新的值腾出空间需要给所有左右值大于5的节点 （5 是"Red"最后一个子节点的右值） 加上2。 所以我们这样进行数据库操作：
UPDATE tree SET rgt = rgt + 2 WHERE rgt > 5;
UPDATE tree SET lft = lft + 2 WHERE lft > 5;
INSERT INTO tree SET lft=6, rgt=7, name='Strawberry';
再做一次查询看看吧！怎么样？很快吧。
四、结语
好了，现在你可以用两种不同的方法设计你的多级数据库结构了，采用何种方式完全取决于你个人的判断，但是对于层次多数量大的结构我更喜欢第二种方法。如果 查询量较小但是需要频繁添加和更新的数据，则第一种方法更为简便。
另外，如果数据库支持的话 你还可以将rebuild_tree()和 腾出空间的操作写成数据库端的触发器函数， 在插入和更新的时候自动执行， 这样可以得到更好的运行效率， 而且你添加新节点的SQL语句会变得更加简单。
分类相关：父 子ID法无限分类的简单实现算法
五、相关回复：
数据库结构:
采用左右值编码的保存该树的数据记录如下（设表名为tree）：
c_id | name | left_node | right_node
1 |商品 | 1 | 18
2 | 食品 | 2 | 11
3 | 肉类 | 3 | 6
4 | 猪肉 | 4 | 5
5 | 菜类 | 7 | 10
6 | 白菜 | 8 | 9
7 | 电器 | 2 | 17
8 | 电视 | 13 | 14
9 | 电棒 | 15 | 16
第一次看见上面的数据记录，相信大部分人都不清楚左值（left_node）和右值（right_node）是根据什么规则计算出来的，而且，这种表设计 似乎没有保存父节点的信息。下面把左右值和树结合起来，请看：
1商品18
+---------------------------------------+
2食品11 12电器17
+-----------------+ +---------------------+
3肉类6 7菜类10 13电视14 15电棒16
4猪肉5 8白菜9
请用手指指着上图中的数字，从1数到18，学习过数据结构的朋友肯定会发现什么吧？对，你手指移动的顺序就是对这棵树的进行先序遍历的顺序。接下来，让我 讲述一下如何利用节点的左右值，得到该节点的父节点，子孙节点数量，及自己在树中的层数。
采用左右值编码的设计方案，在进行类别树的遍历时，由于只需进行2次查询，消除了递归，再加上查询条件都为数字比较，效率极高，类别树的记录条目越多，执 行效率越高。
1、某个节点到底有多少子孙节点？
子孙总数 ＝（父节点的右值 - 父节点的左值-1）/2
以节点“食品”举例，其子孙总数＝（11-2-1）/ 2 ＝ 4
2、如何判断某一节点下有没有子节点？
当 该节点左值-1 等于 其右值 时，其下没有子节点。
3、检索某一父节点的所有子节点？
假定我们要对节点“食品”及其子孙节点进行先序遍历的列表，只需使用如下一条sql语句：
SELECT * FROM `tree` WHERE `left_node` BETWEEN 2 AND 11 ORDER BY `left_node` ASC
4、如何取得父类？
SELECT * FROM `tree` WHERE `left_node`<$left_node AND `right_node`>$right_node
5、检索之后如何列表？
当左值+1==右值时，该节点没有子节点，则下一节点不为其子节点
若下一节点的左值==上一节点右值+1，则2个节点是同级关系
若下一节点的左值==上一节点的左值+1时，则第2个节点应是第一个节点的子节点
若下一节点的左值-上一节点的右值>1时，则下一节点比上一节点高
（下一节点的左值-上一节点的右值）
级
6、在某一父节点下添加一个子节点？
1. 要求该子节点为该父节点下排序第一的节点，则$left_node = 父节点left_node+1, $right_node = $left_node+1;
2. 要求该节点位于父节点下一个子节点A后面，则$left_node = 节点A的right_node+1, $right_node = $left_node+1;
3. 要求该节点是位于父节点下排序最后一位的节点，则$left_node = 父节点right_node, $right_node = $left_node+1;
Sql:
UPDATE `tree` SET `right_node`=`right_node`+2 WHERE `right_node`>=$left_node
UPDATE `tree` SET `left_node`=`left_node`+2 WHERE `left_node`>=$left_node
INSERT INTO `tree` (`name` , `left_node` , `right_node`) VALUES
(`名字` , $left_node , $right_node)
7、移动节点，包括其子节点至节点A下？
设该节点左值$left_node , 右值$right_node
其子节点的数目为$count = ($right_node - $left_node -1 )/2 , 节点A左值为$A_left_node ,
UPDATE `tree` SET `right_node`=`right_node`-$right_node-$left_node-1 WHERE `right_node`>$right_node AND `right_node`<$A_left_node
UPDATE `tree` SET `left_node`=`left_node`-$right_node-$left_node-1 WHERE `left_node`>$right_node AND `left_node`<=$A_left_node
UPDATE `tree` SET `left_node`=`left_node`+$A_left_node-$right_node , `right_node`=`right_node`+$A_left_node-$right_node WHERE `left_node`>=$left_node
AND `right_node`<=$right_node
8、删除所有子节点？
DELETE FROM `tree` WHERE `left_node`>父节点的左值 AND `right_node`>父节点的右值
9、删除一个节点及其子节点？
在上例中的<号>号后面各加一个=号
采用左右值编码的保存该树的数据记录如下（设表名为tree）：
c_id | name | left_node | right_node
1 |商品 | 1 | 18
2 | 食品 | 2 | 11
3 | 肉类 | 3 | 6
4 | 猪肉 | 4 | 5
5 | 菜类 | 7 | 10
6 | 白菜 | 8 | 9
7 | 电器 | 2 | 17
8 | 电视 | 13 | 14
9 | 电棒 | 15 | 16
第一次看见上面的数据记录，相信大部分人都不清楚左值（left_node）和右值（right_node）是根据什么规则计算出来的，而且，这种表设计 似乎没有保存父节点的信息。下面把左右值和树结合起来，请看：
1商品18
+---------------------------------------+
2食品11 12电器17
+-----------------+ +---------------------+
3肉类6 7菜类10 13电视14 15电棒16
4猪肉5 8白菜9
请用手指指着上图中的数字，从1数到18，学习过数据结构的朋友肯定会发现什么吧？对，你手指移动的顺序就是对这棵树的进行先序遍历的顺序。接下来，让我 讲述一下如何利用节点的左右值，得到该节点的父节点，子孙节点数量，及自己在树中的层数。
采用左右值编码的设计方案，在进行类别树的遍历时，由于只需进行2次查询，消除了递归，再加上查询条件都为数字比较，效率极高，类别树的记录条目越多，执 行效率越高。
1、某个节点到底有多少子孙节点？
子孙总数 ＝（父节点的右值 - 父节点的左值-1）/2
以节点“食品”举例，其子孙总数＝（11-2-1）/ 2 ＝ 4
2、如何判断某一节点下有没有子节点？
当 该节点左值-1 等于 其右值 时，其下没有子节点。
3、检索某一父节点的所有子节点？
假定我们要对节点“食品”及其子孙节点进行先序遍历的列表，只需使用如下一条sql语句：
SELECT * FROM `tree` WHERE `left_node` BETWEEN 2 AND 11 ORDER BY `left_node` ASC
4、如何取得父类？
SELECT * FROM `tree` WHERE `left_node`<$left_node AND `right_node`>$right_node
5、检索之后如何列表？
当左值+1==右值时，该节点没有子节点，则下一节点不为其子节点
若下一节点的左值==上一节点右值+1，则2个节点是同级关系
若下一节点的左值==上一节点的左值+1时，则第2个节点应是第一个节点的子节点
若下一节点的左值-上一节点的右值>1时，则下一节点比上一节点高
（下一节点的左值-上一节点的右值）
级
6、在某一父节点下添加一个子节点？
1. 要求该子节点为该父节点下排序第一的节点，则$left_node = 父节点left_node+1, $right_node = $left_node+1;
2. 要求该节点位于父节点下一个子节点A后面，则$left_node = 节点A的right_node+1, $right_node = $left_node+1;
3. 要求该节点是位于父节点下排序最后一位的节点，则$left_node = 父节点right_node, $right_node = $left_node+1;
Sql:
UPDATE `tree` SET `right_node`=`right_node`+2 WHERE `right_node`>=$left_node
UPDATE `tree` SET `left_node`=`left_node`+2 WHERE `left_node`>=$left_node
INSERT INTO `tree` (`name` , `left_node` , `right_node`) VALUES
(`名字` , $left_node , $right_node)
7、移动节点，包括其子节点至节点A下？
设该节点左值$left_node , 右值$right_node
其子节点的数目为$count = ($right_node - $left_node -1 )/2 , 节点A左值为$A_left_node ,
UPDATE `tree` SET `right_node`=`right_node`-$right_node-$left_node-1 WHERE `right_node`>$right_node AND `right_node`<$A_left_node
UPDATE `tree` SET `left_node`=`left_node`-$right_node-$left_node-1 WHERE `left_node`>$right_node AND `left_node`<=$A_left_node
UPDATE `tree` SET `left_node`=`left_node`+$A_left_node-$right_node , `right_node`=`right_node`+$A_left_node-$right_node WHERE `left_node`>=$left_node
AND `right_node`<=$right_node
8、删除所有子节点？
DELETE FROM `tree` WHERE `left_node`>父节点的左值 AND `right_node`>父节点的右值
9、删除一个节点及其子节点？
在上例中的<号>号后面各加一个=号
分享到：
发表评论
-
如何将PHP对象数组转换成普通数组？
2014-03-18 16:54 18990如何将PHP对象数组转换成普通数组？ 在利用j ... -
拼音字典
2010-10-25 10:39 1211本人开发系统时用到的汉字转拼音代码： ... -
阿拉伯数字金额转大写人民币
2010-05-23 17:06 1392/** * 阿拉伯数字金额转大写人民币 * 最大 ... -
mb_convert_encoding函数使用方法介绍
2010-04-06 20:23 15438mb_convert_encoding 函数 ... -
将树形菜单dTree封装成PHP函数
2010-03-30 20:05 4091开发 系统 时，JavaScript树形菜单组件dTree ... -
中文字符串截取（支持gb2312、gbk、utf-8、big5）
2010-03-30 00:28 1390/* * 中文字符串截取，支持gb2312 ... -
开发非税代收系统部分功能代码
2010-03-30 00:05 1223将自己开发的功能代码保存在此，一是方便以后重用，二更是为了防防 ... -
自用代码[JSON编解码、日期校验]
2010-03-29 23:48 1586/** * 將数组转换成json格式数据 ...
相关推荐
本篇文章是对php左右值无限分类的实现算法进行了详细的分析介绍，需要的朋友参考下
数据库“路径法”无限级分类节点算法设计与实现.pdf
递归算法实现论坛简单无限分类递归算法实现论坛简单无限分类
1、资源配合博文《【python代码实现】决策树分类算法》、《【python代码实现】朴素贝叶斯分类算法》、《【python代码实现】人工神经网络分类算法及其实战案例（股票价格波动分析）》实操可掌握： 2、决策树分类算法...
3 FPGA二值图像边界提取算法实现 图2中我们使用串口传图传入的是二值图像。FPGA源码：/*Module name: boundary_extracTIon.vDescripTIon: binary image boundary extracTIon*/`TImescale 1ns/1psmodule boundary_...
QR算法求矩阵特征值的matlab实现
// AC 值的php 算法实现：主要是估算数据的离散程度， // 等效于所有数据出现的随机程度， // AC 小离散度小，数据理论度高，否则随机性大 不太可能计算的出来类似无
AR实现算法AR实现算法AR实现算法AR实现算法
使用MATLAB实现的图像二值化处理算法，有Otsu全局二值化算法，kittler 最小分类错误(minimum error thresholding)全局二值化算法，niblack局部二值化算法。
用C++实现的遗传算法求函数的最大值，可运行
五子棋AI算法-极大极小值搜索算法代码实现；适合学习机器学习算法的初学者，学完后会对极大极小值搜索算法（ Alpha Beta 剪枝算法。）有更深的理解。
KNN算法实现鸢尾花数据集分类 C语言实现 KNN算法实现鸢尾花数据集分类 C语言实现 KNN算法实现鸢尾花数据集分类 C语言实现 KNN算法实现鸢尾花数据集分类 C语言实现 KNN算法实现鸢尾花数据集分类 C语言实现 KNN...
通过修改完善教材中的算法3.1-3.4，利用栈来实现算术表达式求值的算法。对算法中调用的几个函数要给出其实现过程： (1) 函数In(c)：判断c是否为运算符； (2) 函数Precede(t1,t2)：判断运算符t1和t2的优先级； ...
模型算法大全（20+种常用算法模型+代码实现）模型算法大全（20+种常用算法模型+代码实现）模型算法大全（20+种常用算法模型+代码实现）模型算法大全（20+种常用算法模型+代码实现）模型算法大全（20+种常用算法模型+...
FPGA实现FFT算法 FPGA实现FFT算法 FPGA实现FFT算法
java实现朴素贝叶斯分类算法
MYSQL无限分类算法技术文档——MYSQL中分层数据的管理，不解MYSQL高级数据管理的相关技巧，包括了一些必要的SQL语句和高级数据管理的讲解，像邻接表模型、检索整树、检索所有叶子节点、检索单一路径、邻接表模型的...
二值化算法：Otsu算法、Bernsen算法、Niblack算法、循环阈值算法、迭代二值化算法等matlab代码,入门级
第一种方案： 使用递归算法，也是使用频率最多的，大部分开源程序也是这么处理，不过一般都只用到四级分类。这种算法的数据库结构设计最为简单。category表中一个字段id，一个字段fid(父id)。这样可以根据WHERE id =...