如何在数据库中存储一棵树，实现无限级分类

发表于 | 分类于

在工作中经常会遇到类似于组织机构这样有层级的数据，比如一个组织机构的数据

数据库应该怎么设计使得增删改查操作更高效？

解决方案

总的来说，解决方案有如下几种

  • Adjacency list（邻接表）
  • Path enumeration（路径枚举）
  • Closure table（闭包表）

Adjacency list（邻接表）

这是我们最常用的方法，使用 id 与 parent_id 来进行关联。这种设计叫“邻接表”。比如一个组织机构

1
2
3
4
5
6
7
/* 组织机构 */
CREATE TABLE sys_org
(
  id         BIGINT,        /* 机构id */
  parent_id  BIGINT,        /* 父机构id */
  name       VARCHAR(50)    /* 机构名称 */
);

这样每个机构都知道自己的上级机构是谁

id parent_id name
1 0 华南分公司
2 1 行政部
3 1 销售部
4 1 产品部
5 1 研发部
6 5 后台开发
7 6 Java开发
8 6 Python开发
9 5 前端开发
10 9 网页开发
11 9 Android开发
12 9 iOS开发

获取某个节点的下一级子节点

比如查询前端开发（id 为 9）这个节点的下一级节点

1
2
3
4
5
6
SELECT
  *
FROM
  sys_org
WHERE
  parent_id = 9

获取某个节点的子树

如果是 Oracle 数据库，那就好办了，可以利用 CONNECT BY 实现递归查询

比如查询前端开发（id 为 9）这个节点下的子树

1
2
3
4
5
6
7
8
SELECT
  * 
FROM
  sys_org
START WITH 
  id = 9 
CONNECT BY PRIOR 
  id = parent_id

如果是 MySQL 数据库，那就做不到，因为它不支持递归查询，无法用 1 条 SQL 语句实现，只能写一个递归，然后每次调用 1 条 SQL 语句去递归查询

新增节点

新增一个节点很简单，只需要知道 parent_id 即可，比如在后端开发节点（id 为 6）下添加一个节点

1
INSERT INTO sys_org (parent_id, name) VALUES (6, 'GO开发')

删除节点

首先判断这个节点有没有子树存在。如果有，要先把子树删除，最后再删除节点本身

Oracle 数据库可以结合 CONNECT BY 和 IN 来删除子树

1
2
3
4
DELETE FROM 
    sys_org
WHERE
    id IN (SELECT id FROM sys_org START WITH id = 9 CONNECT BY PRIOR id = parent_id)

MySQL 只能通过递归获取到子树的 id 列表，然后结合 DELETE 与 id IN (...) 进行删除

修改指向的父节点

只需要把 parent_id 修改了即可，操作简单

1
UPDATE sys_org SET parent_id = #{父节点的id} WHERE id = #{节点的id}

优势

这是最常用的解决方案，理解起来很容易

弊端

像“获取某个节点的子树”这种需求，对于 Oracle 还算友好，但是对与 MySQL 来说很难实现

Path enumeration（路径枚举）

用 path 来存储 root 到父节点的路径

1
2
3
4
5
6
/* 组织机构 */
CREATE TABLE `sys_org` (
	`id` BIGINT,         /* 机构id */
	`path` VARCHAR(150), /* 在机构树中从root节点到该节点的父节点的路径 */
	`name` VARCHAR(80)   /* 机构名称 */
);

没有了 parent_id，现在是通过 path 来确定节点的层级（约定 root 节点的 id 是 0）

id parent_id name
1 0/ 华南分公司
2 0/1/ 行政部
3 0/1/ 销售部
4 0/1/ 产品部
5 0/1/ 研发部
6 0/1/5/ 后台开发
7 0/1/5/6/ Java开发
8 0/1/5/6/ Python开发
9 0/1/5/ 前端开发
10 0/1/5/9/ 网页开发
11 0/1/5/9/ Android开发
12 0/1/5/9/ iOS开发

获取子节点的下一级子节点

比如获取前端开发（id 为 9）下的所有子节点

1
2
3
4
5
6
SELECT
    *
FROM
    sys_org
WHERE
    path = '0/1/5/9/'

获取子节点的子树

获取研发部（id 为 5）的子树

1
2
3
4
5
6
SELECT
    *
FROM
    sys_org
WHERE
    path LIKE '0/1/5/%'

删除节点

首先判断这个节点有没有子树存在。如果有，要先把子树删除，最后再删除节点本身

现在删除子树对于 Oracle 和 MySQL 的实现都是一样的

1
2
3
4
DELETE FROM 
    sys_org
WHERE
    id IN (SELECT id FROM sys_org WHERE path LIKE '0/1/5/%')

新增节点

麻烦之处在于 path 这个字段如何生成？比如给后台开发节点（id 为 6）添加一个子节点

首先获取到父节点的 path 与 id 拼接后的字符串

1
2
3
4
5
6
SELECT
    CONCAT(path, id, '/')
FROM
    sys_org
WHERE
    id = 6

得到结果

1
0/1/5/6/

然后再插入新节点

1
INSERT INTO sys_org (path, name) VALUES ('0/1/5/6/', 'Go开发')

修改指向的父节点

首先获取到父节点的 path 与 id 拼接后的字符串

1
2
3
4
5
6
SELECT
    CONCAT(path, id, '/')
FROM
    sys_org
WHERE
    id = 6

得到结果

1
0/1/5/6/

然后再修改

1
UPDATE sys_org SET path = '0/1/5/6/' WHERE id = 10

优势与弊端

现在无论是 Oracle 还是 MySQL，实现递归查询都没有问题，只需要使用 = 或者 LIKE 即可实现

弊端就是 LIKE 的性能稍微低一点

Closure table（闭包表）

闭包表是解决层级数据存储的一个简单而优雅的解决方案，它记录了树中所有节点间的关系，而不仅仅只有那些直接的父子关系

实现闭包表，需要两张表，一张是原来的机构表

1
2
3
4
5
6
/* 组织机构 */
CREATE TABLE sys_org
(
  id         BIGINT,        /* 机构id */  
  name       VARCHAR(50)    /* 机构名称 */
);

一张 tree_path 表。它有两个字段，每个字段都是指向 sys_org 表里的 id 字段

1
2
3
4
5
CREATE TABLE tree_path
(
  ancestor     BIGINT,   /* 祖先的id */  
  descendant   BIGINT    /* 后代的id */
);

现在不再使用 sys_org 来存储树的结构，而是将树中任何具有“祖先 — 后代”关系的节点都存放在 tree_path 表中。即使这两个节点之间不是直接的父子关系；同时，还增加一行指向节点自己

比如这样一个机构

那么华南分公司（id 为 1）的数据如下

祖先的id 后代的id
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9

研发部（id 为 3）的数据如下

祖先的id 后代的id
3 3
3 4
3 5
3 6
3 7
3 8
3 9

其实就是把节点本身和节点下的子树存在 tree_path 表中

获取某个节点的子树

比如后台开发（id 为 4）下的子树

1
2
3
4
5
6
7
8
9
10
SELECT
  org.*
FROM
  sys_org AS org
JOIN
  tree_path AS tree 
ON 
  org.id = tree.descendant
WHERE
  tree.ancestor = 4

获取某个节点的所有祖先

1
2
3
4
5
6
7
8
9
10
SELECT
  org.*
FROM
  sys_org AS org
JOIN
  tree_path AS tree 
ON 
  org.id = tree.ancestor
WHERE
  tree.descendant = 节点的ID

插入一个

应该使用哪种方案？

方案 表的个数 查询子节点 查询子树 插入 删除 引用完整性
邻接表 1 简单 困难 简单 简单 是
路径枚举 1 简单 简单 简单 简单 否
闭包表 2 简单 简单 简单 简单 是
  • 邻接表是最方便的设计，这种方案经常被使用
  • 如果使用的数据支持 CONNECT BY 的递归查询，那使用邻接表最好
  • 枚举路径能够很直观地展示出祖先到后代之间的路径。但它也使得数据的存储变得比较冗余
  • 闭包表是最通用的设计，并且这几个方案中，只有它可以允许一个节点属于多棵树。它要求一张额外的表来存储关系，使用空间换时间的方案减少计算所造成的消耗

MongoDB与Redis的实现

上面的方案都是基于关系型数据库来实现的，对于 NoSQL 应该如何实现？

参考