# 邻接列表模型和层次结构

在本教程中，您将学习如何使用邻接列表模型来管理MySQL中的分层数据。

## 邻接列表模型介绍

分层数据无处不在。它可以是博客类别(栏目)，产品层次结构或组织结构。

有很多方法来管理MySQL中的层次数据，邻接列表模型可能是最简单的解决方案。 由于其简单性，邻接列表模型是开发人员和数据库管理员非常受欢迎的选择。

在邻接列表模型中，每个节点都有一个指向其父节点的指针。顶级节点没有父节点。 请参阅以下类别的电子产品：

![img](http://www.yiibai.com/uploads/images/201707/2707/251170744_54135.png)

在使用邻接列表模型之前，应该熟悉一些术语：

* 电子设备(`Electronics`)是顶级节点或根节点。
* 笔记本电脑，相机和照片，手机和配件(`Laptops, Cameras & photo, Phones & Accessories`)节点是`Electronics`节点的子节点。反之亦然`Electronics`节点是`Laptops, Cameras & photo, Phones & Accessories`节点的父节点。
* 叶子节点是没有子节点的节点，例如`Laptops`，`PC`，`Android`，`iOS`等，而非叶节点是至少有一个子节点的节点。
* 一个节点的子孙节点被称为后代节点。一个节点的父节点，祖父节点等也被称为祖先节点。

要对此类树进行建模，我们可以创建一个名为`category`的表，其中包含三个列：`id`，`title`和`parent_id`，如下所示：

```sql
CREATE TABLE category (
  id int(10) unsigned NOT NULL AUTO_INCREMENT,
  title varchar(255) NOT NULL,
  parent_id int(10) unsigned DEFAULT NULL,
  PRIMARY KEY (id),
  FOREIGN KEY (parent_id) REFERENCES category (id) 
    ON DELETE CASCADE ON UPDATE CASCADE
);
```

表中的每一行都是由`id`列标识的树中的一个节点。 `parent_id`列是`category`表本身的外键。它像一个指向`id`列的指针。

**插入数据**

树的根节点没有父节点，因此`parent_id`设置为[NULL](http://www.yiibai.com/mysql/null.html)。其他节点必须只有一个父节点。

要[插入](http://www.yiibai.com/mysql/insert-statement.html)根节点数据，请将`parent_id`设置为`NULL`，如下所示：

```
INSERT INTO category(title,parent_id) 
VALUES('Electronics',NULL);
```

要插入非根节点，只需要将其`parent_id`设置为其父节点的`ID`值。 例如，`Laptop & PC`和`Cameras & Photos`，以及`Phone & Accessories`节点的`parent_id`设置为`1`，参考以下语句：

```sql
INSERT INTO category(title,parent_id) 
VALUES('Laptops & PC',1);

INSERT INTO category(title,parent_id) 
VALUES('Laptops',2);
INSERT INTO category(title,parent_id) 
VALUES('PC',2);

INSERT INTO category(title,parent_id) 
VALUES('Cameras & photo',1);
INSERT INTO category(title,parent_id) 
VALUES('Camera',5);

INSERT INTO category(title,parent_id) 
VALUES('Phones & Accessories',1);
INSERT INTO category(title,parent_id) 
VALUES('Smartphones',7);

INSERT INTO category(title,parent_id) 
VALUES('Android',8);
INSERT INTO category(title,parent_id) 
VALUES('iOS',8);
INSERT INTO category(title,parent_id) 
VALUES('Other Smartphones',8);

INSERT INTO category(title,parent_id) 
VALUES('Batteries',7);
INSERT INTO category(title,parent_id) 
VALUES('Headsets',7);
INSERT INTO category(title,parent_id) 
VALUES('Screen Protectors',7);
```

**查找根节点**

根节点是没有父节点的节点。换句话说，它的`parent_id`为`NULL`：

```sql
SELECT
    id, title
FROM
    category
WHERE
    parent_id IS NULL;
```

**查找节点的直接子节点**

以下查询获取根节点的直接子节点，参考以下查询语句 -

```sql
SELECT
    id, title
FROM
    category
WHERE
    parent_id = 1;
```

**查找叶节点**

叶节点是没有子节点的节点。

```sql
SELECT
    c1.id, c1.title
FROM
    category c1
        LEFT JOIN
    category c2 ON c2.parent_id = c1.id
WHERE
    c2.id IS NULL;
```

**查询整个树**

以下[递归公用表表达式](http://www.yiibai.com/mysql/recursive-cte.html)(CTE)检索整个类别树。 请注意，自从*MySQL 8.0*起，[CTE](http://www.yiibai.com/mysql/cte.html)功能已经可用了。

```sql
WITH RECURSIVE category_path (id, title, path) AS
(
  SELECT id, title, title as path
    FROM category
    WHERE parent_id IS NULL
  UNION ALL
  SELECT c.id, c.title, CONCAT(cp.path, ' > ', c.title)
    FROM category_path AS cp JOIN category AS c
      ON cp.id = c.parent_id
)
SELECT * FROM category_path
ORDER BY path;
```

**查询子树**

以下查询获取ID为`7`的`Phone＆Accessories`的子树。

```sql
WITH RECURSIVE category_path (id, title, path) AS
(
  SELECT id, title, title as path
    FROM category
    WHERE parent_id = 7
  UNION ALL
  SELECT c.id, c.title, CONCAT(cp.path, ' > ', c.title)
    FROM category_path AS cp JOIN category AS c
      ON cp.id = c.parent_id
)
SELECT * FROM category_path
ORDER BY path;
```

得到以下结果 -

![img](http://www.yiibai.com/uploads/images/201707/2707/478090709_86543.png)

**查询单个路径**

要查询从下到上的单一路径，例如从`iOS`到`Electronics`，请使用以下语句：

```sql
WITH RECURSIVE category_path (id, title, parent_id) AS
(
  SELECT id, title, parent_id
    FROM category
    WHERE id = 10 -- child node
  UNION ALL
  SELECT c.id, c.title, c.parent_id
    FROM category_path AS cp JOIN category AS c
      ON cp.parent_id = c.id
)
SELECT * FROM category_path;
```

**计算每个节点的级别**

假设根节点的级别为`0`，下面的每个节点都有一个等于其父节点的级别加`1`的级别。

```sql
WITH RECURSIVE category_path (id, title, lvl) AS
(
  SELECT id, title, 0 lvl
    FROM category
    WHERE parent_id IS NULL
  UNION ALL
  SELECT c.id, c.title,cp.lvl + 1
    FROM category_path AS cp JOIN category AS c
      ON cp.id = c.parent_id
)
SELECT * FROM category_path
ORDER BY lvl;
```

如下所示 -

![img](http://www.yiibai.com/uploads/images/201707/2707/356090708_65718.png)

**删除节点及其后代**

要[删除](http://www.yiibai.com/mysql/delete-statement.html)节点及其后代，只需删除节点本身，则所有后代将被删除的`DELETE CASCADE`自动删除

例如，要`Laptops & PC`节点及其子节点(`Laptops` , `PC`)，请使用以下语句：

```sql
DELETE FROM category 
WHERE
    id = 2;
```

**删除节点并提升其后子节点**

删除非叶节点并提升其后子节点：

* 首先，将节点的直接子节点的`parent_id`更新为新父节点的`ID`。
* 然后，删除节点。

例如，要删除`Smartphones`节点并其子项，例如`Android`，`iOS`，`Other Smartphones`节点：

首先，更新`Smartphones`的所有直接子节点项的`parent_id`：

```sql
UPDATE category 
SET 
    parent_id = 7 -- Phones & Accessories
WHERE
    parent_id = 5; -- Smartphones
```

其次，删除`Smartphones`节点：

```sql
DELETE FROM category 
WHERE
    id = 8;
```

两个语句都应该包含在一个事务中：

```sql
BEGIN;

UPDATE category 
SET 
    parent_id = 7 
WHERE 
    parent_id = 5;

DELETE FROM category 
WHERE 
    id = 8;

COMMIT;
```

**移动子树**

要移动子树，只需[更新](http://www.yiibai.com/mysql/update-data.html)子树的顶级节点的`parent_id`。 例如，要移动`Cameras & photo`作为`Phone and Accessories`的子节点，可使用以下语句：

```sql
UPDATE category 
SET 
    parent_id = 7
WHERE
    id = 5;
```

在本教程中，您已经学会了如何使用邻接列表模型来管理MySQL中的分层数据