無法定位序數(shù)459(無法定位序數(shù)459于動態(tài)鏈接庫)

原文鏈接：https://mp.weixin.qq.com/s/fSE8qQBAGf1jQTp-a5i-8w

不管你是做前端還是后端的開發(fā)，那我相信樹形結(jié)構(gòu)的需求一定有遇到過，特別是管理平臺類型的項目，一般都會有一個樹形結(jié)構(gòu)的菜單欄，再比如說，公司組織架構(gòu)，層級關(guān)系、歸屬關(guān)系等等需求，本質(zhì)上都是樹形結(jié)構(gòu)的一種體現(xiàn)；

遇到這種需求，最常見也最容易想到的設(shè)計思路就是：父子關(guān)系的方式，子項通過一個字段來保存他的父ID，然后通過遞歸的方式得到層級關(guān)系；

前幾天，技術(shù)交流群里面有小伙伴在問，實(shí)際的業(yè)務(wù)中，樹形結(jié)構(gòu)的數(shù)據(jù)太多、層級還深，查詢過程一頓遞歸之后，性能表現(xiàn)得比較差，問有沒有什么好的設(shè)計思路，讓查詢、統(tǒng)計更加的便捷高效；

今天就給大家介紹一種新的樹形結(jié)構(gòu)設(shè)計方案：改進(jìn)后的先序樹方式，在查詢、統(tǒng)計方面的優(yōu)勢，要遠(yuǎn)大于父子關(guān)系的遞歸設(shè)計方案；

本文就來詳細(xì)的講解并對比一下兩個方案的實(shí)現(xiàn)方式以及優(yōu)缺點(diǎn)。

文章目錄：

對于樹形結(jié)構(gòu)的需求，不管是采用什么方式，要處理的問題都是差不多的，下面先列舉一下樹形結(jié)構(gòu)常見的問題點(diǎn)有哪些：

節(jié)點(diǎn)的增刪改是否存在子節(jié)點(diǎn)（葉子節(jié)點(diǎn)）查詢出所有的子節(jié)點(diǎn)查詢所有的節(jié)點(diǎn)查詢所有的子孫節(jié)點(diǎn)父節(jié)點(diǎn)查詢祖先節(jié)點(diǎn)查詢統(tǒng)計所有子孫部門的數(shù)量

針對上面的這些問題，就以一個簡單的公司組織架構(gòu)示例，一起來看看，兩種方案都是如何實(shí)現(xiàn)和解決的？

本文所有的示例都是采用的MySQL+Java實(shí)現(xiàn)，核心思路都類似，實(shí)際使用，可根據(jù)語言特性以及自己習(xí)慣的方式調(diào)整即可。

1父子關(guān)系方案

父子關(guān)系，顧名思義，就是當(dāng)前節(jié)點(diǎn)只關(guān)注自己的父節(jié)點(diǎn)是誰，并將其保存起來即可，查詢我的子節(jié)點(diǎn)有哪些，只需要全局找到所有父ID是和我的ID一致的項；

如下圖所示：

方案特點(diǎn)優(yōu)點(diǎn)方案簡單易懂?dāng)?shù)據(jù)結(jié)構(gòu)簡單清晰層級直觀、鮮明易維護(hù)層級關(guān)系只需要關(guān)注自己的父ID，所以在添加、修改的時候，一旦關(guān)系發(fā)生變化，調(diào)整對應(yīng)的父ID即可。缺點(diǎn)查找麻煩、統(tǒng)計麻煩根據(jù)當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)，只能獲取到子節(jié)點(diǎn)的數(shù)據(jù)，一旦查詢、統(tǒng)計超出父子范圍，就只能通過遞歸逐層查找了；示例

根據(jù)上面的圖示示例，與其對應(yīng)的表結(jié)構(gòu)如下：

IDdep_name(部門名稱)level(層級)parent_id(父ID)1董事會102總經(jīng)理213董事會秘書214產(chǎn)品部325行政總監(jiān)326設(shè)計部447技術(shù)部448財務(wù)部459行政部4510客戶端5711服務(wù)端57

SQL腳本：

DROP TABLE IF EXISTS `department_info`;CREATE TABLE `department_info` ( `id` int(11) NOT NULL, `dep_name` varchar(255) CHARACTER SET utf8mb4 COLLATE utf8mb4_general_ci NULL DEFAULT NULL COMMENT '名稱', `level` int(11) NULL DEFAULT NULL, `parent_id` int(11) NULL DEFAULT NULL COMMENT '父ID', PRIMARY KEY (`id`) USING BTREE) ENGINE = InnoDB CHARACTER SET = utf8mb4 COLLATE = utf8mb4_general_ci ROW_FORMAT = Dynamic;INSERT INTO `department_info` VALUES (1, '董事會', 1, 0);INSERT INTO `department_info` VALUES (2, '總經(jīng)理', 2, 1);INSERT INTO `department_info` VALUES (3, '董事會秘書', 2, 1);INSERT INTO `department_info` VALUES (4, '產(chǎn)品部', 3, 2);INSERT INTO `department_info` VALUES (5, '行政總監(jiān)', 3, 2);INSERT INTO `department_info` VALUES (6, '設(shè)計部', 4, 4);INSERT INTO `department_info` VALUES (7, '技術(shù)部', 4, 4);INSERT INTO `department_info` VALUES (8, '財務(wù)部', 4, 5);INSERT INTO `department_info` VALUES (9, '行政部', 4, 5);INSERT INTO `department_info` VALUES (10, '客戶端', 5, 7);INSERT INTO `department_info` VALUES (11, '服務(wù)端', 5, 7);函數(shù)的創(chuàng)建

由于父子節(jié)點(diǎn)的查詢，需要依賴遞歸，為了查詢方便，這里創(chuàng)建兩個函數(shù)：

遞歸查詢子孫節(jié)點(diǎn)ID的函數(shù)DROP FUNCTION IF EXISTS queryChildrenDepInfo;DELIMITER ;;CREATE FUNCTION queryChildrenDepInfo(dep_id INT)RETURNS VARCHAR(4000)BEGINDECLARE sTemp VARCHAR(4000);DECLARE sTempChd VARCHAR(4000);SET sTemp='$';SET sTempChd = CAST(dep_id AS CHAR);WHILE sTempChd IS NOT NULL DOSET sTemp= CONCAT(sTemp,',',sTempChd);SELECT GROUP_CONCAT(id) INTO sTempChd FROM department_info WHERE FIND_IN_SET(parent_id,sTempChd)>0;END WHILE;RETURN sTemp;END;;DELIMITER ;測試：查詢技術(shù)部下的所有重要節(jié)點(diǎn)？SELECT queryChildrenDepInfo(4);SELECT * FROM department_info WHERE FIND_IN_SET(id,queryChildrenDepInfo(4));遞歸查詢祖先節(jié)點(diǎn)ID的函數(shù)DROP FUNCTION IF EXISTS queryParentDepInfo;DELIMITER;;CREATE FUNCTION queryParentDepInfo(dep_id INT)RETURNS VARCHAR(4000)BEGINDECLARE sTemp VARCHAR(4000);DECLARE sTempChd VARCHAR(4000);SET sTemp='$';SET sTempChd = CAST(dep_id AS CHAR);SET sTemp = CONCAT(sTemp,',',sTempChd);SELECT parent_id INTO sTempChd FROM department_info WHERE id = sTempChd;WHILE sTempChd <> 0 DOSET sTemp = CONCAT(sTemp,',',sTempChd);SELECT parent_id INTO sTempChd FROM department_info WHERE id = sTempChd;END WHILE;RETURN sTemp;END;;DELIMITER ;測試：查詢技術(shù)部所有的祖先節(jié)點(diǎn)？SELECT queryParentDepInfo(7);SELECT * FROM department_info WHERE FIND_IN_SET(id,queryParentDepInfo(7));節(jié)點(diǎn)的增刪改增加節(jié)點(diǎn)比如要在技術(shù)部下添加一個測試部門INSERT INTO department_info(`id`, `dep_name`, `level`, `parent_id`) VALUES (12, '測試部', 5, 7);修改節(jié)點(diǎn)比如：將測試部（ID = 12）提出來，放到產(chǎn)品部（ID = 4）下；就只需要將測試部對應(yīng)的父節(jié)點(diǎn)ID修改為4即可SET @id = 12;SET @pid = 4;UPDATE department_info SET `parent_id` = @pid WHERE `id` = @id;刪除節(jié)點(diǎn)刪除相比于添加修改，情況就會特殊一些，如果刪除的節(jié)點(diǎn)存在子節(jié)點(diǎn)，意味著子節(jié)點(diǎn)也需要同步刪除掉；因此這里就需要用到上面創(chuàng)建的遞歸查詢子孫節(jié)點(diǎn)ID的函數(shù)（queryChildrenDepInfo）比如：刪除技術(shù)部門；DELETE FROM department_info WHERE FIND_IN_SET(id,queryChildrenDepInfo(7));是否存在子節(jié)點(diǎn)（葉子節(jié)點(diǎn)）

在該方案下，要想判斷是否是葉子節(jié)點(diǎn)，有兩種實(shí)現(xiàn)方式：

統(tǒng)計當(dāng)前節(jié)點(diǎn)以及子孫節(jié)點(diǎn)的數(shù)量遞歸查詢所有子節(jié)點(diǎn)的ID，并統(tǒng)計數(shù)量，由于函數(shù)查詢包含了節(jié)點(diǎn)自身，所以這里使用了COUNT(*)-1來計算子節(jié)點(diǎn)的數(shù)量，如果等于0就是葉子節(jié)點(diǎn)，大于0說明不是葉子節(jié)點(diǎn)；-- 查看設(shè)計部（ID=6）是不是葉子節(jié)點(diǎn)SET @id = 6;-- 由于數(shù)量包含了自身，由于統(tǒng)計的是子節(jié)點(diǎn)的數(shù)量，所以這里需要-1將自己去掉SELECT COUNT(*)-1 FROM department_info WHERE FIND_IN_SET(id,queryChildrenDepInfo(@id));添加葉子節(jié)點(diǎn)的標(biāo)記在表中添加一個isLeaf字段，當(dāng)節(jié)點(diǎn)增刪改操作的時候，用這個字段來標(biāo)記一下當(dāng)前是否是葉子節(jié)點(diǎn)查詢出所有的下級部門（子節(jié)點(diǎn)）

查詢所有的下級部門，此時就需要借助當(dāng)前節(jié)點(diǎn)的id和level字段

例：查詢產(chǎn)品部（id = 4，level = 3）的子節(jié)點(diǎn)

SET @id = 4;SET @lv = 3;SELECT * from department_info where parent_id = @id AND `level` = @lv + 1;查詢所有的下下級部門（孫節(jié)點(diǎn)）

實(shí)際業(yè)務(wù)場景下，這種需求很少，這里主要用來演示可操作性，不排除特殊的場合下用得上；

查詢孫節(jié)點(diǎn)相比與子節(jié)點(diǎn)就麻煩很多了，因為當(dāng)前節(jié)點(diǎn)和孫節(jié)點(diǎn)是沒有任何數(shù)據(jù)上的關(guān)聯(lián)，因此需要借助子節(jié)點(diǎn)才能找到孫節(jié)點(diǎn)，因此這里又必須得用上遞歸查詢子孫節(jié)點(diǎn)ID的函數(shù)了；

例：查詢產(chǎn)品部（id = 4，level = 3）的孫節(jié)點(diǎn)

-- 查詢孫節(jié)點(diǎn)SET @id = 4;SET @lv = 3;SELECT * FROM department_info WHERE FIND_IN_SET(id,queryChildrenDepInfo(@id)) AND `level` = @lv + 2;查詢所有的下屬部門

查詢下屬部門就和查詢下下級部門（孫節(jié)點(diǎn)）類似，只是不用校驗層級即可；

例：查詢產(chǎn)品部下所有的下屬部門？

SET @id = 4;SELECT * FROM department_info WHERE FIND_IN_SET(id,queryChildrenDepInfo(@id));查詢隸屬部門

也就是查詢節(jié)點(diǎn)；在該方案下，節(jié)點(diǎn)中已經(jīng)保存了父節(jié)點(diǎn)的ID，通過ID就能直接獲取到父節(jié)點(diǎn)

查詢所有上級部門

由于當(dāng)前節(jié)點(diǎn)只保存了父級節(jié)點(diǎn)ID，更上一級的信息只能通過遞歸逐級獲取；

例：查詢技術(shù)部（id = 7）的所有上級部門；

SET @id = 7;SELECT * FROM department_info WHERE FIND_IN_SET(id,queryParentDepInfo(@id));統(tǒng)計所有下屬部門的數(shù)量

和查詢是否是葉子節(jié)點(diǎn)的方式一樣，只是對得到的數(shù)據(jù)解讀的方式不同而已；

例：統(tǒng)計技術(shù)部的下屬部門數(shù)量？

SET @id = 7;SELECT COUNT(*)-1 FROM department_info WHERE FIND_IN_SET(id,queryChildrenDepInfo(@id));2改進(jìn)后的先序樹方案

從從上述的父子關(guān)系方案可以看出，大部分的操作，都需要遞歸查詢出所有的子孫節(jié)點(diǎn)后才行，如果出現(xiàn)文章開始說的，層級多，深度深的話，遞歸的過程，就會大大影響查詢、統(tǒng)計的性能；

下面就來介紹一下改進(jìn)后的先序樹的樹形結(jié)構(gòu)方案，節(jié)點(diǎn)不再保存父節(jié)點(diǎn)的ID，而是為每個節(jié)點(diǎn)增加左值和右值：

如下圖示：

對應(yīng)的數(shù)據(jù)如下：

iddep_name(部門名稱)lt(左值)rt(右值)lv(層級)1董事會12212總經(jīng)理21923董事會秘書202124產(chǎn)品部31235行政總監(jiān)131836設(shè)計部4547技術(shù)部61148財務(wù)部141549行政部1617410客戶端78511服務(wù)端9105

SQL語句：

DROP TABLE IF EXISTS `department_info2`;CREATE TABLE `department_info2` ( `id` int(11) NOT NULL AUTO_INCREMENT, `dep_name` varchar(255) CHARACTER SET utf8mb4 COLLATE utf8mb4_general_ci NOT NULL COMMENT '名稱', `lt` int(11) NOT NULL COMMENT '節(jié)點(diǎn)左數(shù)', `rt` int(11) NOT NULL COMMENT '節(jié)點(diǎn)右數(shù)', `lv` int(11) NOT NULL, PRIMARY KEY (`id`) USING BTREE) ENGINE = InnoDB AUTO_INCREMENT = 12 CHARACTER SET = utf8mb4 COLLATE = utf8mb4_general_ci ROW_FORMAT = Dynamic;INSERT INTO `department_info2` VALUES (1, '董事會', 1, 22, 1);INSERT INTO `department_info2` VALUES (2, '總經(jīng)理', 2, 19, 2);INSERT INTO `department_info2` VALUES (3, '董事會秘書', 20, 21, 2);INSERT INTO `department_info2` VALUES (4, '產(chǎn)品部', 3, 12, 3);INSERT INTO `department_info2` VALUES (5, '行政總監(jiān)', 13, 18, 3);INSERT INTO `department_info2` VALUES (6, '設(shè)計部', 4, 5, 4);INSERT INTO `department_info2` VALUES (7, '技術(shù)部', 6, 11, 4);INSERT INTO `department_info2` VALUES (8, '財務(wù)部', 14, 15, 4);INSERT INTO `department_info2` VALUES (9, '行政部', 16, 17, 4);INSERT INTO `department_info2` VALUES (10, '客戶端', 7, 8, 5);INSERT INTO `department_info2` VALUES (11, '服務(wù)端', 9, 10, 5);方案特點(diǎn)優(yōu)點(diǎn)查詢匯總簡單高效無需遞歸查詢，性能高缺點(diǎn)結(jié)構(gòu)相對復(fù)雜，數(shù)據(jù)層面理解難度較高不易維護(hù)以為左右值的存在，會直接影響到后續(xù)的節(jié)點(diǎn)，因此，當(dāng)前節(jié)點(diǎn)增刪改時，都會對后續(xù)的節(jié)點(diǎn)產(chǎn)業(yè)影響；示例節(jié)點(diǎn)的增刪改新增如下圖：在技術(shù)部下新增一個測試部，新增節(jié)點(diǎn)對應(yīng)的左右值分別為11、12；過程分析：第一步，所有比11（新增節(jié)點(diǎn)的左數(shù)）大的左數(shù)全部+2（紫色部分）第二步，所有比12（新增節(jié)點(diǎn)的右數(shù)）大的右數(shù)全部+2（橙色部分）第三步，添加左右數(shù)分別為11、12的部門節(jié)點(diǎn)由于這里涉及到多個步驟，我們需要保證數(shù)據(jù)庫操作的原子性，因此需要做事務(wù)操作，這里為了方便，創(chuàng)建一個存儲過程；存儲過程并不式必須的，同樣也可以以代碼的形式來保證事務(wù)操作；只是使用存儲過程，可靠性會高一些；添加節(jié)點(diǎn)存儲過程：DROP PROCEDURE IF EXISTS inrtDepartment;CREATE PROCEDURE inrtDepartment(IN lt_i INT,IN rt_i INT,IN lv_i INT,IN dn VARCHAR(256))BEGINDECLARE d_error INTEGER DEFAULT 0;DECLARE CONTINUE HANDLER FOR SQLEXCEPTION SET d_error= -2;-- 異常時設(shè)置為1DECLARE CONTINUE HANDLER FOR NOT FOUND SET d_error = -3; -- 如果表中沒有下一條數(shù)據(jù)則置為2START TRANSACTION;-- 將所有左值大于新增左值的部門全部+2UPDATE department_info2 SET lt=lt+2 WHERE lt > lt_i;-- 將所有右值大于新增右值的部門全部+2UPDATE department_info2 SET rt=rt+2 WHERE rt >= lt_i;-- 新增部門INSERT INTO department_info2(dep_name,lt,rt,lv) VALUES(dn,lt_i,rt_i,lv_i);SET d_error= ROW_COUNT();IF d_error != 1 THENROLLBACK;-- 結(jié)果不等于1 的時候，說明新增失敗，回滾操作ELSECOMMIT; -- 等于1的時候，說明添加成功，提交END IF;lect d_error;END輸入?yún)?shù)lt_i ：新增部門的左值rt_i：新增部門的右值lv_i：行政部門的層級dn：部門名稱如上圖的示例，就可以調(diào)用新增的存儲過程添加：call inrtDepartment(11, 12, 5,"測試部");修改普通的節(jié)點(diǎn)信息修改，這里就不多多說了，很簡單；節(jié)點(diǎn)移動是此方案下，最復(fù)雜的修改操作，因為整個過程涉及到位置的變化，層級的變化等多個維度的調(diào)整，而且還得保證事務(wù)操作；例：我們要將技術(shù)部（id = 4）交由總經(jīng)理（id = 2）直接負(fù)責(zé)，也就是移動到總經(jīng)理之下；過程分析：第一步，計算技術(shù)部的左右數(shù)差值第二步，計算與移動后的上級節(jié)點(diǎn)之間的差值第三步，確定是左移還是右移第四步，將本節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)之間的差值減去（左移）/加上（右移）第五步，將移動的節(jié)點(diǎn)以及子孫的節(jié)點(diǎn)與父節(jié)點(diǎn)之間的差值減去（左移）/加上（右移）第六步，調(diào)整層級整個過程如下圖所示，稍微有點(diǎn)點(diǎn)復(fù)雜，可以結(jié)合圖示以及存儲過程的代碼，仔細(xì)的理解一下：為了方便操作，避免出錯，這里同樣以存儲過程的方式來實(shí)現(xiàn)核心邏輯，降低出錯風(fēng)險：DROP PROCEDURE IF EXISTS moveDepartment;CREATE PROCEDURE moveDepartment(IN fid INT,IN tid INT)BEGINDECLARE d_error INTEGER DEFAULT 0;DECLARE num INTEGER DEFAULT 0; -- 刪除節(jié)點(diǎn)左右值之間的差值DECLARE mnum INTEGER DEFAULT 0; -- 移動階段與上級節(jié)點(diǎn)之間的差值DECLARE ids VARCHAR(1000); -- 保存所有正在移動的id集合，保證多個節(jié)點(diǎn)移動時也能正常DECLARE blt INT; -- 需要移動節(jié)點(diǎn)的左數(shù)DECLARE brt INT; -- 需要移動節(jié)點(diǎn)的右數(shù)DECLARE blv INT; -- 需要移動節(jié)點(diǎn)的層級DECLARE tlt INT; -- 目標(biāo)節(jié)點(diǎn)的左數(shù)DECLARE trt INT; -- 目標(biāo)節(jié)點(diǎn)的右數(shù)DECLARE tlv INT; -- 目標(biāo)節(jié)點(diǎn)的層級DECLARE CONTINUE HANDLER FOR SQLEXCEPTION SET d_error= -2;-- 異常時設(shè)置為1DECLARE CONTINUE HANDLER FOR NOT FOUND SET d_error = -3; -- 如果表中沒有下一條數(shù)據(jù)則置為2START TRANSACTION;-- 查詢待移動的節(jié)點(diǎn)的左右數(shù)以及層級SELECT lt,rt,lv INTO blt, brt,blv FROM department_info2 WHERE id = fid;-- 查詢目標(biāo)節(jié)點(diǎn)的左右數(shù)以及層級SELECT lt,rt,lv INTO tlt, trt,tlv FROM department_info2 WHERE id = tid;-- 查詢所有要一定的節(jié)點(diǎn)，當(dāng)前節(jié)點(diǎn)以及其子孫節(jié)點(diǎn)SELECT GROUP_CONCAT(id) INTO ids FROM department_info2 WHERE lt>=blt AND rt <=brt;IF tlt > blt AND trt < brt THEN-- 將自己移動到自己的下屬節(jié)點(diǎn) 暫時不允許 如果要如此操作，需要將下級調(diào)整為平級 再移動SET d_error = -4;ELSEIF blt > tlt AND brt < trt AND blv = tlv + 1 THEN-- 說明本身就已經(jīng)是目標(biāo)節(jié)點(diǎn)在子節(jié)點(diǎn)了，不需要處理，直接成功SET d_error = 0;ELSE-- 計算移動節(jié)點(diǎn)與上級節(jié)點(diǎn)之間的差值SET mnum = trt - brt -1;-- 計算當(dāng)前節(jié)點(diǎn)及其子節(jié)點(diǎn)的差值SET num = brt - blt + 1;-- 首先將移動前的節(jié)點(diǎn)整個元素表中移除掉IF trt > brt THEN-- 左往右移動UPDATE department_info2 SET lt=lt-num WHERE lt > brt AND lt < trt;UPDATE department_info2 SET rt=rt-num WHERE rt > brt AND rt < trt;ELSE-- 從右往左移動 將系數(shù)全部變?yōu)樨?fù)值，-負(fù)數(shù)就等于+正數(shù)SET mnum = -mnum;SET num = -num;UPDATE department_info2 SET lt=lt-num WHERE lt >= trt AND lt < blt;UPDATE department_info2 SET rt=rt-num WHERE rt >= trt AND rt < blt;END IF;-- 調(diào)整移動的節(jié)點(diǎn)以及下屬節(jié)點(diǎn)UPDATE department_info2 SET lt=lt+mnum,rt=rt+mnum,lv = lv - (blv - tlv -1) WHERE FIND_IN_SET(id,ids);SET d_error= ROW_COUNT();IF d_error <= 0 THENROLLBACK;ELSECOMMIT;END IF;END IF;lect d_error;END輸入?yún)?shù)fid：移動的節(jié)點(diǎn)idtid：目標(biāo)節(jié)點(diǎn)id測試：CALL moveDepartment(7,2)刪除刪除的過程正好與新增相反，在刪除節(jié)點(diǎn)及其自己點(diǎn)的時候，大于刪除節(jié)點(diǎn)的所有左右值都需要減去刪除節(jié)點(diǎn)的左右差值+1；如下圖示例：刪除技術(shù)部過程：第一步，計算出刪除節(jié)點(diǎn)的左右差值+1；技術(shù)部的左右值分別時6和11，差值+1：11 - 6 + 1第二步，刪除節(jié)點(diǎn)機(jī)器所有子節(jié)點(diǎn)第三步，所有大于刪除節(jié)點(diǎn)左右值的節(jié)點(diǎn)，全部減去差值同樣為了方便操作，我們也創(chuàng)建一個存儲過程：DROP PROCEDURE IF EXISTS removeDepartment;CREATE PROCEDURE removeDepartment(IN did INT)BEGINDECLARE d_error INTEGER DEFAULT 0;DECLARE num INTEGER DEFAULT 0; -- 刪除節(jié)點(diǎn)左右值之間的差值DECLARE dlt INT; -- 刪除節(jié)點(diǎn)的左值DECLARE drt INT; -- 刪除節(jié)點(diǎn)的右值值DECLARE CONTINUE HANDLER FOR SQLEXCEPTION SET d_error= -2;-- 異常時設(shè)置為1DECLARE CONTINUE HANDLER FOR NOT FOUND SET d_error = -3; -- 如果表中沒有下一條數(shù)據(jù)則置為2START TRANSACTION;-- 查詢刪除節(jié)點(diǎn)的左右值SELECT lt,rt INTO dlt, drt FROM department_info2 WHERE id = did;-- 計算當(dāng)前節(jié)點(diǎn)及其子節(jié)點(diǎn)的差值SET num = drt - dlt + 1;-- 刪除當(dāng)前節(jié)點(diǎn)及其子節(jié)點(diǎn)DELETE FROM department_info2 WHERE lt>=dlt AND rt<=drt;SET d_error= ROW_COUNT();-- 左右值減少對應(yīng)的插值UPDATE department_info2 SET lt=lt-num WHERE lt > dlt;UPDATE department_info2 SET rt=rt-num WHERE rt > drt;IF d_error != num/2 THEN -- 判斷刪除的數(shù)量與當(dāng)前節(jié)點(diǎn)+子孫節(jié)點(diǎn)的數(shù)量是否一致；不一致的話，直接回滾ROLLBACK;ELSECOMMIT;END IF;lect d_error;END測試：-- 設(shè)計部的id = 7SET @id=7;call removeDepartment(@id);是否存在子節(jié)點(diǎn)（葉子節(jié)點(diǎn)）

無需額外的查詢，直接通過節(jié)點(diǎn)的左右數(shù)，即可判斷是否是葉子節(jié)點(diǎn)了；當(dāng)右數(shù) - 左數(shù) = 1時，說明當(dāng)前節(jié)點(diǎn)就屬于葉子節(jié)點(diǎn)，否則就不是；

查詢所有的下級部門

等價于：查詢左數(shù)比當(dāng)前節(jié)點(diǎn)大，右數(shù)比當(dāng)前節(jié)點(diǎn)小，且層比當(dāng)前節(jié)點(diǎn)大1的所有節(jié)點(diǎn)；

例：查詢產(chǎn)品部（lt = 3，rt = 12，lv = 3）的所有下級部門：

SET @lt = 3; -- 節(jié)點(diǎn)左數(shù)SET @rt = 12; -- 節(jié)點(diǎn)右數(shù)SET @lv = 3; -- 當(dāng)先的層級SELECT * from department_info2 where lt > @lt AND rt < @rt AND `lv` = @lv + 1查詢所有的下下級部門（孫節(jié)點(diǎn)）

實(shí)際業(yè)務(wù)中很少會出現(xiàn)此需求，這里僅僅用于可行性演示；

孫節(jié)點(diǎn)的查詢和子節(jié)點(diǎn)類似，僅僅層級由+1變?yōu)榱?2

例：查詢產(chǎn)品部（lt = 3，rt = 12，lv = 3）的所有下下級部門：

SET @lt = 3; -- 節(jié)點(diǎn)左數(shù)SET @rt = 12; -- 節(jié)點(diǎn)右數(shù)SET @lv = 3; -- 當(dāng)先的層級SELECT * from department_info2 where lt > @lt AND rt < @rt AND `lv` = @lv + 2;查詢所有下屬部門

等價于：比當(dāng)前節(jié)點(diǎn)左數(shù)大，右數(shù)小的節(jié)點(diǎn)，全部是子孫節(jié)點(diǎn)；

例，查詢產(chǎn)品部（lt = 3，rt = 12）的所有下屬部門：

SET @lt = 3; -- 節(jié)點(diǎn)左數(shù)SET @rt = 12; -- 節(jié)點(diǎn)右數(shù)SELECT * from department_info2 where lt > @lt AND rt < @rt;查詢隸屬部門

等價于：左數(shù)比自己小，右數(shù)比自己大，且層級-1的節(jié)點(diǎn)，也就是父節(jié)點(diǎn)

例，查詢技術(shù)部（lt = 6 ， rt = 11）的隸屬部門：

SET @lt = 6; -- 節(jié)點(diǎn)左數(shù)SET @rt = 11; -- 節(jié)點(diǎn)右數(shù)SET @lv = 4; -- 當(dāng)先的層級SELECT * from department_info2 where lt < @lt AND rt > @rt AND `lv` = @lv - 1 ;查詢所有的上級部門

與查詢父節(jié)點(diǎn)類似，只是不再需要校驗層級了，所有左數(shù)比自己小，右數(shù)比自己大都是自己的祖先節(jié)點(diǎn)；

例，查詢產(chǎn)品部（lt = 3，rt = 12）的所有上級部門

SET @lt = 3; -- 節(jié)點(diǎn)左數(shù)SET @rt = 12; -- 節(jié)點(diǎn)右數(shù)SELECT * from department_info2 where lt < @lt AND rt > @rt;統(tǒng)計所有下屬部門的數(shù)量

統(tǒng)計子孫節(jié)點(diǎn)數(shù)量，無需額外查詢，只需根據(jù)自己的左右數(shù)，即可計算出子節(jié)點(diǎn)的數(shù)量；

計算公式：（右數(shù) - 左數(shù) - 1 ）/ 2；

例，計算產(chǎn)品部（id = 4）的下屬部門的數(shù)量：

SELECT dep_name,(rt - lt - 1) / 2 as num FROM department_info2 where id = 43格式化數(shù)據(jù)

不管是那種方案，數(shù)據(jù)層面都是扁平的，只是通過字段邏輯表達(dá)了結(jié)構(gòu)化的關(guān)系，那查詢出來之后，要如何將數(shù)據(jù)結(jié)構(gòu)化成樹形結(jié)構(gòu)之后展示呢，下面介紹遞歸和非遞歸的兩種方式實(shí)現(xiàn)方式:

基礎(chǔ)的對象@Data@RequiredArgsConstructorpublic class LrItem {@NonNullprivate Integer id;@NonNullprivate String depName;@NonNullprivate Integer left;@NonNullprivate Integer right;private Integer level;private Integer parentId;/*** 是否是葉子*/private Boolean isLeaf;private List<LrItem> childItem;}測試數(shù)據(jù)這里只是演示格式化數(shù)據(jù)，就不整那么復(fù)雜了；實(shí)際業(yè)務(wù)場景，這批數(shù)據(jù)一般都是從數(shù)據(jù)庫中查詢出來的。List<LrItem> deps = new ArrayList<>();deps.add(new LrItem(1, "董事會", 1, 22));deps.add(new LrItem(2, "總經(jīng)理", 2, 19));deps.add(new LrItem(3, "董事會秘書", 20, 21));deps.add(new LrItem(4, "產(chǎn)品部", 3, 12));deps.add(new LrItem(5, "行政總監(jiān)", 13, 18));deps.add(new LrItem(6, "設(shè)計部", 4, 5));deps.add(new LrItem(7, "技術(shù)部", 6, 11));deps.add(new LrItem(8, "財務(wù)部", 14, 15));deps.add(new LrItem(9, "行政部", 16, 17));deps.add(new LrItem(10, "客戶端", 7, 8));deps.add(new LrItem(11, "服務(wù)端", 9, 10));整理數(shù)據(jù)public static void init(List<LrItem> deps) {// 如果數(shù)據(jù)庫排序過了之后 這里就不用排序了deps.sort(Comparator.comparing(LrItem::getLeft));// 為計算層級 緩存節(jié)點(diǎn)右側(cè)的值List<Integer> rights = new ArrayList<>();Map<Integer, Integer> mp = new HashMap<>();// 初始化節(jié)點(diǎn)的層級，葉子節(jié)點(diǎn) 以及 父節(jié)點(diǎn)ID 對應(yīng)的數(shù)據(jù)deps.forEach(item -> {if (rights.size() > 0) {// 一旦發(fā)現(xiàn)本次節(jié)點(diǎn)右側(cè)的值比前一次的大，說明出現(xiàn)層級上移了 需要移除前一個底層及的值// 這里大部分情況下只存在移除前面一個值情況while (rights.get(rights.size() - 1) < item.getRight()) {rights.remove(rights.size() - 1);//從rights末尾去除}}Integer _level = rights.size() + 1;item.tLevel(_level);mp.put(_level, item.getId());item.tParentId(mp.containsKey(_level - 1) ? mp.get(_level - 1) : 0); //計算出上級部門編號item.tIsLeaf(item.getLeft() == item.getRight() - 1);//判斷是否葉子部門rights.add(item.getRight());});System.out.println(rights);System.out.println(mp);}遞歸整理

遞歸的思路比較簡單清晰，就是拿到當(dāng)前節(jié)點(diǎn)之后，在所有是節(jié)點(diǎn)中找自己的子節(jié)點(diǎn)，當(dāng)所有節(jié)點(diǎn)都找過一遍之后，整個樹形結(jié)構(gòu)話的過程就完了；

我們可以結(jié)合Java 8 Stream新特性，讓整個遞歸代碼相對簡單清晰；

/** * @param deps 所有數(shù)據(jù) */public static void recursive(List<LrItem> deps) { init(deps); //獲取父節(jié)點(diǎn) List<LrItem> collect = deps.stream() .filter(m -> m.getParentId() == 0) .map(m -> { m.tChildItem(getChildrens(m, deps)); return m; } ).collect(Collectors.toList()); // 普遍請求下，根節(jié)點(diǎn)只會有一個，所以這里取出第一個元素，如果由多個，可根據(jù)需求調(diào)整，這里僅做測試使用 System.out.println(JSON.toJSON(collect.get(0)));}/** * 遞歸查詢子節(jié)點(diǎn) * * @param root 根節(jié)點(diǎn) * @param all 所有節(jié)點(diǎn) * @return 根節(jié)點(diǎn)信息 */private static List<LrItem> getChildrens(LrItem root, List<LrItem> all) { List<LrItem> children = all.stream() .filter(m -> Objects.equals(m.getParentId(), root.getId())) .map(m -> { m.tChildItem(getChildrens(m, all)); return m; } ).collect(Collectors.toList()); return children;}非遞歸倒序整理

這是一個以空間換時間的方案；

此方式的特點(diǎn)：按層級排序后的數(shù)據(jù)，只需要一次for循環(huán)，就能整理出結(jié)構(gòu)化的數(shù)據(jù)。

第一步，計算出層級以及父節(jié)點(diǎn)ID第二步，按層級進(jìn)行排序第三步，倒序從最深的節(jié)點(diǎn)讓root節(jié)點(diǎn)遍歷遍歷過程以Map<Integer, List<LrItem>>的方式緩存ID及當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)，當(dāng)上升一個層級之后，就將Map中緩存的關(guān)于我的自階段取出來，保存到自己對象的childItem字段中

public static void reverFormat(List<LrItem> deps) { init(deps); deps.sort(Comparator.comparing(LrItem::getLevel)); deps.forEach(item -> System.out.println(JSON.toJSONString(item))); // 臨時緩存各自節(jié)點(diǎn)的容器 Map<Integer, List<LrItem>> childCache = new HashMap<>(); // 當(dāng)前節(jié)點(diǎn) LrItem lrItem = null; //int level = 0; // 采用倒序遍歷，整理各個子節(jié)點(diǎn)的集合 for (int i = deps.size() - 1; i >= 0; i--) { lrItem = deps.get(i); Integer parentId = lrItem.getParentId(); if (null == lrItem || null == parentId) { continue; } List<LrItem> childItems = childCache.get(parentId); if (null == childItems) { childCache.put(parentId, childItems = new ArrayList<>()); } childItems.add(lrItem); // 如果不是葉子節(jié)點(diǎn)的時候，說明他肯定有子節(jié)點(diǎn)，去緩存中找到，回填回去 if (!lrItem.getIsLeaf()) { childItems = childCache.get(lrItem.getId()); childItems.sort(Comparator.comparing(LrItem::getId)); lrItem.tChildItem(childItems); childCache.remove(lrItem.getId()); } } System.out.println(JSON.toJSONString(lrItem));}格式化后的數(shù)據(jù)

不管那種方式，最終都會得到以下的結(jié)構(gòu)化數(shù)據(jù)；

{ "depName": "董事會", "id": 1, "isLeaf": fal, "left": 1, "level": 1, "prientId": 0, "right": 22, "childItem": [ { "depName": "總經(jīng)理", "id": 2, "isLeaf": fal, "left": 2, "level": 2, "prientId": 1, "right": 19, "childItem": [ { "depName": "行政總監(jiān)", "id": 5, "isLeaf": fal, "left": 13, "level": 3, "prientId": 2, "right": 18, "childItem": [ { "depName": "設(shè)計部", "id": 6, "isLeaf": true, "left": 4, "level": 4, "prientId": 4, "right": 5 }, { "depName": "技術(shù)部", "id": 7, "isLeaf": fal, "left": 6, "level": 4, "prientId": 4, "right": 11, "childItem": [ { "depName": "客戶端", "id": 10, "isLeaf": true, "left": 7, "level": 5, "prientId": 7, "right": 8 }, { "depName": "服務(wù)端", "id": 11, "isLeaf": true, "left": 9, "level": 5, "prientId": 7, "right": 10 } ] } ], "depName": "產(chǎn)品部", "id": 4, "isLeaf": fal, "left": 3, "level": 3, "prientId": 2, "right": 12 }, { "childItem": [ { "depName": "財務(wù)部", "id": 8, "isLeaf": true, "left": 14, "level": 4, "prientId": 5, "right": 15 }, { "depName": "行政部", "id": 9, "isLeaf": true, "left": 16, "level": 4, "prientId": 5, "right": 17 } ] } ] }, { "depName": "董事會秘書", "id": 3, "isLeaf": true, "left": 20, "level": 2, "prientId": 1, "right": 21 } ]}4比較

針對上面的詳解，下來以表格的形式來更直觀的對兩者做一下對比：

功能父子關(guān)系方案先序數(shù)方案新增簡單復(fù)雜修改簡單復(fù)雜刪除復(fù)雜復(fù)雜判斷葉子節(jié)點(diǎn)復(fù)雜（除非增加編輯難度，提前整理好）簡單查詢子節(jié)點(diǎn)簡單簡單查詢孫節(jié)點(diǎn)復(fù)雜簡單查詢父節(jié)點(diǎn)簡單簡單查詢祖先節(jié)點(diǎn)復(fù)雜簡單統(tǒng)計子孫節(jié)點(diǎn)數(shù)量復(fù)雜簡單適用場景結(jié)構(gòu)簡單，層級少，統(tǒng)計少，頻繁改動結(jié)構(gòu)復(fù)雜，改動少，層級深，需要復(fù)雜統(tǒng)計

5總結(jié)

經(jīng)過對兩種方案常用場景的分析，發(fā)現(xiàn)其實(shí)各自都有自己的優(yōu)缺點(diǎn)，所以原諒我標(biāo)題稍微有點(diǎn)點(diǎn)標(biāo)題黨；相比起來，個人還是比較喜歡改進(jìn)的先序數(shù)方案

父子關(guān)系方案適合結(jié)構(gòu)相對簡單、層級少的需求；

而先序數(shù)方案就更適合結(jié)構(gòu)復(fù)雜，改動少，層級深，需要頻繁匯總統(tǒng)計的需求了；

所以說，還是那句話，沒有絕對好的方案，只有合不合適的場景；需要更具自己業(yè)務(wù)的實(shí)際情況，酌情挑選對項目最有利的方案。

好了，今天的分享就到這里；如果有任何問題，歡迎隨時交流指正！