树形数据结构是咱们常见的一种数据结构，比方文件目录、公司组织构造等。然而关系型数据库却没有对应的原生数据结构去存储查问这种数据结构，本文介绍了几种实现关系型数据库树形数据存储的形式供大家参考。

前言

树形构造是生存中常见的数据结构之一，如公司的组织构造、计算机文件的目录构造和家庭族谱等。本文将以区域作为示例，介绍几种常见的数据库实现树形查问的形式：

树形构造的要害属性：深度

计划一、毗连目录模式(adjacency list model)

计划原理

毗连目录模式在树形构造数据的每条记录中，记录了指向父数据的记录，如下图所示：

数据库中的表构造如下所示：

查问状况 1：当咱们须要查问上海的间接父区域时，通过以下 Sql 查问：

select parent from 区域表 where name = '上海' 

查问状况 2：当咱们须要查问上海的间接子区域时，通过以下 Sql 查问：

select name from 区域表 where parent = '上海' 

查问状况 3：当咱们须要查问上海的二级子区域时：

select name from 区域表 where parent in（select name from 区域表 where parent = '上海'）

查问状况 4：当咱们须要查问上海的所有子区域，并且不晓得区域树的总层数（伪代码）：

result_set = select name from 区域表 where parent = '上海';
current_parent = select name from 区域表 where parent = '上海';
while current_parent is not null:
    current_parent = select name from 区域表 where parent in current_parent
    result_set.add_all(current_parent)

能够看到：此种查问状况下，随着树的高度减少，IO 次数也会减少。

计划优缺点

查问所有子树难度：高
查问所有父节点难度：高
查问下一层子节点难度：低
查问上一层父节点难度：低
插入新记录的难度：低
删除原有记录的难度：低
占用额定空间少，只须要占用额定一列 O(n)的空间；

实用场景：

1. 只蕴含间接父子查问的场景
2. 蕴含多层查问，然而能够加载所有数据到内存中的场景

计划二、预排序遍历树算法(modified preorder tree traversal algorithm)

计划原理

预排序的意思就是咱们在查问前对存到数据库中的数据进行一次非凡的排序，给每条数据增加两个字段：左索引和右索引，增加的形式如下图所示

数据库中的表构造如下所示：

查问状况 1 ：查找上海有多少子区域（不蕴含本身）：

select rindex-lindex as region_num from 区域表 where name = '上海';

解释：编号时，能够发现从上海的左侧开始编号递增，回到右侧时候给所有的子节点左右都编号了一次，所以上海节点的右索引减去左索引除以 2(每个子节点有左右两个编号)，就是子节点的总数目。
查问状况 2：查问上海的所有子区域：

查问状况 2 ：查问上海的所有子区域：

select name from 区域表 where lindex > 16 and rindex < 25;

解释：由编号过程能够发现，上海子区域的编号值必定在（19，24）范畴内，而非上海子区域的编号范畴必定不在（19，24）范畴内，所以此处 where 中的 lindex 和 rindex 能够调换，例如以下语句也能够查问出上海的子区域

select name from 区域表 where lindex > 16 and lindex < 25;

select name from 区域表 where rindex > 16 and rindex < 25;

select name from 区域表 where rindex > 16 and lindex < 25;

查问状况 3 ：查问浦东区域的父区域（上海的父区域只有一个，不直观）：

select name from 区域表 where rindex < 19 and lindex > 24;

解释：由下面的编号过程可知，只有一个节点的左右编号范畴在另外一个节点的左右编号范畴内（查问 2 的逆推），同理，这个查问语句中的左右 19 和 24 一样能够调换，例如：

select name from 区域表 where rindex < 19 and lindex > 19;

select name from 区域表 where rindex < 24 and lindex > 24;

select name from 区域表 where rindex < 24 and lindex > 19;

批改状况 1 ：删除浦东区域
当树形构造变更时，须要从新触发预排序，如删除浦东之后，左右索引值在 19 到 24 的值须要减 1，左右索引大于 24 的须要减 2.

update 区域表 set rindex = rindex-1 where rindex < 24 and rindex > 19;
update 区域表 set lindex = lindex-1 where lindex < 24 and lindex > 19;
update 区域表 set rindex = rindex-2 where rindex > 24;
update 区域表 set lindex = lindex-2 where lindex > 24;

批改状况 2 ：把删除的浦东区域增加回来：

update 区域表 set rindex = rindex+1 where rindex < 24 and rindex >= 19;
update 区域表 set lindex = lindex+1 where lindex < 24 and lindex >= 19;
update 区域表 set rindex = rindex+2 where rindex >= 24;
update 区域表 set lindex = lindex+2 where lindex >= 24;

计划优缺点

查问所有子树难度：低
查问所有父节点难度：低
查问下一层子节点难度：高
查问上一层父节点难度：高
插入新记录的难度：高
删除原有记录的难度：高
占用额定空间少，只须要占用额定一列 O(n)的空间；

实用场景：

1. 数据简直不更新的场景。

计划三、门路枚举法（Path Enumerations）

计划原理

该办法在每一条数据记录后边增加了一列，用于存储根节点到该点的残缺门路。

查问状况 1 ：查找上海有多少子区域（不蕴含本身）：

select name from 区域表 where path like '中国 / 上海 /%';

查问状况 2 ：查问上海区域的所有父区域：

select name from 区域表 where path like '%/ 上海';

删除 / 变更 / 减少状况 ：删除 / 变更 / 减少上海区域：
须要更新所有子节点的门路字符串。

计划优缺点

查问所有子树难度：低
查问所有父节点难度：低
查问下一层子节点难度：低
查问上一层父节点难度：低
插入新记录的难度：高
删除原有记录的难度：高
占用额定空间中等，只须要占用额定一列 O(n)*O(m)的空间（n 为节点总数目。m 为树的深度）；

计划四、ClosureTable

计划原理

之前的计划中，都是对原有的记录增加列，而后对新增的列进行查问获取父子节点信息关系。而 ClosureTable 则是新增一张表，用于记录节点间接的关系（父节点，子节点，深度），如下图中的孙桥和浦东，会生成以下关系记录；

查问状况 1 ：查问上海的下一层子区域：

select child from 区域表 where parent = '上海' and deepth = 1;

查问状况 2 ：查问上海的所有子区域：

select child from 区域表 where parent = '上海';

查问状况 3 ：查问上海的上一层父区域：

select parent from 区域表 where child = '上海' and deepth = 1;

查问状况 4 ：查问上海的所有父区域：

select parent from 区域表 where child = '上海';

删除状况 ：删除上海区域：
更新上海的子节点的深度：

parents = select parent from 区域表 where child = '上海';
children = select child from 区域表 where parent = '上海';
update 区域表 set depth = depth -1 where parent in parents and child in children.
delete parent from 区域表 where child = '上海' or parent = '上海';

计划优缺点

查问所有子树难度：低
查问所有父节点难度：低
查问下一层子节点难度：低
查问上一层父节点难度：低
插入新记录的难度：高
删除原有记录的难度：高
占用额定空间高，须要额定一张表存 O(n)*O(m)条记录（n 为节点总数目。m 为树的深度）；

我是御狐神，欢送大家关注我的微信公众号

本文最先公布至微信公众号，版权所有，禁止转载！