MySQL php / MySQL最佳树形结构

在Web开发中，树形结构是一种非常常见的数据结构，比如网站的导航菜单、分类目录等等。MySQL和PHP是Web开发中常用的技术栈之一，那么在使用这两种技术的同时，如何设计和优化树形结构数据库模型呢？本文将介绍MySQL实现树形结构的三种方案，并分析各自的优缺点。

阅读更多：MySQL 教程

方案一：父ID组合键

该方案是最常见的实现方式之一，使用简单灵活，适用于节点层数较少的树形结构。其基本思路是：

将父节点的ID作为自己的一个字段存储在自己的记录中
每个节点都能快速定位其父节点
通过递归查询，可以得到任意节点的子孙节点

下面是一组示例数据表：

CREATE TABLE `tree` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `name` varchar(32) NOT NULL DEFAULT '',
  `parent_id` int(11) NOT NULL DEFAULT '0',
  `sortorder` int(11) NOT NULL DEFAULT '0',
  PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;

其中，name字段存储节点名称，sortorder用于排序。以一个简单的多级商品分类为例，插入一些数据用于测试：

INSERT INTO tree (name,parent_id) VALUES ('电脑',0);
INSERT INTO tree (name,parent_id) VALUES ('笔记本电脑',1);
INSERT INTO tree (name,parent_id) VALUES ('平板电脑',1);
INSERT INTO tree (name,parent_id) VALUES ('电视',0);
INSERT INTO tree (name,parent_id) VALUES ('液晶电视',4);
INSERT INTO tree (name,parent_id) VALUES ('等离子电视',4);

接着，可以使用如下SQL语句查询出某个节点的所有子孙节点：

WITH RECURSIVE sub_tree (id, name, parent_id, level, path) AS (
  SELECT id, name, parent_id, 0, CAST(id AS CHAR(100)) AS path 
  FROM tree WHERE id=1  -- 1表示查询根节点下的所有子节点，真实环境中需要动态传入需要查询的节点ID
  UNION ALL
  SELECT t.id, t.name, t.parent_id, sub_tree.level+1, CONCAT(sub_tree.path,',',t.id) 
  FROM tree t JOIN sub_tree ON t.parent_id=sub_tree.id
)
SELECT * FROM sub_tree ORDER BY path;

以上SQL语句使用了MySQL 8.0及以上版本的CTE(Common Table Expression)和递归查询特性，先是查询出父节点，再递归查询出所有的子孙节点。查询结果如下：

+----+-----------------+-----------+-------+---------+
| id | name            | parent_id | level | path    |
+----+-----------------+-----------+-------+---------+
| 1  | 电脑            | 0         | 0     | 1       |
| 2  | 笔记本电脑      | 1         | 1     | 1,2     |
| 3  | 平板电脑        | 1         | 1     | 1,3     |
| 4  | 电视            | 0         | 0     | 4       |
| 5  | 液晶电视        | 4         | 1     | 4,5     |
| 6  | 等离子电视      | 4         | 1     | 4,6     |
+----+-----------------+-----------+-------+---------+

这样，就可以通过一个节点的ID，查询其所有子孙节点了。

方案二：闭包表

闭包表（Closure Table）是一种创建树形结构模型的高效方式，其基本思路是：

创建一个新表，该表保存源节点与其所有祖先节点的关系
每个记录包含两个字段：祖先节点ID和后代节点ID
通过递归查询，可以得到任意节点的子孙节点

下面是一个简单的闭包表示例：

CREATE TABLE `tree_closure` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `ancestor` int(11) NOT NULL DEFAULT '0',
  `descendant` int(11) NOT NULL DEFAULT '0',
  `depth` int(11) NOT NULL DEFAULT '0',
  PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;

其中，ancestor字段存储祖先节点ID，descendant字段存储后代节点ID，depth字段表示两个节点之间的距离。以同样的商品分类为例，插入一些数据：

INSERT INTO tree_closure (ancestor, descendant, depth) VALUES (1,1,0);
INSERT INTO tree_closure (ancestor, descendant, depth) VALUES (1,2,1);
INSERT INTO tree_closure (ancestor, descendant, depth) VALUES (1,3,1);
INSERT INTO tree_closure (ancestor, descendant, depth) VALUES (4,4,0);
INSERT INTO tree_closure (ancestor, descendant, depth) VALUES (4,5,1);
INSERT INTO tree_closure (ancestor, descendant, depth) VALUES (4,6,1);

接着，可以使用如下SQL语句查询出某个节点的所有子孙节点：

SELECT t.*, (COUNT(tc.ancestor) - 1) AS depth 
FROM tree t JOIN tree_closure tc ON t.id = tc.descendant 
WHERE tc.ancestor = 1  -- 1表示查询根节点下的所有子节点，真实环境中需要动态传入需要查询的节点ID
GROUP BY t.id ORDER BY tc.depth;

以上SQL语句将tree表与tree_closure表进行了连接，并且使用了MySQL的聚合函数COUNT和GROUP BY，查询结果如下：

+----+-----------------+-----------+-------+
| id | name            | parent_id | depth |
+----+-----------------+-----------+-------+
| 1  | 电脑            | 0         | 0     |
| 2  | 笔记本电脑      | 1         | 1     |
| 3  | 平板电脑        | 1         | 1     |
| 4  | 电视            | 0         | 0     |
| 5  | 液晶电视        | 4         | 1     |
| 6  | 等离子电视      | 4         | 1     |
+----+-----------------+-----------+-------+

这样，就可以通过一个节点的ID，查询其所有子孙节点了。

方案三：嵌套集模型

嵌套集模型（Nested Set Model）是一种实现数据库中树形结构的方法，其基本思路是：

每个节点对应到数据库表中的一行记录
每个节点记录包含两个字段：左节点、右节点
左节点和右节点的值代表了节点在嵌套集中的位置
通过左右节点的范围查询，可以得到任意节点的子孙节点

首先，对于嵌套集模型，需要增加left和right两个字段：

CREATE TABLE `tree_nested_set` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `name` varchar(32) NOT NULL DEFAULT '',
  `left` int(11) NOT NULL DEFAULT '0',
  `right` int(11) NOT NULL DEFAULT '0',
  PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;

以同样的商品分类为例，插入一些数据：

INSERT INTO tree_nested_set (name, `left`, `right`) VALUES ('电脑', 1, 6);
INSERT INTO tree_nested_set (name, `left`, `right`) VALUES ('笔记本电脑', 2, 3);
INSERT INTO tree_nested_set (name, `left`, `right`) VALUES ('平板电脑', 4, 5);
INSERT INTO tree_nested_set (name, `left`, `right`) VALUES ('电视', 7, 12);
INSERT INTO tree_nested_set (name, `left`, `right`) VALUES ('液晶电视', 8, 9);
INSERT INTO tree_nested_set (name, `left`, `right`) VALUES ('等离子电视', 10, 11);

接着，可以使用如下SQL语句查询出某个节点的所有子孙节点：

SELECT t.*, (COUNT(tparent.id) - (sub_tree.depth + 1)) AS depth 
FROM tree_nested_set AS t, tree_nested_set AS tparent, tree_nested_set AS sub_parent, 
(SELECT node.id, (COUNT(parent.id) - 1) AS depth FROM tree_nested_set AS node, 
tree_nested_set AS parent WHERE node.`left` BETWEEN parent.`left` AND parent.`right` 
GROUP BY node.id ORDER BY node.`left`) AS sub_tree 
WHERE t.`left` BETWEEN sub_parent.`left` AND sub_parent.`right` AND sub_parent.id=sub_tree.id 
AND tparent.id=sub_parent.id AND sub_tree.id=1 -- 1表示查询根节点下的所有子节点，真实环境中需要动态传入需要查询的节点ID
GROUP BY t.id ORDER BY t.`left`;

以上SQL语句使用了MySQL的多表连接、聚合函数、子查询等技巧，比较复杂。但是查询效率较高，因为它不需要进行递归查询。查询结果如下：

+----+-----------------+------+-------+
| id | name            | left | right |
+----+-----------------+------+-------+
| 1  | 电脑            | 1    | 6     |
| 2  | 笔记本电脑      | 2    | 3     |
| 3  | 平板电脑        | 4    | 5     |
| 4  | 电视            | 7    | 12    |
| 5  | 液晶电视        | 8    | 9     |
| 6  | 等离子电视      | 10   | 11    |
+----+-----------------+------+-------+

这样，就可以通过一个节点的ID，查询其所有子孙节点了。