关系数据库中存储树结构及前端还原的方法

树形结构很常见,例如组织结构图、线性化讨论等。树形结构中,实例被称为节点(node),每个节点有多个子节点和一个父节点。最上层的节点叫根(root)节点,它没有父节点。最底层的节点叫叶(leaf)节点,它没有子节点。本文主要介绍如何在关系数据库中存储树结构,以及如何从关系数据库中恢复树结构。

关系数据库中存储树结构的方法

层级数据设计方案

在关系数据库中存储树结构主要有以下几种方案:

  • 邻接表模型

最常见的解决方案,在数据库表中添加parent_id字段,再引用同一张表中的其他记录的id。可通过一个外键约束维护这种关系。

优点:增加叶节点、修改节点或子树位置很方便。

缺点:查询节点的所有后代、删除子树很困难。

  • 路径枚举

路径枚举是一个由连续的直接层级关系组成的完整路径。例如/usr/local/lib。

优点:查询节点所有后代、插入新节点很方便。
缺点:依赖应用程序逻辑代码维护路径字符串,验证字符串正确性开销大。受限于字符串长度,树结构无法无限扩展。

  • 嵌套集

嵌套集解决方案是存储子孙节点的相关信息,而不是节点的直接祖先。通常使用两个数字nsleft和nsright编码每个节点,以表示子孙节点信息。

nsleft的数值小于该节点所有后代的ID,同时nsright的值大于该节点所有后代的ID。

确定这三个值(nsleft,ID,nsright)的简单方法是对树进行一次深度优先遍历,在逐层深入过程中依次递增地分配nsleft的值,并在返回时依次递增地分配nsright的值。

优点:查询给定节点祖先和后代很容易,删除非叶子节点,其后代会自动代替被删除节点成为其祖先节点的直接后代。

缺点:不易理解,插入和移动节点复杂。

  • 闭包表

闭包表通过额外的数据库表记录树中节点间父子的关系,包括直接的父子关系、间接的父子关系和指向自己的关系。

层级数据设计比较

层级数据设计比较
设计 查询子 查询树 插入 删除 引用完整性
邻接表 1 简单 困难 简单 简单
邻接表+递归查询 1 简单 简单 简单 简单
路径枚举 1 简单 简单 简单 简单
嵌套集 1 困难 简单 困难 困难
闭包集 2 简单 简单 简单 简单
  • 邻接表设计最简单,如果使用的数据库支持WITH或CONNECT BY PRIOR的递归查询,将使得邻接表查询更为高效。

前端从关系数据库中还原树结构

表结构,使用sequelize的对象表示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
'use strict';
module.exports = (sequelize, DataTypes) => {
const Role = sequelize.define('Role', {
id: {
type: DataTypes.STRING(50),
primaryKey: true
},
roleName: {
type: DataTypes.STRING(128),
allowNull: false
},
path: {
type: DataTypes.STRING(512),
allowNull: false,
unique: true,
comment: '角色路径唯一!'
},
deleteFlag:{
type: DataTypes.BOOLEAN,
defaultValue: false
}
}, {});
Role.associate = function(models) {
// associations can be defined here
Role.hasMany(models.User)
};
return Role;
};

递归生成角色树:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// 获取第一层节点
function getFirstLevel(recordList){
var firstLevelList=[];
for(let i=0;i< recordList.length;i++){
let record=recordList[i]
if (record.path.length === 2 && record.path.split('')[1] === '/' && parseInt(record.path.split('')[0])>=0){
record.label=record.roleName
firstLevelList.push(record)
}
}
return firstLevelList
}

// 指定根节点,递归生成角色树
function recursiveTree(parentRecord,recordList){
for (let i = 0; i < recordList.length; i++){
let record = recordList[i]
if(parentRecord.path==record.path.slice(0,-2)){
record=recursiveTree(record,recordList)
if (parentRecord.children==undefined){
parentRecord.children=[]
}
parentRecord.children.push(record)
}
}
parentRecord.label = parentRecord.roleName
return parentRecord
}

// 生成角色树
export function parseRoleTree(recordList){
var result = getFirstLevel(recordList);

for (let i=0;i<result.length;i++){
parent = result[i]
parent = recursiveTree(parent, recordList)
}

return result;
}

参考链接

  1. java递归生成树形结构菜单,by 伊宇紫.
  2. Bill Karwin著,谭振林,Push Chen译. SQL反模式[M].人民邮电出版社.