问题
现在有一个要存储一下公司的人员结构,大致层次结构如下怎么存储这个结构?并且要获取以下信息:
1.查询小天的直接上司;
2.查询老宋管理下的直属员工;
3.查询小天的所有上司;
4.查询老王管理的所有员工。
方案一 Adjacency List(存储父节点)
Adjacency List(邻接表)是只存储当前节点的父节点ID。
数据库存储结构
-- ------------------------------ Table structure for employees-- ----------------------------DROPTABLEIFEXISTS`employees`;CREATETABLE`employees` ( `eid`int(11)NOTNULLCOMMENT'主键ID', `ename`varchar(100)CHARACTERSET utf8 COLLATE utf8_general_ci NULLDEFAULTNULLCOMMENT'姓名', `position`varchar(100)CHARACTERSET utf8 COLLATE utf8_general_ci NULLDEFAULTNULLCOMMENT'位置', `parent_id`int(11)NULLDEFAULTNULLCOMMENT'上级ID', PRIMARYKEY(`eid`)USINGBTREE)ENGINE=InnoDBCHARACTERSET= utf8 COLLATE= utf8_general_ci ROW_FORMAT = Dynamic;-- ------------------------------ Records of employees-- ----------------------------INSERTINTO`employees`VALUES(1,'老王','高管',0);INSERTINTO`employees`VALUES(2,'老宋','产品部主管',1);INSERTINTO`employees`VALUES(3,'老牛','技术部主管',1);INSERTINTO`employees`VALUES(4,'小吴','产品A组长',2);INSERTINTO`employees`VALUES(5,'小李','产品B组长',2);INSERTINTO`employees`VALUES(6,'小欢','产品经理',3);INSERTINTO`employees`VALUES(7,'小小','产品经理',3);INSERTINTO`employees`VALUES(8,'小天','产品部员工',4);INSERTINTO`employees`VALUES(9,'小里','产品部员工',4);INSERTINTO`employees`VALUES(10,'小黑','产品部员工',5);INSERTINTO`employees`VALUES(11,'小胡','产品部员工',5);INSERTINTO`employees`VALUES(12,'小丽','技术部员工',6);INSERTINTO`employees`VALUES(13,'小蓝','技术部员工',6);INSERTINTO`employees`VALUES(14,'小黄','技术部员工',7);INSERTINTO`employees`VALUES(15,'小真','技术部员工',7);123456789101112131415161718192021222324252627282930
如图所示:
SQL示例
1.添加节点
比如在小吴节点下,再次插入一个M节点
INSERT INTO employees ( eid, ename, position, parent_id ) VALUES ( 16, 'M', '产品部员工', 4 ); 12
2.查询小天的直接上司
SELECT e2.eid, e2.ename FROM employees e1, employees e2 WHERE e1.parent_id = e2.eid AND e1.ename = '小天'; 123456789
3.查询老宋管理下的直属员工
SELECT e1.eid, e1.ename FROM employees e1, employees e2 WHERE e1.parent_id = e2.eid AND e2.ename = '老宋'; 123456789
3.查询老宋管理下的直属员工
SELECT e1.eid, e1.ename FROM employees e1, employees e2 WHERE e1.parent_id = e2.eid AND e2.ename = '老宋'; 123456789
4.查询小天的所有上司
这里肯定没法直接查,只能用循环进行循环查询,先查直接上司,再查直接上司的直接上司,依次循环,这样麻烦的事情,得先建立一个函数:
-- 函数 CREATE DEFINER=`root`@`localhost` FUNCTION `getSuperiors`(`uid` int) RETURNS varchar(1000) CHARSET utf8mb4 BEGIN DECLARE superiors VARCHAR(1000) DEFAULT ''; DECLARE sTemp INTEGER DEFAULT uid; DECLARE tmpName VARCHAR(20); WHILE (sTemp>0) DO SELECT parent_id into sTemp FROM employees where eid = sTemp; SELECT ename into tmpName FROM employees where eid = sTemp; IF(sTemp>0)THEN SET superiors = concat(tmpName,',',superiors); END IF; END WHILE; SET superiors = LEFT(superiors,CHARACTER_LENGTH(superiors)-1); RETURN superiors; END; -- 查询子节点的全部父节点 select getSuperiors(11) as superior; 123456789101112131415161718192021
ps:显然获取子节点的全部父节点的时候很麻烦
5.查询老王管理的所有员工
先获取所有父节点为老王id的员工id,然后将员工姓名加入结果列表里,在调用一个神奇的查找函数,即可进行神奇的查找:
-- 函数 CREATE DEFINER=`root`@`localhost` FUNCTION `getSubordinate`(`uid` int) RETURNS varchar(2000) CHARSET utf8mb4 BEGIN DECLARE str varchar(1000); DECLARE cid varchar(100); DECLARE result VARCHAR(1000); DECLARE tmpName VARCHAR(100); SET str = '$'; SET cid = CAST(uid as char(10)); WHILE cid is not null DO SET str = concat(str, ',', cid); SELECT group_concat(eid) INTO cid FROM employees where FIND_IN_SET(parent_id,cid); END WHILE; SELECT GROUP_CONCAT(ename) INTO result FROM employees WHERE FIND_IN_SET(parent_id,str); RETURN result; END; -- 查询父节点下的所有子节点 SELECT getSubordinate(2); 12345678910111213141516171819
总结:
优点:存储的信息少,查直接上司和直接下属的时候很方便;
缺点:多级查询时较复杂,无论是SELECT还是DELETE都可能涉及到获取所有子节点的问题;
这种方法适合只需要用到直接上下级关系的时候,可以节省很多空间。
方案二 Path Enumeration(存储路径)
Path Enumeration 路径枚举法,存储根节点到每个子节点的路径
数据库存储结构
-- ---------------------------- -- Table structure for employees2 -- ---------------------------- DROP TABLE IF EXISTS `employees2`; CREATE TABLE `employees2` ( `eid` int(11) NOT NULL COMMENT '主键ID', `ename` varchar(100) CHARACTER SET utf8 COLLATE utf8_general_ci NULL DEFAULT NULL COMMENT '姓名', `position` varchar(100) CHARACTER SET utf8 COLLATE utf8_general_ci NULL DEFAULT NULL COMMENT '位置', `path` varchar(200) CHARACTER SET utf8 COLLATE utf8_general_ci NULL DEFAULT NULL COMMENT '所在路径', PRIMARY KEY (`eid`) USING BTREE ) ENGINE = InnoDB CHARACTER SET = utf8 COLLATE = utf8_general_ci ROW_FORMAT = Dynamic; -- ---------------------------- -- Records of employees2 -- ---------------------------- INSERT INTO `employees2` VALUES (1, '老王', '高管', '/1'); INSERT INTO `employees2` VALUES (2, '老宋', '产品部主管', '/1/2'); INSERT INTO `employees2` VALUES (3, '老牛', '技术部主管', '/1/3'); INSERT INTO `employees2` VALUES (4, '小吴', '产品A组长', '/1/2/4'); INSERT INTO `employees2` VALUES (5, '小李', '产品B组长', '/1/2/5'); INSERT INTO `employees2` VALUES (6, '小欢', '产品经理', '/1/3/6'); INSERT INTO `employees2` VALUES (7, '小小', '产品经理', '/1/3/7'); INSERT INTO `employees2` VALUES (8, '小天', '产品部员工', '/1/2/4/8'); INSERT INTO `employees2` VALUES (9, '小里', '产品部员工', '/1/2/4/9'); INSERT INTO `employees2` VALUES (10, '小黑', '产品部员工', '/1/2/5/10'); INSERT INTO `employees2` VALUES (11, '小胡', '产品部员工', '/1/2/5/11'); INSERT INTO `employees2` VALUES (12, '小丽', '技术部员工', '/1/3/6/12'); INSERT INTO `employees2` VALUES (13, '小蓝', '技术部员工', '/1/3/6/13'); INSERT INTO `employees2` VALUES (14, '小黄', '技术部员工', '/1/3/7/14'); INSERT INTO `employees2` VALUES (15, '小真', '技术部员工', '/1/3/7/15'); 12345678910111213141516171819202122232425262728293031
如图所示:
SQL示例
1.添加节点
要插入自己,然后查出父节点的Path,并且把自己生成的ID更新到path中去。比如,要在小吴节点后面插入M节点
-- 1.插入自己M,eid为16INSERTINTO employees2 ( eid, ename, position, path )VALUES(16,'M','产品部员工','');-- 2.查出小吴的path为/1/2/4SELECT path FROM employees2 WHERE eid=4-- 3.更新M的path为/1/2/4/16UPDATE employees2 SET path='/1/2/4/16'WHERE eid=16; 1234567
2.查询小天的直接上司
在上一个解决方案中能轻而易举做到的事情,在这个方案中却有些麻烦了,因为需要对path字段进行字符串处理,去掉“/”+自身id才是直接上司的path值。
SELECT e1.eid, e1.ename FROM employees2 e1, employees2 e2 WHERE e2.ename = '小天' AND e1.path = REPLACE ( e2.path, CONCAT( '/', e2.eid ), '' ); 123456789
3.查询老宋管理下的直属员工
怎么查管理下的直属员工呢?那就要用模糊查询了;使用正则匹配,匹配所有path符合规则的记录
SELECT e2.eid, e2.ename FROM employees2 e1, employees2 e2 WHERE e1.ename = '老宋' AND e2.path REGEXP CONCAT( e1.path, '/[0-9]{1,}$' ); 123456789
4.查询小天的所有上司
这里就能体现这种存储结构的优势了。不看效率的话,还是很方便的
SELECT e1.eid, e1.ename FROM employees2 e1, employees2 e2 WHERE e2.ename = '小天' AND e2.path LIKE concat( e1.path, '/%' ); 123456789
4.查询小天的所有上司
这里就能体现这种存储结构的优势了。不看效率的话,还是很方便的
SELECT e1.eid, e1.ename FROM employees2 e1, employees2 e2 WHERE e2.ename = '小天' AND e2.path LIKE concat( e1.path, '/%' ); 123456789
总结:
优点:多级查询十分方便;
缺点:插入节点稍微麻烦些;查询直接上下级的时候稍微复杂;path字段的长度是有限的,不能无限制的增加节点深度;
这种方法适用于存储小型的树结构。
方案三 Closure Table(存储关系表和深度)
Closure Table 终结表法,保存每个节点与其各个子节点的关系,也就是记录以其为根节点的全部子节点信息。
数据库存储结构
-- ---------------------------- -- Table structure for employees3 -- ---------------------------- DROP TABLE IF EXISTS `employees3`; CREATE TABLE `employees3` ( `eid` int(11) NOT NULL COMMENT '主键ID', `ename` varchar(100) CHARACTER SET utf8 COLLATE utf8_general_ci NULL DEFAULT NULL COMMENT '姓名', `position` varchar(100) CHARACTER SET utf8 COLLATE utf8_general_ci NULL DEFAULT NULL COMMENT '位置', PRIMARY KEY (`eid`) USING BTREE ) ENGINE = InnoDB CHARACTER SET = utf8 COLLATE = utf8_general_ci ROW_FORMAT = Dynamic; -- ---------------------------- -- Records of employees3 -- ---------------------------- INSERT INTO `employees3` VALUES (1, '老王', '高管'); INSERT INTO `employees3` VALUES (2, '老宋', '产品部主管'); INSERT INTO `employees3` VALUES (3, '老牛', '技术部主管'); INSERT INTO `employees3` VALUES (4, '小吴', '产品A组长'); INSERT INTO `employees3` VALUES (5, '小李', '产品B组长'); INSERT INTO `employees3` VALUES (6, '小欢', '产品经理'); INSERT INTO `employees3` VALUES (7, '小小', '产品经理'); INSERT INTO `employees3` VALUES (8, '小天', '产品部员工'); INSERT INTO `employees3` VALUES (9, '小里', '产品部员工'); INSERT INTO `employees3` VALUES (10, '小黑', '产品部员工'); INSERT INTO `employees3` VALUES (11, '小胡', '产品部员工'); INSERT INTO `employees3` VALUES (12, '小丽', '技术部员工'); INSERT INTO `employees3` VALUES (13, '小蓝', '技术部员工'); INSERT INTO `employees3` VALUES (14, '小黄', '技术部员工'); INSERT INTO `employees3` VALUES (15, '小真', '技术部员工'); -- ---------------------------- -- Table structure for emp_relations -- ---------------------------- DROP TABLE IF EXISTS `emp_relations`; CREATE TABLE `emp_relations` ( `root_id` int(11) NULL DEFAULT NULL COMMENT '根节点的eid', `depth` int(11) NULL DEFAULT NULL COMMENT '根节点到该节点的深度', `is_leaf` tinyint(1) NULL DEFAULT NULL COMMENT '该节点是否为叶子节点', `node_id` int(11) NULL DEFAULT NULL COMMENT '该节点的eid' ) ENGINE = InnoDB CHARACTER SET = utf8 COLLATE = utf8_general_ci ROW_FORMAT = Dynamic; -- ---------------------------- -- Records of emp_relations -- ---------------------------- INSERT INTO `emp_relations` VALUES (1, 0, 0, 1); INSERT INTO `emp_relations` VALUES (1, 1, 0, 2); INSERT INTO `emp_relations` VALUES (1, 1, 0, 3); INSERT INTO `emp_relations` VALUES (1, 2, 0, 4); INSERT INTO `emp_relations` VALUES (1, 2, 0, 5); INSERT INTO `emp_relations` VALUES (1, 2, 0, 6); INSERT INTO `emp_relations` VALUES (1, 2, 0, 7); INSERT INTO `emp_relations` VALUES (1, 3, 1, 8); INSERT INTO `emp_relations` VALUES (1, 3, 1, 9); INSERT INTO `emp_relations` VALUES (1, 3, 1, 10); INSERT INTO `emp_relations` VALUES (1, 3, 1, 11); INSERT INTO `emp_relations` VALUES (1, 3, 1, 12); INSERT INTO `emp_relations` VALUES (1, 3, 1, 13); INSERT INTO `emp_relations` VALUES (1, 3, 1, 14); INSERT INTO `emp_relations` VALUES (1, 3, 1, 15); INSERT INTO `emp_relations` VALUES (2, 0, 0, 2); INSERT INTO `emp_relations` VALUES (2, 1, 0, 4); INSERT INTO `emp_relations` VALUES (2, 1, 0, 5); INSERT INTO `emp_relations` VALUES (2, 2, 1, 8); INSERT INTO `emp_relations` VALUES (2, 2, 1, 9); INSERT INTO `emp_relations` VALUES (2, 2, 1, 0); INSERT INTO `emp_relations` VALUES (2, 2, 1, 11); INSERT INTO `emp_relations` VALUES (3, 0, 0, 3); INSERT INTO `emp_relations` VALUES (3, 1, 0, 6); INSERT INTO `emp_relations` VALUES (3, 1, 0, 7); INSERT INTO `emp_relations` VALUES (3, 2, 1, 12); INSERT INTO `emp_relations` VALUES (3, 2, 1, 13); INSERT INTO `emp_relations` VALUES (3, 2, 1, 14); INSERT INTO `emp_relations` VALUES (3, 2, 1, 15); INSERT INTO `emp_relations` VALUES (4, 0, 0, 4); INSERT INTO `emp_relations` VALUES (4, 1, 1, 8); INSERT INTO `emp_relations` VALUES (4, 1, 1, 9); INSERT INTO `emp_relations` VALUES (5, 0, 0, 5); INSERT INTO `emp_relations` VALUES (5, 1, 1, 10); INSERT INTO `emp_relations` VALUES (5, 1, 1, 11); INSERT INTO `emp_relations` VALUES (5, 1, 1, 12); 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980
表数据如下:
SQL示例
1.插入节点
比如,要在小吴节点后面插入M节点:
在插入M节点后,找出以小吴节点为后代的那些节点作为和M节点之间有后代关系,插入到数据表。
-- 1.插入自己M,eid为16INSERTINTO employees2 ( eid, ename, position )VALUES(16,'M','产品部员工');-- 2.查出以小吴为后代的节点数据SELECT*FROM emp_relations WHERE node_id=4-- 3.插入到数据表:深度+1作为和M节点的深度
INSERT INTO emp_relations ( root_id, depth, is_leaf, node_id ) VALUES ( 1, 3, 0, 16 ), ( 2, 2, 0, 16 ), ( 4, 1, 0, 16 ), ( 16, 0, 1, 16 ); 123456789101112
2.查询小天的直接上司
在关系表中找到node_id为小天id,depth为1的根节点id即可
SELECT e2.ename BOSS FROM employees3 e1, employees3 e2, emp_relations rel WHERE e1.ename = '小天' AND rel.node_id = e1.eid AND rel.depth = 1 AND e2.eid = rel.root_id 1234567891011
3.查询老宋管理下的直属员工
只要查询root_id为老宋eid且深度为1的node_id即为其直接下属员工id
SELECT e1.eid, e1.ename 直接下属 FROM employees3 e1, employees3 e2,
emp_relations rel WHERE e2.ename = '老宋' AND rel.root_id = e2.eid AND rel.depth = 1 AND e1.eid = rel.node_id 123456789101112
4.查询小天的所有上司。
只要在关系表中找到node_id为小天eid且depth大于0的root_id即可
SELECT e2.eid, e2.ename 上司 FROM employees3 e1, employees3 e2, emp_relations rel WHERE e1.ename ='小天' AND rel.node_id = e1.eid AND rel.depth >0 AND e2.eid = rel.root_id 123456789101112
5.查询老王管理的所有员工
SELECT e1.eid, e1.ename 下属 FROM employees3 e1, employees3 e2, emp_relations rel WHERE e2.ename ='老王' AND rel.root_id = e2.eid AND rel.depth >0 AND e1.eid = rel.node_id 123456789101112
总结:
优点:四个查询的复杂程度是一样的,而且可以让另一张表只存储跟节点紧密相关的信息,看起来更简洁;
缺点:关系表会很庞大,当层次很深,结构很庞大的时候,关系表数据的增长会越来越快,相当于用空间效率来换取了查找上的时间效率
对比
树形结构在数据库中存储的三种方式就介绍完了,接下来对比一下三种方法:
- 方案一:Adjacency List
优点:只存储上级id,存储数据少,结构类似于单链表,在查询相邻节点的时候很方便,添加删除节点都比较简单。
缺点:查询多级结构的时候会显得力不从心(无论是SELECT还是DELETE都可能涉及到获取所有子节点的问题)。
适用场合:对多级查询需求不大的场景比较适用。 - 方案二:Path Enumeration
优点:查询多级结构的时候比较方便。查询相邻节点时也比较ok。增加或者删除节点的时候比较简单。
缺点:需要存储的path值可能会很大,甚至超过设置的最大值范围,理论上无法无限扩张。
适用场合:结构相对简单的场景比较适合。 - 方案三:Closure Table
优点:在查询树形结构的任意关系时都很方便。
缺点:需要存储的数据量比较多,索引表需要的空间比较大,增加和删除节点相对麻烦。
适用场合:纵向结构不是很深,增删操作不频繁的场景比较适用。