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

发表于 阅读次数：

树形结构很常见，例如组织结构图、线性化讨论等。树形结构中，实例被称为节点（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].人民邮电出版社.