我们经常需要在关系型数据库中保存一些树状结构数据，比如分类、菜单、论坛帖子树状回复等。常用的方法有两种：
1. 领接表的方式；
2. 预排序遍历树方式；
假设树状结构如下图：
领接表方式
主要依赖于一个 parent 字段，用于指向上级节点，将相邻的上下级节点连接起来，id 为自动递增自动，parent_id 为上级节点的 id。一目了然，“Java”是“Language”的子节点。
我们要显示树，PHP 代码也可以很直观，代码如下：
复制代码 代码如下:
<?php
/**
* 获取父节点下的所有子节点
*
* @since 2011-05-18
*
* @param $parent_id 父节点 id，0 则显示整个树结构。
* @param $level 当前节点所处的层级，用于缩进显示节点。
* @return void
*/
function show_children ($parent_id = 0, $level = 0)
{
// 获取父节点下的所有子节点
$result = mysql_query('SELECT id, name FROM tree WHERE parent_id=' . intval($parent_id));
// 显示每个子节点
while ($row = mysql_fetch_array($result)) {
// 缩进显示
echo '<div>' . $row['name'] . '</div>';
// 递归调用当前函数，显示再下一级的子节点
show_children($row['id'], $level + 1);
}
}
?>
想要显示整个树结构，调用 show_children()。想要显示“Database”子树，则调用 show_children(2)，因为“Database”的 id 是 2。
还有一个经常用到的功能是获取节点路径，即给出一个节点，返回从根节点到当前节点的路径。用函数实现如下：
复制代码 代码如下:
<?php
/**
* @param $id 需要获取路径的当前节点的 id。
* @return array
*/
function get_path($id)
{
// 获取当前节点的父节点 id 和当前节点名
$result = mysql_query('SELECT parent_id, name FROM tree WHEREname'];
// 如果父节点非 0，即非根节点，则进行递归调用获取父节点的路径
if ($row['parent_id']) {
// 递归调用，获取父节点的路径，并且合并到当前路径数组的其它元素前边
$path = array_merge(get_path($row['parent_id']), $path);
}
return $path;
}
?>
想要获取“MySQL 5.0”的路径，调用 get_path(4)，4 即是这个节点的 id。
领接表方式的优点在于容易理解，代码也比较简单明了。缺点则是递归中的 SQL 查询会导致负载变大，特别是需要处理比较大型的树状结构的时候，查询语句会随着层级的增加而增加，WEB 应用的瓶颈基本都在数据库方面，所以这是一个比较致命的缺点，直接导致树结构的扩展困难重重。
排序遍历树方式
现在我们来聊聊第二种方式─预排序遍历树方式（即通常所说的 MPTT，Modified Preorder Tree Traversal）。此算法是在第一种方式的基础之上，给每个节点增加一个左、右数字，用于标识节点的遍历顺序，如下图所示：
从根节点开始左边为 1，然后下一个节点的左边为 2，以此类推，到最低层节点之后，最低层节点的右边为其左边的数字加 1。顺着这些节点，我们可以很容易地遍历完整个树。根据上图，我们对数据表做一些改变，增加两个字段，lft 和 rgt 用于存储左右数字（由于 left 和 right 是 MySQL 的保留字，所以我们改用简写）。表中各行的内容也就变成了：
接下来看看显示树/子树是多么简单，只需要一条 SQL 语句即可，比如显示“Database”子树，则需要获取到“Database”的左右数字，左为 2，右为 11，那么 SQL 语句是：
复制代码 代码如下:
SELECT * FROM tree WHERE lft BETWEEN 2 AND 11;