- 邻接表模型
- 嵌套集合模型
邻接表模型用于分层数据
邻接表模型是一种分级数据模型，其中每个节点有一个指向其父亲的指针（根节点该指针为空值），使用下面的SQL语句将建立该结构并插入测试数据：-- ------------------------------------------------------------ 表的结构 `category`--CREATE TABLE IF NOT EXISTS `category` ( `category_id` int(10) NOT NULL AUTO_INCREMENT, `category_name` varchar(50) NOT NULL, `parent_id` int(10) DEFAULT NULL, PRIMARY KEY (`category_id`)) ENGINE=InnoDB DEFAULT CHARSET=utf8 AUTO_INCREMENT=15 ;---- 转存表中的数据 `category`--INSERT INTO `category` (`category_id`, `category_name`, `parent_id`) VALUES(1, 'A', NULL),(2, 'B', 1),(3, 'C', 1),(4, 'D', 1),(5, 'E', 2),(6, 'F', 2),(7, 'I', 4),(8, 'G', 5),(9, 'H', 5),(10, 'J', 7),(11, 'K', 10),(12, 'L', 10);
建立完成后，数据库中存在了数据，并且分类图是这样的，每个节点为(关键字：数据库ID）：
parent_id就是它的父节点的ID号，这种方法非常简单，因为能很容易的看清楚父子关系。使用以下的简单PHP函数代码可以很容易的输出树状路径：
";//测试把SQL打印出来，拿到数据库执行一下看看结果 $result = mysql_query($sql); $row = mysql_fetch_array($result);//现在$row数组存了父亲节点的ID和名称信息 // 将树状路径保存在数组里面 $path = array(); //如果父亲节点不为空（根节点），就把父节点加到路径里面 if ($row['parent_id']!=NULL) { //将父节点信息存入一个数组元素 $parent[0]['category_id'] = $row['parent_id']; $parent[0]['category_name'] = $row['parent_name']; //递归的将父节点加到路径中 $path = array_merge(get_path($row['parent_id']), $parent); } return $path;}//根据上面的图可以看出，K的ID是11，我们就用它来测试路径$path = get_path(11);echo "路径数组：
";echo "";print_r($path);echo "
";//将路径到根节点的路径打印出来//打印结果：J>I>D>A>echo "向根节点打印路径：
";for ($i=count($path)-1; $i>=0; $i--){ echo $path[$i]['category_name']. '>';}?> 运行结果截图：
由此可以知道怎样找到一个叶子节点（没有孩子的节点）到根节点的路径，下面来看怎样从根节点往下来遍历层级结构，通过节点的层级关系来打印所有的节点：
"; // 递归的打印所有的孩子节点 display_children($row['category_id'], $level+1); }}//根节点是A:1我们就用它来打印所有的节点display_children(1, 0);?>
嵌套集合模型用于树形分层结构数据
嵌套集合模型，也叫做先根遍历树算法，也是一种处理树形层级数据的方法。代替节点间的父子关系，层级使用嵌套的容器的集合来表示，其中每个节点具有两个值，一个left，一个right。以下是例子的模拟图： 决定left和right的值的过程是从左到右进行的，首先给left赋值，让后向下遍历节点的孩子们，最后才能得到节点的right的值。SQL语句如下所示：CREATE TABLE category ( category_id INT(10) AUTO_INCREMENT PRIMARY KEY, category_name VARCHAR(50) NOT NULL, lft INT(10) NOT NULL, rgt INT(10) NOT NULL);现在可以用一句SQL查询得到整个树的节点： SELECT * FROM category WHERE lft BETWEEN 1 AND 14 ORDER BY lft ASC 在本SQL中的两个数字值1和14就是根节点的left和right值。类似的如果想得到某个节点的所有孩子节点，只需要将该SQL语句的1和14替换成本节点的left和right值就可以了。例如，如果想得到所有男人的衣服，可以用下面的SQL语句： SELECT * FROM category WHERE lft BETWEEN 2 AND 7 ORDER BY lft ASC 想找到一条到某个节点的路径，用一条SQL语句就可以搞定： SELECT * FROM category WHERE lft < 9 AND rgt > 10 ORDER BY lft ASC 请仔细观察一下一些叶子节点到根节点的路径。就会发现所有的祖先都有更小的左值和更大的右值。本例子中一条到裙子分类的路径被取出。观察一下裙子的所有left值都小于9，right值都大于10，其他的非祖先节点都不满足该要求。 尽管嵌套集合模型更加复杂并且有些难以理解，它有非常多的优势。它不需要依赖其他资源（比如PHP代码），也不需要递归。同时，数据库查询语句非常的简单，大多数用一条SQL语句就可以搞定。这些特性都能够显著的增加应用程序的性能，使得它能够用可接受的速度来处理复杂的层级结构。 然而万事皆无完美，更新该层级结构（增加或删除节点）却更加的复杂，并且可能会非常慢。 增加一个节点到层级结构的方法： 将一个节点插入到层级数据中，需要整个树很多节点的left和right值的更新。例如，如果你想将一个男士运动鞋的分类插入到男性衣服的短裤后面。那么所有你必须将大于6的所有left和right值都增加2。为什么呢？因为短裤的right值是6，那你就必须将你的新分类的left和right值设定为7和8，当然，以下两条SQL就可以解决：
UPDATE category SET rgt=rgt+2 WHERE rgt>6 UPDATE category SET lft=lft+2 WHERE lft>6 INSERT INTO category (category_name,lft,rgt) VALUES ( 'Sneakers' , '7' , '8' ) 树形层级数据中删除一个节点的方法：
在层级集合模型中删除一个节点的方法，比在邻接表中相同的操作稍微难一些。不同的操作的复杂程度是不同的，比如删除一个叶子节点和一个带孩子节点就很不同。
要删除一个叶子节点，先将所有left和right大于该节点left和right值的节点的left和right减去2，然后再删除该节点。以下使用SQL实现该过程：
UPDATE category SET lft=lft-2 WHERE lft>5 UPDATE category SET rgt=rgt-2 WHERE rgt>6 DELETE FROM category WHERE lft= '5' AND rgt= '6' 该例子中短裤节点被删除了。
如果要删除的节点有孩子节点的话，删除过程会多一个步骤:
比如我们删除男性衣服分类的时候：
UPDATE category SET lft=lft-1, rgt=rgt-1 WHERE lft>2 AND rgt<7 UPDATE category SET lft=lft-2 WHERE lft>7 UPDATE category SET rgt=rgt-2 WHERE rgt>7 DELETE FROM category WHERE lft= '2' AND rgt= '7'