本文主要研究一下mysql的树形结构存储及查询
这种方式就是每个节点存储自己的parent_id信息 • 建表及数据准备
CREATE TABLE `menu` (
`id` int(11) NOT NULL AUTO_INCREMENT,
`name` varchar(50) NOT NULL,
`parent_id` int(11) NOT NULL DEFAULT '0',
PRIMARY KEY (`id`)
) ENGINE=InnoDB;
INSERT INTO menu
(id
, name
, parent_id
) VALUES (1, 'level1a', 0), (2, 'level1b', 0), (3, 'level2a-1a',1), (4, 'level2b-1a',1), (5, 'level2a-1b', 2), (6, 'level2b-1b', 2), (7, 'level3-2a1a', 3), (8, 'level3-2b1a', 4), (9, 'level3-2a1b', 5), (10, 'level3-2b1b', 6);
- 查询
-- 查询跟节点下的所有节点 SELECT t1.name AS lev1, t2.name as lev2, t3.name as lev3 FROM menu AS t1 LEFT JOIN menu AS t2 ON t2.parent_id = t1.id LEFT JOIN menu AS t3 ON t3.parent_id = t2.id WHERE t1.name = 'level1a';
+---------+------------+-------------+ | lev1 | lev2 | lev3 | +---------+------------+-------------+ | level1a | level2a-1a | level3-2a1a | | level1a | level2b-1a | level3-2b1a | +---------+------------+-------------+
-- 查询叶子节点 SELECT t1.name FROM menu AS t1 LEFT JOIN menu as t2 ON t1.id = t2.parent_id WHERE t2.id IS NULL;
+-------------+ | name | +-------------+ | level3-2a1a | | level3-2b1a | | level3-2a1b | | level3-2b1b | +-------------+
>存储及修改上比较方便,就是要在sql里头查询树比较费劲,一般是加载到内存由应用自己构造
# 存储path
>这种方式在存储parent的基础上,额外存储path,即从根节点到该节点的路径
- 建表及数据准备
CREATE TABLE menu_path
( id
int(11) NOT NULL AUTO_INCREMENT, name
varchar(50) NOT NULL, parent_id
int(11) NOT NULL DEFAULT '0', path
varchar(255) NOT NULL DEFAULT '', PRIMARY KEY (id
) ) ENGINE=InnoDB;
INSERT INTO menu_path
(id
, name
, parent_id
, path
) VALUES (1, 'level1a', 0, '1/'), (2, 'level1b', 0, '2/'), (3, 'level2a-1a',1, '1/3'), (4, 'level2b-1a',1, '1/4'), (5, 'level2a-1b', 2, '2/5'), (6, 'level2b-1b', 2, '2/6'), (7, 'level3-2a1a', 3, '1/3/7'), (8, 'level3-2b1a', 4, '1/4/8'), (9, 'level3-2a1b', 5, '2/5/9'), (10, 'level3-2b1b', 6, '2/6/10');
- 查询
-- 查询某个节点的所有子节点 select * from menu_path where path like '1/%' +----+-------------+-----------+-------+ | id | name | parent_id | path | +----+-------------+-----------+-------+ | 1 | level1a | 0 | 1/ | | 3 | level2a-1a | 1 | 1/3 | | 4 | level2b-1a | 1 | 1/4 | | 7 | level3-2a1a | 3 | 1/3/7 | | 8 | level3-2b1a | 4 | 1/4/8 | +----+-------------+-----------+-------+
>查找某个节点及其子节点比较方面,就是修改比较费劲,特别是节点移动,所有子节点的path都得跟着修改
# MPTT(Modified Preorder Tree Traversal)
![](https://i2.sitepoint.com/graphics/sitepoint_numbering.gif)
>不存储parent_id,改为存储lft,rgt,它们的值由树的先序遍历顺序决定
- 建表及数据准备
CREATE TABLE menu_preorder
( id
int(11) NOT NULL, name
varchar(50) NOT NULL, lft
int(11) NOT NULL DEFAULT '0', rgt
int(11) NOT NULL DEFAULT '0', PRIMARY KEY (id
) ) ENGINE=InnoDB;
1(level1a)14
2(level2a)7 8(level2b)13
3(level3a-2a)4 5(level3b-2a)6 9(level3c-2b)10 11(level3d-2b)12
INSERT INTO menu_preorder
(id
, name
, lft
, rgt
) VALUES (1, 'level1a', 1, 14), (2, 'level2a',2, 7), (3, 'level2b',8, 13), (4, 'level3a-2a', 3, 4), (5, 'level3b-2a', 5, 6), (6, 'level3c-2b', 9, 10), (7, 'level3d-2b', 11, 12);
select * from menu_preorder +----+------------+-----+-----+ | id | name | lft | rgt | +----+------------+-----+-----+ | 1 | level1a | 1 | 14 | | 2 | level2a | 2 | 7 | | 3 | level2b | 8 | 13 | | 4 | level3a-2a | 3 | 4 | | 5 | level3b-2a | 5 | 6 | | 6 | level3c-2b | 9 | 10 | | 7 | level3d-2b | 11 | 12 | +----+------------+-----+-----+
- 查询
-- 查询某个节点及其子节点,比如level2b select * from menu_preorder where lft between 8 and 13 +----+------------+-----+-----+ | id | name | lft | rgt | +----+------------+-----+-----+ | 3 | level2b | 8 | 13 | | 6 | level3c-2b | 9 | 10 | | 7 | level3d-2b | 11 | 12 | +----+------------+-----+-----+
-- 查询所有叶子节点 SELECT name FROM menu_preorder WHERE rgt = lft + 1;
+------------+ | name | +------------+ | level3a-2a | | level3b-2a | | level3c-2b | | level3d-2b | +------------+
-- 查询某个节点及其父节点 SELECT parent.* FROM menu_preorder AS node, menu_preorder AS parent WHERE node.lft BETWEEN parent.lft AND parent.rgt AND node.name = 'level2b' ORDER BY parent.lft;
+----+---------+-----+-----+ | id | name | lft | rgt | +----+---------+-----+-----+ | 1 | level1a | 1 | 14 | | 3 | level2b | 8 | 13 | +----+---------+-----+-----+
-- 树形结构展示 SELECT CONCAT( REPEAT(' ', COUNT(parent.name) - 1), node.name) AS name FROM menu_preorder AS node, menu_preorder AS parent WHERE node.lft BETWEEN parent.lft AND parent.rgt GROUP BY node.name ORDER BY node.lft;
+--------------+ | name | +--------------+ | level1a | | level2a | | level3a-2a | | level3b-2a | | level2b | | level3c-2b | | level3d-2b | +--------------+ ```
好处是通过lft进行范围(该节点的lft,rgt作为范围)查找就可以,缺点就是增删节点导致很多节点的lft及rgt都要修改
• 存储parent的方式最为场景,一般树形结构数据量不大的话,直接在应用层内存构造树形结构和搜索 • 存储path的好处是可以借助path来查找节点及其子节点,缺点就是移动node需要级联所有子节点的path,比较费劲 • MPTT的方式好处是通过lft进行范围(该节点的lft,rgt作为范围)查找就可以,缺点就是增删节点导致很多节点的lft及rgt都要修改
• Managing Hierarchical Data in MySQL[1] • hierarchical-data-database[2] • hierarchical-data-database-2[3] • hierarchical-data-database-3[4]
[1] Managing Hierarchical Data in MySQL http://download.nust.na/pub6/mysql/tech-resources/articles/hierarchical-data.html
[2] hierarchical-data-database https://www.sitepoint.com/hierarchical-data-database/
[3] hierarchical-data-database-2 https://www.sitepoint.com/hierarchical-data-database-2/
[4] hierarchical-data-database-3 https://www.sitepoint.com/hierarchical-data-database-3/