我们经常需要在关系型数据库中保存一些树状结构数据，比如分类、菜单、论坛帖子树状回复等。常用的方法有两种：

1. 领接表的方式；

2. 预排序遍历树方式；

假设树状结构如下图：

领接表方式

主要依赖于一个 parent 字段，用于指向上级节点，将相邻的上下级节点连接起来，id 为自动递增自动，parent_id 为上级节点的 id。一目了然，“Java”是“Language”的子节点。

我们要显示树，PHP 代码也可以很直观，代码如下：
复制代码 代码如下:
<"margin-left:' . ($level * 12) . 'px">' . $row['name'] . '</div>';
        // 递归调用当前函数，显示再下一级的子节点
        show_children($row['id'], $level + 1);
    }
}
"codetitle">复制代码 代码如下:
<"//img.jbzj.com/file_images/article/201407/2014715105045117.gif" alt="" />

从根节点开始左边为 1，然后下一个节点的左边为 2，以此类推，到最低层节点之后，最低层节点的右边为其左边的数字加 1。顺着这些节点，我们可以很容易地遍历完整个树。根据上图，我们对数据表做一些改变，增加两个字段，lft 和 rgt 用于存储左右数字（由于 left 和 right 是 MySQL 的保留字，所以我们改用简写）。表中各行的内容也就变成了：

接下来看看显示树/子树是多么简单，只需要一条 SQL 语句即可，比如显示“Database”子树，则需要获取到“Database”的左右数字，左为 2，右为 11，那么 SQL 语句是：

复制代码 代码如下:
SELECT * FROM tree WHERE lft BETWEEN 2 AND 11;

SQL 语句是简单了，但我们所希望的缩进显示却是个问题。什么时候应该显示缩进？缩进多少单位？解决这个问题，需要使用堆栈，即后进先出（LIFO），每到一个节点，将其右边的数字压入堆栈中。我们知道，所有节点右边的值都比其父节点右边的值小，那么将当前节点右边的值和堆栈最上边的右边值进行比较，如果当前节点比堆栈最上边的值小，表示当前堆栈里边剩下的都是父节点了，这时可以显示缩进，堆栈的元素数量即是缩进深度。PHP 代码实现如下：
复制代码 代码如下:
<"margin-left:'.(count($stack)*12).'px">'.$row['name'].'</div>';
        // 将当前的节点压入堆栈里边，为循环后边的节点缩进显示做好准备
        array_push($stack, $row['rgt']);
    }
}
"codetitle">复制代码 代码如下:
SELECT name FROM tree WHERE lft <= 7 AND rgt >= 10 ORDER BY lft ASC;

PHP 函数实现如下：

复制代码 代码如下:
<"codetitle">复制代码 代码如下:
UPDATE tree SET rgt=rgt+2 WHERE rgt>9;
UPDATE tree SET lft=lft+2 WHERE lft>9;

位置空出来了，开始插入新节点吧：
复制代码 代码如下:
INSERT INTO tree SET lft=10, rgt=11, name='ORACLE 10';

调用 show_tree() 看看结果对不对  具体的 PHP 实现代码这里就不写了。

现在总结一下预排序遍历树方式的优缺点。缺点是算法比较抽象，不容易理解，增加节点的时候虽然只用了几条 SQL 语句，但可能会需要更新很多记录，从而造成阻塞。优点是树的构造，路径获取方面性能都比领接表方式好很多。也就是说，这个算法牺牲了一些写的性能来换取读的性能，在 WEB 应用中，读数据库的比例远大于写数据库的比例，所以预排序遍历树方式比领接表方式更加受欢迎，更加实用，很多应用中都能看到 MPTT 的影子，通常所用的表里都有字段 lft 和 rgt。