树在 MySQL 中的存储方式

参考《大话数据结构》，如下定义树：

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

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

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

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

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

领接表

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

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='菜单表'

闭包表

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='菜单闭包表'

// 未完，待续……