数据库树形结构设计

知识库实战项目商城项目商城项目大约 3 分钟

理想中树形结构应该具备如下特征:

  1. 数据存储冗余度⼩、直观性强;
  2. 检索遍历过程简单⾼效;
  3. 节点增删改查 CRUD 操作⾼效

继承关系驱动的 Schema 设计

结构通常设计为:

优点:设计和实现⾃然⽽然,⾮常直观和⽅便。
缺点:频繁递归对 Tree 得 CURD 操作,IO 开销大,性能低。在 Tree 规模相对较⼩的情况下,可以借助于缓存机制来做优化。

基于左右值编码的 Schema 设计

设计:左节点永远小于右节点的值。
优点:消除递归操作,查询条件是基于整形数字的⽐较,效率很⾼。
缺点:节点的添加、删除及修改代价较⼤,将会涉及到表中多⽅⾯数据的改动。

创建表和插入数据

-- 创建表
CREATE TABLE `tree` (
	`node_id` int(11) NOT NULL AUTO_INCREMENT,
	`name` varchar(45) DEFAULT NULL,
	`lft` int(11) DEFAULT NULL,
	`rgt` int(11) DEFAULT NULL,
	PRIMARY KEY (`node_id`)
) ENGINE = InnoDB CHARSET = utf8;

-- 插⼊数据
INSERT INTO `tree` VALUES (1, 'Food', 1, 18), (2, 'Fruit', 2, 11), (3, 'Red', 3, 6), (4, 'Cherry', 4, 5), (5, 'Yellow', 7, 10), (6, 'Banana', 8, 9), (7, 'Meat', 12, 17), (8, 'Beef', 13, 14), (9, 'Pork', 15, 16);

-- 获取某节点的⼦节点
SELECT * FROM tree WHERE lft BETWEEN 2 AND 11 ORDER BY lft ASC;
-- 获取某节点的⼦孙节点总数= (右值 – 左值– 1) / 2
select (112 - 1) / 2 from dual;

节点在树中所处的层次

-- 节点在树中所处的层次
SELECT COUNT(*) FROM tree WHERE lft <= 2 AND rgt >= 11;
-- ⾃定义函数来计算
CREATE FUNCTION `CountLayer`(p_node_id int)
RETURNS int(11) DETERMINISTIC
BEGIN declare p_result,p_lft,p_rgt int default 0;
if exists ( select 1 from tree where node_id=p_node_id ) then begin
    SELECT lft, rgt INTO (p_lft, p_rgt) FROM tree WHERE node_id = p_node_id;
    SELECT count(*) INTO p_result FROM tree WHERE lft <= p_lft AND rgt >= p_rgt;
    end;
    return p_result;
end if;
    RETURN 0;
END
-- 执行函数查询
select CountLayer(2);

获取节点的子孙节点

-- 基于层次计算函数,我们创建⼀个视图,添加了新的记录节点层次的数列
CREATE VIEW tree_view AS SELECT node_id, name, lft, rgt , CountLayer(Node_id) AS layer FROM tree ORDER BY Lft
-- 创建存储过程,⽤于计算给定节点的所有⼦孙节点及相应的层次
CREATE PROCEDURE `GetChildrenNodeList`(p_node_id int)
BEGIN declare p_lft,p_rgt int default 0;
if exists(select node_id from tree where node_id = p_node_id) then begin
    SELECT lft, rgt INTO (p_lft, p_rgt) FROM tree WHERE node_id = p_node_id;
    SELECT * FROM tree_view WHERE lft BETWEEN p_lft AND p_rgt ORDER BY lft ASC;
    end;
end if;
END
-- 执行存储过程
call GetChildrenNodeList(2);

获取某节点的⽗节点

-- 获取某节点的⽗节点
SELECT * FROM tree WHERE lft < 2 AND rgt > 11 ORDER BY lft ASC
-- 存储过程
CREATE PROCEDURE `GetParentNodePath`(p_node_id int)
BEGIN declare p_lft,p_rgt int default 0;
if exists(select node_id from tree where node_id = p_node_id) then begin
    SELECT lft, rgt INTO (p_lft, p_rgt) FROM tree WHERE node_id = p_node_id;
    SELECT * FROM tree_view WHERE lft < p_lft AND rgt > p_rgt ORDER BY lft ASC;
    end;
end if;
END
-- 执行存储过程
call GetParentNodePath(2);

添加⼦节点

-- 添加⼦节点
CREATE PROCEDURE `AddSubNode` ( p_node_id int, p_node_name varchar(50) )
BEGIN declare p_rgt int default 0;
if exists(select node_id from tree where node_id = p_node_id) then begin START TRANSACTION;
    SELECT rgt INTO p_rgt FROM tree WHERE node_id = p_node_id;
    UPDATE tree SET rgt = rgt + 2 WHERE rgt >= p_rgt;
    UPDATE tree SET lft = lft + 2 WHERE lft >= p_rgt;
    INSERT INTO tree (name, lft, rgt) VALUES (p_node_name, p_rgt, p_rgt + 1);
    COMMIT;
    end;
end if;
END
-- 执行添加⼦节点
call AddSubNode(3,'Apple');

删除某节点

-- 删除某节点
CREATE PROCEDURE `DelNode`(p_node_id int)
BEGIN declare p_lft,p_rgt int default 0;
if exists(select node_id from tree where node_id = p_node_id) then START TRANSACTION;
    DELETE FROM tree WHERE lft >= p_lft AND rgt <= p_rgt;
    UPDATE tree SET lft = lft - (p_rgt - p_lft + 1) WHERE lft > p_lft;
    UPDATE tree SET rgt = rgt - (p_rgt - p_lft + 1) WHERE rgt > p_rgt;
    COMMIT;
end if;
END
-- 执行删除节点
call DelNode(8);