sailorlee
- 浏览: 42754 次
- 性别:
- 来自: 河北唐山
-
最近访客 更多访客>>
文章分类
最新评论
-
fangguojun：
在插入新记录是提到的把所有左值和右值大于5的节点加上2，这里的 ...
改进前序遍历树—–关于无限分类的问题 -
li6151770：
listeners:{
change:{
} ...
Ext实现页面表单Enter全键盘导航
产品分类，多级的树状结构的论坛，邮件列表等许多地方我们都会遇到这样的问题：如何存储多级结构的数据？在PHP的应用中，提供后台数据存储的通常是关系型数据库，它能够保存大量的数据，提供高效的数据检索和更新服务。然而关系型数据的基本形式是纵横交错的表，是一个平面的结构，如果要将多级树状结构存储在关系型数据库里就需要进行合理的翻译工作。接下来我会将自己的所见所闻和一些实用的经验和大家探讨一下：
层级结构的数据保存在平面的数据库中基本上有两种常用设计方法：
1、毗邻目录模式(adjacency list model)
2、预排序遍历树算法(modified preorder tree traversal algorithm)
我不是计算机专业的，也没有学过什么数据结构的东西，所以这两个名字都是我自己按照字面的意思翻的，如果说错了还请多多指教。
这两个东西听着好像很吓人，其实非常容易理解。这里我用一个简单食品目录作为我们的示例数据。
我们的数据结构是这样的
以下是代码：
为了照顾那些英文一塌糊涂的PHP爱好者
Food:食物
Fruit:水果
Red:红色
Cherry:樱桃
Yellow:黄色
Banana:香蕉
Meat:肉类
Beef:牛肉
Pork:猪肉
毗邻目录模式(adjacency list model)
这种模式我们经常用到，很多的教程和书中也介绍过。我们通过给每个节点增加一个属性 parent 来表示这个节点的父节点从而将整个树状结构通过平面的表描述出来。根据这个原则，例子中的数据可以转化成如下的表：
以下是代码：
我们看到 Pear 是Green的一个子节点，Green是Fruit的一个子节点。而根节点'Food'没有父节点。 为了简单地描述这个问题， 这个例子中只用了name来表示一个记录。 在实际的数据库中，你需要用数字的id来标示每个节点，数据库的表结构大概应该像这样：id, parent_id, name, description。
有了这样的表我们就可以通过数据库保存整个多级树状结构了。
显示多级树
如果我们需要显示这样的一个多级结构需要一个递归函数。
以下是代码：
对整个结构的根节点（Food）使用这个函数就可以打印出整个多级树结构，由于Food是根节点它的父节点是空的，所以这样调用: display_children('',0)。将显示整个树的内容：
如果你只想显示整个结构中的一部分，比如说水果部分，就可以这样调用：display_children('Fruit',0);
几乎使用同样的方法我们可以知道从根节点到任意节点的路径。比如 Cherry 的路径是 "Food >; Fruit >; Red"。 为了得到这样的一个路径我们需要从最深的一级"Cherry"开始， 查询得到它的父节点"Red"把它添加到路径中， 然后我们再查询Red的父节点并把它也添加到路径中，以此类推直到最高层的"Food"
以下是代码：
如果对"Cherry"使用这个函数：print_r(get_path('Cherry'))，就会得到这样的一个数组了：
接下来如何把它打印成你希望的格式，就是你的事情了。
缺点：
这种方法很简单，容易理解，好上手。但是也有一些缺点。主要是因为运行速度很慢，由于得到每个节点都需要进行数据库查询，数据量大的时候要进行很多查询才能完成一个树。另外由于要进行递归运算，递归的每一级都需要占用一些内存所以在空间利用上效率也比较低。
现在让我们看一看另外一种不使用递归计算，更加快速的方法，这就是预排序遍历树算法(modified preorder tree traversal algorithm)
这种方法大家可能接触的比较少，初次使用也不像上面的方法容易理解，但是由于这种方法不使用递归查询算法，有更高的查询效率。
我们首先将多级数据按照下面的方式画在纸上，在根节点Food的左侧写上 1 然后沿着这个树继续向下 在 Fruit 的左侧写上 2 然后继续前进，沿着整个树的边缘给每一个节点都标上左侧和右侧的数字。最后一个数字是标在Food 右侧的 18。 在下面的这张图中你可以看到整个标好了数字的多级结构。（没有看懂？用你的手指指着数字从1数到18就明白怎么回事了。还不明白，再数一遍，注意移动你的手指）。
这些数字标明了各个节点之间的关系，"Red"的号是3和6，它是 "Food" 1-18 的子孙节点。 同样，我们可以看到 所有左值大于2和右值小于11的节点 都是"Fruit" 2-11 的子孙节点
以下是代码：
这样整个树状结构可以通过左右值来存储到数据库中。继续之前，我们看一看下面整理过的数据表。
以下是代码：
注意：由于"left"和"right"在 SQL中有特殊的意义，所以我们需要用"lft"和"rgt"来表示左右字段。 另外这种结构中不再需要"parent"字段来表示树状结构。也就是 说下面这样的表结构就足够了。
以下是代码：
好了我们现在可以从数据库中获取数据了，例如我们需要得到"Fruit"项下的所有所有节点就可以这样写查询语句：
SELECT * FROM tree WHERE lft BETWEEN 2 AND 11;
这个查询得到了以下的结果。
以下是代码：
看到了吧，只要一个查询就可以得到所有这些节点。为了能够像上面的递归函数那样显示整个树状结构，我们还需要对这样的查询进行排序。用节点的左值进行排序：
SELECT * FROM tree WHERE lft BETWEEN 2 AND 11 ORDER BY lft ASC;
剩下的问题如何显示层级的缩进了。
以下是代码：
如果你运行一下以上的函数就会得到和递归函数一样的结果。只是我们的这个新的函数可能会更快一些，因为只有2次数据库查询。
要获知一个节点的路径就更简单了，如果我们想知道Cherry 的路径就利用它的左右值4和5来做一个查询。
SELECT name FROM tree WHERE lft < 4 AND rgt >; 5 ORDER BY lft ASC;
这样就会得到以下的结果：
以下是代码：
那么某个节点到底有多少子孙节点呢？很简单，子孙总数=(右值-左值-1)/2
descendants = (right – left - 1) / 2
不相信？自己算一算啦。
用这个简单的公式，我们可以很快的算出"Fruit 2-11"节点有4个子孙节点，而"Banana 8-9"节点没有子孙节点，也就是说它不是一个父节点了。
很神奇吧？虽然我已经多次用过这个方法，但是每次这样做的时候还是感到很神奇。
这的确是个很好的办法，但是有什么办法能够帮我们建立这样有左右值的数据表呢？这里再介绍一个函数给大家，这个函数可以将name和parent结构的表自动转换成带有左右值的数据表。
以下是代码：
当然这个函数是一个递归函数，我们需要从根节点开始运行这个函数来重建一个带有左右值的树
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';
再做一次查询看看吧！怎么样？很快吧。
好了，现在你可以用两种不同的方法设计你的多级数据库结构了，采用何种方式完全取决于你个人的判断，但是对于层次多数量大的结构我更喜欢第二种方法。如果查询量较小但是需要频繁添加和更新的数据，则第一种方法更为简便。
另外，如果数据库支持的话 你还可以将rebuild_tree()和 腾出空间的操作写成数据库端的触发器函数， 在插入和更新的时候自动执行， 这样可以得到更好的运行效率， 而且你添加新节点的SQL语句会变得更加简单。
层级结构的数据保存在平面的数据库中基本上有两种常用设计方法：
1、毗邻目录模式(adjacency list model)
2、预排序遍历树算法(modified preorder tree traversal algorithm)
我不是计算机专业的，也没有学过什么数据结构的东西，所以这两个名字都是我自己按照字面的意思翻的，如果说错了还请多多指教。
这两个东西听着好像很吓人，其实非常容易理解。这里我用一个简单食品目录作为我们的示例数据。
我们的数据结构是这样的
以下是代码：
CODE:
Food
|
|---Fruit
| |
| |---Red
| | |
| | |--Cherry
| |
| |---Yellow
| |
| |--Banana
|
|---Meat
|
|--Beef
|
|--Pork
|
|---Fruit
| |
| |---Red
| | |
| | |--Cherry
| |
| |---Yellow
| |
| |--Banana
|
|---Meat
|
|--Beef
|
|--Pork
为了照顾那些英文一塌糊涂的PHP爱好者
Food:食物
Fruit:水果
Red:红色
Cherry:樱桃
Yellow:黄色
Banana:香蕉
Meat:肉类
Beef:牛肉
Pork:猪肉
毗邻目录模式(adjacency list model)
这种模式我们经常用到，很多的教程和书中也介绍过。我们通过给每个节点增加一个属性 parent 来表示这个节点的父节点从而将整个树状结构通过平面的表描述出来。根据这个原则，例子中的数据可以转化成如下的表：
以下是代码：
CODE:
+-----------------------+
| parent | name |
+-----------------------+
| | Food |
| Food | Fruit |
| Fruit | Green |
| Green | Pear |
| Fruit | Red |
| Red | Cherry |
| Fruit | Yellow |
| Yellow | Banana |
| Food | Meat |
| Meat | Beef |
| Meat | Pork |
+-----------------------+
| 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, description。
有了这样的表我们就可以通过数据库保存整个多级树状结构了。
显示多级树
如果我们需要显示这样的一个多级结构需要一个递归函数。
以下是代码：
CODE:
<?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);
}
}
?>;
// $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)。将显示整个树的内容：
CODE:
Food
Fruit
Red
Cherry
Yellow
Banana
Meat
Beef
Pork
Fruit
Red
Cherry
Yellow
Banana
Meat
Beef
Pork
如果你只想显示整个结构中的一部分，比如说水果部分，就可以这样调用：display_children('Fruit',0);
几乎使用同样的方法我们可以知道从根节点到任意节点的路径。比如 Cherry 的路径是 "Food >; Fruit >; Red"。 为了得到这样的一个路径我们需要从最深的一级"Cherry"开始， 查询得到它的父节点"Red"把它添加到路径中， 然后我们再查询Red的父节点并把它也添加到路径中，以此类推直到最高层的"Food"
以下是代码：
CODE:
<?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;
}
?>;
// $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'))，就会得到这样的一个数组了：
CODE:
Array
(
[0] =>; Food
[1] =>; Fruit
[2] =>; Red
)
(
[0] =>; Food
[1] =>; Fruit
[2] =>; Red
)
接下来如何把它打印成你希望的格式，就是你的事情了。
缺点：
这种方法很简单，容易理解，好上手。但是也有一些缺点。主要是因为运行速度很慢，由于得到每个节点都需要进行数据库查询，数据量大的时候要进行很多查询才能完成一个树。另外由于要进行递归运算，递归的每一级都需要占用一些内存所以在空间利用上效率也比较低。
现在让我们看一看另外一种不使用递归计算，更加快速的方法，这就是预排序遍历树算法(modified preorder tree traversal algorithm)
这种方法大家可能接触的比较少，初次使用也不像上面的方法容易理解，但是由于这种方法不使用递归查询算法，有更高的查询效率。
我们首先将多级数据按照下面的方式画在纸上，在根节点Food的左侧写上 1 然后沿着这个树继续向下 在 Fruit 的左侧写上 2 然后继续前进，沿着整个树的边缘给每一个节点都标上左侧和右侧的数字。最后一个数字是标在Food 右侧的 18。 在下面的这张图中你可以看到整个标好了数字的多级结构。（没有看懂？用你的手指指着数字从1数到18就明白怎么回事了。还不明白，再数一遍，注意移动你的手指）。
这些数字标明了各个节点之间的关系，"Red"的号是3和6，它是 "Food" 1-18 的子孙节点。 同样，我们可以看到 所有左值大于2和右值小于11的节点 都是"Fruit" 2-11 的子孙节点
以下是代码：
CODE:
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
|
+-------------------------------------------+
| |
2 Fruit 11 12 Meat 17
| |
+------------------------+ +-----------------------+
| | | |
3 Red 6 7 Yellow 10 13 Beef 14 15 Pork 16
| |
4 Cherry 5 8 Banana 9
这样整个树状结构可以通过左右值来存储到数据库中。继续之前，我们看一看下面整理过的数据表。
以下是代码：
CODE:
+-----------------------+-----+-----+
| 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 |
+-----------------------+-----+-----+
| 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"字段来表示树状结构。也就是 说下面这样的表结构就足够了。
以下是代码：
CODE:
+------------+-----+-----+
| 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 |
+------------+-----+-----+
| 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;
这个查询得到了以下的结果。
以下是代码：
CODE:
+------------+-----+-----+
| name | lft | rgt |
+------------+-----+-----+
| Fruit | 2 | 11 |
| Red | 3 | 6 |
| Cherry | 4 | 5 |
| Yellow | 7 | 10 |
| Banana | 8 | 9 |
+------------+-----+-----+
| 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;
剩下的问题如何显示层级的缩进了。
以下是代码：
CODE:
<?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'];
}
}
?>;
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;
这样就会得到以下的结果：
以下是代码：
CODE:
+------------+
| name |
+------------+
| Food |
| Fruit |
| Red |
+------------+
| name |
+------------+
| Food |
| Fruit |
| Red |
+------------+
那么某个节点到底有多少子孙节点呢？很简单，子孙总数=(右值-左值-1)/2
descendants = (right – left - 1) / 2
不相信？自己算一算啦。
用这个简单的公式，我们可以很快的算出"Fruit 2-11"节点有4个子孙节点，而"Banana 8-9"节点没有子孙节点，也就是说它不是一个父节点了。
很神奇吧？虽然我已经多次用过这个方法，但是每次这样做的时候还是感到很神奇。
这的确是个很好的办法，但是有什么办法能够帮我们建立这样有左右值的数据表呢？这里再介绍一个函数给大家，这个函数可以将name和parent结构的表自动转换成带有左右值的数据表。
以下是代码：
CODE:
<?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;
}
?>;
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';
再做一次查询看看吧！怎么样？很快吧。
好了，现在你可以用两种不同的方法设计你的多级数据库结构了，采用何种方式完全取决于你个人的判断，但是对于层次多数量大的结构我更喜欢第二种方法。如果查询量较小但是需要频繁添加和更新的数据，则第一种方法更为简便。
另外，如果数据库支持的话 你还可以将rebuild_tree()和 腾出空间的操作写成数据库端的触发器函数， 在插入和更新的时候自动执行， 这样可以得到更好的运行效率， 而且你添加新节点的SQL语句会变得更加简单。
分享到：
发表评论
相关推荐
数据文件存储实际的数据库数据和元数据，日志文件记录所有对数据库的修改操作，以备恢复，而控制文件则保存数据库的关键配置信息。数据库管理系统（DBMS）通过存储管理器来管理这些文件，利用缓冲区（Buffer Cache）...
通过递归调用`nodes`方法，我们可以将子节点添加到当前节点下，形成多级结构。 最后，我们在`Form1_Load`事件处理程序中调用`nodes`方法，传入TreeView的根节点集合、数据集和0作为初始父节点ID，这样便完成了整个...
1. **分析数据需求**：明确数据库的目的，确定需要保存的主题信息，如商品、用户、订单等。 2. **将需求分类入表**：根据主题创建独立的表，例如，顾客信息、商品详情、交易记录等。 3. **确定所需字段**： - 每个...
在这个实训中，学生被要求掌握和运用链表或二叉树的数据结构来设计这样一个系统，而不允许使用数据库。 1. 实验目的： 实训的主要目标是提升学生的系统编程能力，使他们能从编写单一功能的程序过渡到开发完整系统...
1. 多级安全DBMS（Multi-level Secure Database Management System，MLS DBMS）：是指能够处理和存储不同安全级别的数据，并为不同安全级别的用户提供服务的数据库管理系统。在多级安全环境中，数据通常根据其安全...
后端逻辑主要负责从数据库中获取数据，并将其转换为前端可以使用的格式。 ##### 4.1 获取一级数据 ```java public List<TsFrom> getTsFrom() throws Exception { // 连接数据库并执行SQL语句获取数据 List...
总的来说，C#解压缩文件夹并保存目录结构是开发过程中的一项实用技能，结合ASP.NET可以构建强大的文件服务，结合SQLDBA知识可以优化数据库管理。京华志和精华志这样的社区提供了丰富的学习材料，鼓励开发者分享和...
Redis使用特定的数据结构保存这些值，例如，列表使用quicklist，哈希使用哈希表，集合可能是整数集合或使用跳表实现的无序集合，有序集合使用跳表加上附加的分数字段。 Redis的数据库由redisDb结构表示，其中包含了...
全备是指备份数据库中的所有数据和结构。这种备份方式非常直接，恢复时也较为便捷，但缺点是占用的存储空间较大，且在数据量大时备份时间会比较长。 ```shell mysqldump -u root -p your_database > your_...
4. **灵活的数据分区策略**：支持多种分区方法，如范围分区、哈希分区等，以优化数据分布和查询性能，同时支持多级分区，适应复杂的数据结构。 5. **用户自定义函数（UDF）支持**：允许使用Java、Python、C/C++、...
总之，网上购物系统的数据库设计是一个涉及多方面技术的综合性任务，需要结合业务需求，合理规划数据模型，优化数据结构，确保系统的高效稳定运行。在开发过程中，应持续关注性能监控，适时进行调整优化，以适应不断...
- **备份数据归档**：将不再频繁使用的备份数据转移到低成本的存储介质上，以便长期保存。 总之，Oracle 数据库的高可用性、性能优化以及备份恢复是确保数据库稳定运行不可或缺的组成部分。通过对这些关键技术点的...
多级存储结构通常包括高速缓存和持久化存储两部分，高速缓存用于快速访问最近或最频繁使用的数据，而持久化存储则用于长期保存数据，保证数据在系统重启后仍然可用。 实时数据库的数据处理流程如图1所示，包括...
比如，它可以使用“路径法”，即为每个分类保存一个包含所有父分类ID的字符串，如"1/2/3"，表示当前分类是属于1的子分类，2的孙子分类。这样，在获取分类树时，只需要根据这个路径一次性查询数据库，获取所有需要的...
其数据库结构是整个系统的核心，它存储了网站的各种信息，如用户数据、商品信息、广告、公告等。下面将详细解析Destoon数据库中的主要表及其功能。 1. **广告（ad）** 这个表主要用于存储网站上的各种广告信息，...
商品分类可能通过多级分类结构来实现，便于管理和搜索。 2. 供应商信息：供应商表会包含供应商的名称、联系方式、地址、供应商品列表等，便于跟踪进货渠道和管理供应商关系。 3. 客户信息：顾客表则保存了客户的...
根据提供的文件信息，我们可以推断出这是一本关于《数据结构与算法分析》（使用 C++ 实现）的书籍答案手册。以下是对该文件中提到的关键知识点进行详细解析： ### 数据结构与算法分析 #### 一、引言 在计算机科学...