树形结构很常见,例如组织结构图、线性化讨论等。树形结构中,实例被称为节点(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 | 'use strict'; |
递归生成角色树:
1 | // 获取第一层节点 |
参考链接
- java递归生成树形结构菜单,by 伊宇紫.
- Bill Karwin著,谭振林,Push Chen译. SQL反模式[M].人民邮电出版社.