在数据库中存储分层数据
? 无论您是想建立自己的论坛，还是想在网站上发布邮件列表中的消息，还是想编写自己的cms:总有一天，您会希望将分层数据存储在数据库中。而且，除非您使用类似XML的数据库，否则表是没有层次结构的；它们只是一个简单的列表。您必须找到一种方法来转换平面文件中的层次结构。
? 存储树是一个常见的问题，有多种解决方案。有两种主要的方法:邻接表模型和改进的前序树遍历算法。
? 在本文中，我们将探讨这两种保存分层数据的方法。我将用一个虚构的网上食品店的树作为例子。这家食品店按种类、颜色和类型来组织食物。这棵树看起来像这样:
? 本文包含许多代码示例，展示了如何保存和检索数据。因为我自己使用这种语言，而且许多其他人也使用或知道这种语言，所以我选择用PHP编写示例。你可以很容易地把它们翻译成你自己选择的语言。
邻接表模型
? 我们将尝试的第一种也是最优雅的方法叫做“邻接表模型”或“递归方法”。这是一个很好的方法，因为你只需要一个简单的函数来遍历你的树。在我们的食品商店中，邻接表看起来像这样:
? 如你所见，在邻接表方法中，你保存了每个节点的“父节点”。我们可以看到‘Pear’是‘Green’的子，是‘Fruit’的子等等。根节点“Food”没有父值。为了简单起见，我使用“title”值来标识每个节点。当然，在真实的数据库中，您将使用每个节点的数字id。
查询树结构
? 既然我们已经在数据库中插入了树，那么是时候编写一个显示函数了。该函数必须从根节点(没有父节点的节点)开始，然后应该显示该节点的所有子节点。对于这些子节点中的每一个，该函数都应该检索并显示该子节点的所有子节点。对于这些孩子，该函数应该再次显示所有孩子，依此类推。
? 您可能已经注意到，在这个函数的描述中有一个规则的模式。我们可以简单地编写一个函数，它检索某个父节点的子节点。然后，该函数应该为这些子节点中的每一个启动另一个自身实例，以显示它们的所有子节点。这就是“递归方法”得名的递归机制。
<?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) {
// retrieve all children of $parent
$result = mysql_query('SELECT title FROM tree '.
'WHERE parent="'.$parent.'";');
// display each child
while ($row = mysql_fetch_array($result)) {
// indent and display the title of this child
echo str_repeat(' ',$level).$row['title']."n";
// call this function again to display this
// child's children
display_children($row['title'], $level+1);
}
}
?>
? 为了显示整个树，我们将使用一个空字符串运行函数，如下所示$parent和$level = 0: display_children('',0);对于我们的食品商店树，该函数返回:
Food
Fruit
Red
Cherry
Yellow
Banana
Meat
Beef
Pork
? 注意，如果您只想查看一个子树，您可以告诉函数从另一个节点开始。例如，要显示“水果”子树，您可以运行display_children('Fruit',0);
节点的路径
? 使用几乎相同的函数，如果您只知道节点的名称或id，就可以查找到该节点的路径。例如，通往“樱桃”的道路是“食物”>“水果”>“红色”。为了得到这条路径，我们的函数必须从最深层开始:“Cherry”。然后，它查找该节点的父节点，并将它添加到路径中。在我们的示例中，这将是“红色”。如果我们知道’ Red ‘是’ Cherry ‘的父节点，我们可以通过使用到’ Red ‘的路径来计算到’ Cherry '的路径。这是由我们刚刚使用的函数给出的:通过递归查找父节点，我们将得到树中任何节点的路径。
<?php
// $node is the name of the node we want the path of
function get_path($node) {
// look up the parent of this node
$result = mysql_query('SELECT parent FROM tree '.
'WHERE title="'.$node.'";');
$row = mysql_fetch_array($result);
// save the path in this array
$path = array();
// only continue if this $node isn't the root node
// (that's the node with no parent)
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;
}
?>
? 这个函数现在返回给定节点的路径。它以数组的形式返回路径，所以为了显示路径，我们可以使用print_r(get_path('Cherry'));如果你为“Cherry”这样做，你会看到:
Array
(
[0] => Food
[1] => Fruit
[2] => Red
)
不足之处
? 正如我们刚刚看到的，这是一个很好的方法。这很容易理解，我们需要的代码也很简单。那么，邻接表模型的缺点是什么？在大多数编程语言中，它既慢又低效。这主要是由递归引起的。我们需要对树中的每个节点进行一次数据库查询。
? 由于每个查询都需要一些时间，这使得函数在处理大树时非常慢。
? 这个方法没有那么快的第二个原因是你可能会用到的编程语言。与Lisp等语言不同，大多数语言不是为递归函数设计的。对于每个节点，该函数启动其自身的另一个实例。因此，对于一个有四层的树，您将同时运行该函数的四个实例。由于每个函数都占用一片内存，并且需要一些时间来初始化，所以当应用于大树时，递归非常慢。
改进的前序树遍历
现在，让我们看看另一种存储树的方法。递归可能很慢，所以我们宁愿不使用递归函数。我们还想尽量减少数据库查询的数量。最好是，每个活动只有一个查询。
? 我们将从水平放置圣诞树开始。从根节点(’ Food ')开始，在它的左边写一个1。顺着树走到‘水果’，在旁边写一个2。这样，你沿着树的边走(遍历)，同时在每个节点的左右两边写一个数字。最后一个数字写在“食物”节点的右边。在此图像中，您可以看到整个编号树，以及一些指示编号顺序的箭头。
? 我们将这些数字称为左和右(例如，“食物”的左值是1，右值是18)。如您所见，这些数字表明了每个节点之间的关系。因为“红色”有数字3和6，所以它是1-18“食物”节点的后代。同样的，我们可以说左值大于2，右值小于11的所有节点都是2-11“果实”的后代。树结构现在存储在左值和右值中。这种遍历树并计数节点的方法被称为“改进的前序树遍历”算法。
? 在我们继续之前，让我们看看这些值在我们的表中是什么样子的:
? 请注意，单词“左”和“右”在SQL中有特殊的含义。因此，我们必须使用’ lft ‘和’ rgt '来标识列。还要注意，我们不再真正需要“parent”列。我们现在有了lft和rgt值来存储树结构。
查询树结构
? 如果您想使用一个包含左值和右值的表来显示树，您首先必须标识出您想要检索的节点。例如，如果您想要“Fruit”子树，您必须只选择左值在2和11之间的节点。在SQL中，这将是:
SELECT * FROM tree WHERE lft BETWEEN 2 AND 11;
返回:
? 这就是:一个查询中的一整棵树。为了像显示递归函数一样显示该树，我们必须在该查询中添加一个ORDER BY子句。如果您在表格中添加和删除行，您的表格可能不会按正确的顺序排列。因此，我们应该根据行的左侧值对行进行排序。
SELECT * FROM tree WHERE lft BETWEEN 2 AND 11 ORDER BY lft ASC;
? 剩下的唯一问题是缩进。
? 为了显示树结构，子节点应该比父节点缩进一些。我们可以通过保存一堆正确的值来做到这一点。每次从一个节点的子节点开始，都将该节点的正确值添加到堆栈中。您知道该节点的所有子节点的右值都小于父节点的右值，因此通过将当前节点的右值与堆栈中最后一个右节点的右值进行比较，您可以看到是否仍在显示该父节点的子节点。显示完一个节点后，从堆栈中删除它的右值。如果你计算堆栈中的元素，你将得到当前节点的级别。
<?php
function display_tree($root) {
// retrieve the left and right value of the $root node
$result = mysql_query('SELECT lft, rgt FROM tree '.
'WHERE title="'.$root.'";');
$row = mysql_fetch_array($result);
// start with an empty $right stack
$right = array();
// now, retrieve all descendants of the $root node
$result = mysql_query('SELECT title, lft, rgt FROM tree '.
'WHERE lft BETWEEN '.$row['lft'].' AND '.
$row['rgt'].' ORDER BY lft ASC;');
// display each row
while ($row = mysql_fetch_array($result)) {
// only check stack if there is one
if (count($right)>0) {
// check if we should remove a node from the stack
while ($right[count($right)-1]<$row['rgt']) {
array_pop($right);
}
}
// display indented node title
echo str_repeat(' ',count($right)).$row['title']."n";
// add this node to the stack
$right[] = $row['rgt'];
}
}
?>
? 如果您运行这段代码，您将得到与上面讨论的递归函数完全相同的树。我们的新函数可能会更快:它不是递归的，只使用两个查询。
节点的路径
? 有了这个新算法，我们还必须找到一种新的方法来获得到特定节点的路径。要获得这个路径，我们需要该节点的所有祖先的列表。
? 对于我们的新表结构，这真的不需要太多工作。例如，当您查看4-5“Cherry”节点时，您会看到所有祖先的左侧值都小于4，而所有右侧值都大于5。要获取所有祖先，我们可以使用以下查询:
SELECT title FROM tree WHERE lft < 4 AND rgt > 5 ORDER BY lft ASC;
? 注意，就像我们前面的查询一样，我们必须使用ORDER BY子句对节点进行排序。该查询将返回:
+-------+
| title |
+-------+
| Food |
| Fruit |
| Red |
+-------+
? 我们现在只需连接这些行，就可以得到通往“Cherry”的路径。
有多少后代
? 如果你给我一个节点的左右值，我可以用一点数学告诉你它有多少个后代。
? 随着每个后代将节点的右侧值增加2，后代的数量可以通过以下公式计算:
descendants = (right - left - 1) / 2
? 通过这个简单的公式，我可以告诉你，2-11 '水果’节点有4个后代节点，8-9 '香蕉’节点只是一个子节点，而不是父节点。
自动遍历树
? 既然您已经看到了使用这个表可以做的一些方便的事情，那么是时候学习如何自动创建这个表了。虽然这是一个很好的练习，第一次用一棵小树，我们真的需要一个脚本来为我们做所有这些计数和树行走。
? 让我们写一个脚本，将邻接表转换成修改过的前序树遍历表。
<?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 title 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['title'], $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 title="'.$parent.'";');
// return the right value of this node + 1
return $right+1;
}
?>
? 这是一个递归函数。你应该从rebuild_tree('Food',1);然后，该函数检索“Food”节点的所有子节点。
? 如果没有孩子，它设置它的左值和右值。左值给定，1，右值就是左值加1。如果有子节点，这个函数会重复，并返回最后一个右边的值。然后，该值被用作“Food”节点的正确值。
? 递归使得这个函数很难理解。然而，这个函数实现的结果与我们在本节开始时手动实现的结果相同。它遍历树，为它看到的每个节点添加一个。运行该函数后，您将看到左右值仍然相同(快速检查:根节点的右值应该是节点数的两倍)。
添加节点
? 我们如何向树中添加一个节点？有两种方法:您可以在表中保留父列，然后重新运行rebuild_tree()函数——一个简单但不优雅函数；或者，您可以更新新节点右侧所有节点的左值和右值。
? 第一种选择很简单。使用邻接表方法进行更新，使用改进的前序树遍历算法进行检索。如果想要添加一个新节点，只需将它添加到表中并设置父列。然后，您只需重新运行rebuild_tree()功能。这很简单，但是对于大树来说不是很有效。
? 添加和删除节点的第二种方法是更新新节点右侧所有节点的左值和右值。让我们看一个例子。我们想添加一种新的水果，一个“草莓”，作为最后一个节点和“红色”的子节点。首先，我们必须腾出一些空间。“红色”的正确值应该从6更改为8，7-10“黄色”节点应该更改为9-12等。更新“红色”节点意味着我们必须给所有大于5的左右值加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, title='Strawberry';
? 如果我们运行我们的display_tree()函数，我们将看到新的“草莓”节点已经成功地插入到树中:
Food
Fruit
Red
Cherry
Strawberry
Yellow
Banana
Meat
Beef
Pork
不足之处
? 首先，改进的前序树遍历算法似乎很难理解。它肯定没有邻接表方法简单。然而，一旦你习惯了左和右属性，很明显你可以用这种技术做几乎所有你可以用邻接表方法做的事情，而且改进的前序树遍历算法要快得多。更新树需要更多的查询，这比较慢，但是检索节点只需要一个查询。
结论
? 现在，您已经熟悉了在数据库中存储树的两种方式。虽然我对改进的前序树遍历稍有偏好，但在您的特定情况下，邻接表方法可能更好。我将让你自己判断。
? 最后一点注意:正如我已经说过的，我不建议您使用节点的标题来引用该节点。您确实应该遵循数据库规范化的基本规则。我没有使用数字标识，因为那样会降低示例的可读性。
