树在 MySQL 中的存储方式

参考《大话数据结构》,如下定义树:

树(Tree)是n(n>=0)个结点的有限集。n=0时称为空树。在任意一颗非空树中:
有且仅有一个特定的称为根(root)的结点;
当n>1时,其余结点可分为m(m>0)个互补交互的有限集T1、T2…Tm,其中每一个集合本身又是一棵树,并称为根的子树(SubTree)。

在工作中,树被广泛使用,最常见的就是数据库中的 B+ 树,除此之外,网站中的菜单也常常是用树来表达其中的层次关系的(hierarchical),本文重点讲解基于菜单树这种应用常见下树在数据库中的存储方式。

参考《SQL 反模式》,树在数据库中常见的存储方式有:

  • 领接表
  • 路径枚举
  • 嵌套集
  • 闭包表

最简单最常见的是领接表,最高效的是闭包表,所以本文将重点讨论领接表和闭包表。

领接表

这种存储方式很简单,就是给每一条记录添加一个指向父亲节点的指针,即 parent_id。

1
2
3
4
5
6
CREATE TABLE `menus` (
`id` bigint(20) unsigned NOT NULL AUTO_INCREMENT COMMENT '自增id',
`menu_name` varchar(64) NOT NULL DEFAULT '' COMMENT '语义化的菜单名称',
`parent_id` int(10) NOT NULL DEFAULT '1' COMMENT '菜单父节点id',
PRIMARY KEY (`id`)
) ENGINE=InnoDB AUTO_INCREMENT=7 DEFAULT CHARSET=utf8 COMMENT='菜单表'

闭包表

1
2
3
4
5
6
CREATE TABLE `menu_tree` (
`ancestor` bigint(20) unsigned NOT NULL COMMENT '祖先节点',
`descendant` bigint(20) unsigned NOT NULL COMMENT '子代节点',
`distance` int(11) unsigned NOT NULL COMMENT '子孙到祖先中间相差的层级数目',
PRIMARY KEY `uniq_ancestor_descendant` (`ancestor`,`descendant`,`distance`)
) ENGINE=InnoDB AUTO_INCREMENT=10 DEFAULT CHARSET=utf8 COMMENT='菜单闭包表'

// 未完,待续……

本文标题:树在 MySQL 中的存储方式

文章作者:Syncher

发布时间:2019年01月19日 - 16:01

最后更新:2019年03月08日 - 09:03

原始链接:https://0x400.com/2019-01-19-mysql-store-tree-using-closure-table.html

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。