以关系型数据库实现树状结构，除了大家熟悉和容易理解的“邻接表模型”，还有另一种“嵌套集合模型”，其基本理论在网上都可找到，比如：

Mike Hillyer 的原作

http://mikehillyer.com/articles/managing-hierarchical-data-in-mysql/

陈建平对上文的译作

http://www.cnblogs.com/chinaontology/archive/2010/03/10/NestedSetModel.html

以及刘敏的博客中有上述译文版整理的 PDF 文档可以下载

http://www.liumin.name/20071117/acts_as_nested_set/

该文详细讲解了左右界的核心理论，便于大家从零开始理解“嵌套集合模型”。但是此文的例子只使用了最经典左右界 2 个字段，在涉及节点深度时的嵌套查询太多，SQL 执行的性能大为降低。雪峰结合网上学来的其它一些变通方案，增加了一个冗余的节点深度字段，降低了查询的复杂提高了执行性能，从而可用于真正的开发和生产环境。

本文以上述文章为基础，并且阅读本文需要了解“嵌套集合模型”的基本原理，如果还不了解，建议先阅读上述文档。

我们使用的情景案例，是层级的地区数据。先看建表的 SQL 语句：

CREATE TABLE IF NOT EXISTS `geo` (

  `cid` int(11) NOT NULL AUTO_INCREMENT,

  `name` varchar(20) NOT NULL,

  `depth` int(11) NOT NULL,

  `lft` int(11) NOT NULL,

  `rgt` int(11) NOT NULL,

  PRIMARY KEY (`cid`),

  KEY `lft` (`lft`),

  KEY `rgt` (`rgt`)

) ENGINE=InnoDB  DEFAULT CHARSET=utf8 ;

我在Mike Hillyer 的表结构上只增加了一个 depth 字段，用以表示节点深度。

以下从树状结构使用的主要功能需求逐个介绍一下。

插入新节点

先插入一个根节点，我们约定根节点的 depth 为1，当只有一个根节点时，它的左右界当然是 1 和 2，所以：

INSERT INTO geo (name, depth, lft, rgt) VALUES ('根', 1, 1, 2);

我们再逐个插入几个子节点，来熟悉一下插入节点对已有节点的影响。

子节点的 depth 是当前节点 depth +1，根据“嵌套集合模型”的数学原理，子节点的左界是当前节点的右界，子节点的右界是当前节点的右界加1，并且所有在当前节点右侧的节点的左右界都加2。所以：

INSERT INTO geo (name, depth, lft, rgt) VALUES ('北京', 1+1, 2, 2+1);

UPDATE geo SET lft=lft+2 WHERE lft>2;

UPDATE geo SET rgt=rgt+2 WHERE rgt>=2;

再插入一个子节点，此时父节点仍是根节点，但它的 rgt 值已更新为 4，而它的 depth 仍为 1，所以：

INSERT INTO geo (name, depth, lft, rgt) VALUES ('天津', 1+1, 4, 4+1);

UPDATE geo SET lft=lft+2 WHERE lft>4;

UPDATE geo SET rgt=rgt+2 WHERE rgt>=4;

其实插入子节点，只需要知道当前节点的 rgt 和 depth，再加上新建子节点的名字，可以做成个存储过程。但 SQL 的逻辑也没有特别复杂，也可以用程序以事务方式执行。

下面我把范例的数据的 SQL 帖出来，大家可以直接导入。有兴趣的可以继续自己练习自己插入新节点。

INSERT INTO `geo`

 (`cid`, `name`, `depth`, `lft`, `rgt`)

 VALUES

(1, '根', 1, 1, 22),

(2, '北京', 2, 2, 13),

(3, '天津', 2, 14, 19),

(4, '上海', 2, 20, 21),

(5, '东城