前言

本文基于mysql数据库探讨。

关于在数据库中存储树形结构，一直以来是一个比较头疼的问题。mysql 8中支持了 with recursive 语法，查询起来通过一个sql就能行，但是在 mysql 5.7 中还不支持，也就衍生了一些，方便 树形结构查询的方案，本文根据以往的经验做一个总结。探讨一下这些方案的优劣。

准备

Tips： 日常最常见的树形结构有 行政区划、部门组织。此处以简单的部门组织为例，展开叙述。

Tips： 以下方案皆通过 mysql 5.7 进行优化。 mysql 8 可以使用 CTE 语法。

-- 此处为最初的为经过优化的 简化版本部门表
create table sys_dept
(
    dept_id     bigint auto_increment comment '部门id' primary key,
    parent_id   bigint      default 0   null comment '父部门id',
    dept_name   varchar(30) default ''  null comment '部门名称',
    status      char        default '0' null comment '部门状态（0正常 1停用）',
    del_flag    char        default '0' null comment '删除标志（0代表存在 2代表删除）'
)
    comment '部门表';

详述

第一版本

在准备一节中，准备了一张表，该表中存储了上级部门的 ID ，以此来确定树形关系。这个版本中，有这非常明显的问题，比如：我们要查一个部门下所有的子级、查询指定级别的部门等等。查询起来都是比较麻烦的，只能在代码里面通过 递归 的方式，多次连接数据库才能达到目的，如果层级比较多的话，单单是数据库连接耗时也会是不小的开销（即使有连接池）。

第二版本

根据第一版本中非常明显的问题，可以创建 ancestors（祖级列表），level（级别） 字段，使得查询更加方便，存储的体积会稍微增大，但是相较于在数据多的情况，这点可以忽略。表结构就变成了以下：

create table sys_dept
(
    dept_id     bigint auto_increment comment '部门id' primary key,
    parent_id   bigint      default 0   null comment '父部门id',
    dept_name   varchar(30) default ''  null comment '部门名称',
    ancestors   varchar(50) default ''  null comment '祖级列表',
    level       int         DEFAULT     NULL COMMENT '层级',
    status      char        default '0' null comment '部门状态（0正常 1停用）',
    del_flag    char        default '0' null comment '删除标志（0代表存在 2代表删除）'
)
    comment '部门表';

-- ancestors 存储数据示例：0,100,201,389,532 
-- 可以利用 mysql 的函数 find_in_set 很方便的查询所有的下级

这个版本已经足够应付大部分的场景。但如果需要查询 一个部门 从 root 到 自身的完整链路。 例如：查询后端组的全部名称（北京卡路里信息科技有限公司 - 研发部 - 后端组）。

第三版本

第三个版本就需要一个很巧妙的思想，就是将要查询的上级约束在一个范围以内，并且 level 是不一样的。也就是演变成如下表结构：

create table sys_dept
(
    dept_id   bigint auto_increment comment '部门id' primary key,
    parent_id bigint      default 0   null comment '父部门id',
    dept_name varchar(30) default ''  null comment '部门名称',
    ancestors varchar(50) default ''  null comment '祖级列表',
    level     int         DEFAULT NULL COMMENT '层级',
    `left`    int         DEFAULT NULL COMMENT '左边界',
    `right`   int         DEFAULT NULL COMMENT '右边界',
    status    char        default '0' null comment '部门状态（0正常 1停用）',
    del_flag  char        default '0' null comment '删除标志（0代表存在 2代表删除）'
)
    comment '部门表';

-- ancestors 字段在这个版本中其实是可以删除的，为了方便对比，在此处暂时留着

为便于理解，给出数据表中数据示例：

简单来说，这个版本的思想就是，将一个树形结构约束到一个范围以内。
再看一下插入流程（详细说明 left、right 的变化）：

1. 插入研发部

left  right
 1      2

2. 插入研发部-1

left  right
 1      4
 2      3

3. 插入研发部-1-1

left  right
 1      6
 2      5
 3      4

…

在插入的时候每一次都需要变换 left、right。相应的在插入的时候会消耗一定的时间，但是相比较与每次查询所花费的时间，还是可以接受的。并且一般情况下，这种树形结构的数据变动的次数不会特别频繁。

预排序遍历树（Modified Preorder Tree Traversal，MPTT）: 从根节点开始，沿着树的前序遍历方向，为每个节点分配一个唯一的左值（lft）和右值（rgt）。节点的左值小于其所有子孙节点的左值，右值大于其所有子孙节点的右值。通过这种方式，可以方便地通过lft和rgt字段的范围查询来确定节点的上下级关系，而无需使用递归查询，提高了查询效率

总结

希望大家能在设计的时候多一些选择，尽可能的优化自己项目的速度。合理利用，合理取舍。

本人写的一个简单示例：https://gitee.com/su_xing_kang/administrative_division.git