Mysql樹形結構的資料庫表設計方案

2021-09-22 13:03:06

前言

最近研究樹形選單網上找了很多例子看了。一下是網上找的一些資料，然後自己重新實踐，記錄下免得下次又忘記了。

程式設計過程中，我們常常用樹形結構來表徵某些資料的關聯關係，如企業上下級部門、欄目結構、商品分類等等，通常而言，這些樹狀結構需要藉助於資料庫完成持久化。然而目前的各種基於關係的資料庫，都是以二維表的形式記錄儲存資料資訊，因此是不能直接將Tree存入DBMS，設計合適的Schema及其對應的CRUD演演算法是實現關係型資料庫中儲存樹形結構的關鍵。

理想中樹形結構應該具備如下特徵：資料儲存冗餘度小、直觀性強；檢索遍歷過程簡單高效；節點增刪改查CRUD操作高效。無意中在網上搜尋到一種很巧妙的設計，原文是英文，看過後感覺有點意思，於是便整理了一下。本文將介紹兩種樹形結構的Schema設計方案：一種是直觀而簡單的設計思路，另一種是基於左右值編碼的改進方案。

一、基本資料

本文列舉了一個食品族譜的例子進行講解，通過類別、顏色和品種組織食品，樹形結構圖如下：

二、繼承關係驅動的設計

對樹形結構最直觀的分析莫過於節點之間的繼承關係上，通過顯示地描述某一節點的父節點，從而能夠建立二維的關係表，則這種方案的Tree表結構通常設計為：{Node_id,Parent_id}，上述資料可以描述為如下圖所示：

這種方案的優點很明顯：設計和實現自然而然，非常直觀和方便。缺點當然也是非常的突出：由於直接地記錄了節點之間的繼承關係，因此對Tree的任何CRUD操作都將是低效的，這主要歸根於頻繁的「遞迴」操作，遞迴過程不斷地存取資料庫，每次資料庫IO都會有時間開銷。當然，這種方案並非沒有用武之地，在Tree規模相對較小的情況下，我們可以藉助於快取機制來做優化，將Tree的資訊載入記憶體進行處理，避免直接對資料庫IO操作的效能開銷。

三、基於左右值編碼的設計

在基於資料庫的一般應用中，查詢的需求總要大於刪除和修改。為了避免對於樹形結構查詢時的「遞迴」過程，基於Tree的前序遍歷設計一種全新的無遞迴查詢、無限分組的左右值編碼方案，來儲存該樹的資料。

第一次看見這種表結構，相信大部分人都不清楚左值（Lft）和右值（Rgt）是如何計算出來的，而且這種表設計似乎並沒有儲存父子節點的繼承關係。但當你用手指指著表中的數位從1數到18，你應該會發現點什麼吧。對，你手指移動的順序就是對這棵樹進行前序遍歷的順序，如下圖所示。當我們從根節點Food左側開始，標記為1，並沿前序遍歷的方向，依次在遍歷的路徑上標註數位，最後我們回到了根節點Food，並在右邊寫上了18。

依據此設計，我們可以推斷出所有左值大於2，並且右值小於11的節點都是Fruit的後續節點，整棵樹的結構通過左值和右值儲存了下來。然而，這還不夠，我們的目的是能夠對樹進行CRUD操作，即需要構造出與之配套的相關演演算法。

四、樹形結構CRUD演演算法

（1）獲取某節點的子孫節點

只需要一條SQL語句，即可返回該節點子孫節點的前序遍歷列表，以Fruit為例：

SELECT * FROM tree WHERE lft BETWEEN 2 AND 11 ORDER BY lft ASC

查詢結果如下所示：

那麼某個節點到底有多少的子孫節點呢？通過該節點的左、右值我們可以將其子孫節點圈進來，則子孫總數 = (右值 – 左值– 1) / 2，以Fruit為例，其子孫總數為：(11 –2 – 1) / 2 = 4。同時，為了更為直觀地展現樹形結構，我們需要知道節點在樹中所處的層次，通過左、右值的SQL查詢即可實現，以Fruit為例：SELECTCOUNT(*) FROM tree WHERE lft <= 2 AND rgt >=11。為了方便描述，我們可以為Tree建立一個檢視，新增一個層次數列，該列數值可以寫一個自定義函數來計算，函數定義如下：

建立表

CREATE TABLE `tree` (
  `id` int(11) NOT NULL,
  `name` varchar(255) DEFAULT NULL,
  `lft` int(255) DEFAULT NULL,
  `rgt` int(11) DEFAULT NULL
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

INSERT INTO `jpa`.`tree` (`id`, `name`, `lft`, `rgt`) VALUES ('1', 'Food', '1', '18');
INSERT INTO `jpa`.`tree` (`id`, `name`, `lft`, `rgt`) VALUES ('2', 'Fruit', '2', '11');
INSERT INTO `jpa`.`tree` (`id`, `name`, `lft`, `rgt`) VALUES ('3', 'Red', '3', '6');
INSERT INTO `jpa`.`tree` (`id`, `name`, `lft`, `rgt`) VALUES ('4', 'Cherry', '4', '5');
INSERT INTO `jpa`.`tree` (`id`, `name`, `lft`, `rgt`) VALUES ('5', 'Yellow', '7', '10');
INSERT INTO `jpa`.`tree` (`id`, `name`, `lft`, `rgt`) VALUES ('6', 'Banana', '8', '9');
INSERT INTO `jpa`.`tree` (`id`, `name`, `lft`, `rgt`) VALUES ('7', 'Meat', '12', '17');
INSERT INTO `jpa`.`tree` (`id`, `name`, `lft`, `rgt`) VALUES ('8', 'Beef', '13', '14');
INSERT INTO `jpa`.`tree` (`id`, `name`, `lft`, `rgt`) VALUES ('9', 'Pork', '15', '16');

CREATE VIEW `treeview` AS 
SELECT 
  `a`.`id` AS `id`,
  `a`.`name` AS `name`,
  `a`.`lft` AS `lft`,
  `a`.`rgt` AS `rgt`,
  `CountLayer` (`a`.`id`) AS `layer` 
FROM
  `tree` `a`

基於層次計算函數，我們建立一個檢視，新增了新的記錄節點層次的數列：

> CREATE FUNCTION `CountLayer` (`node_id` INT) RETURNS INT (11) 
BEGIN
    DECLARE result INT (10) DEFAULT 0 ;
    DECLARE lftid INT;
    DECLARE rgtid INT;
    SELECT lft,rgt INTO lftid, rgtid FROM tree WHERE id = node_id;
    SELECT COUNT(*) INTO result  FROM tree WHERE lft <= lftid AND rgt >= rgtid;
    RETURN (result);
END

建立儲存過程，用於計算給定節點的所有子孫節點及相應的層次：

CREATE  PROCEDURE `GetChildrenNodeList`(IN `node_id` INT)
BEGIN
DECLARE lftid INT;
DECLARE rgtid INT;
SELECT lft,rgt INTO lftid,rgtid FROM tree WHERE id= node_id;
SELECT * FROM treeview WHERE lft BETWEEN lftid AND rgtid ORDER BY lft ASC;
END

現在，我們使用上面的儲存過程來計算節點Fruit所有子孫節點及對應層次，查詢結果如下：

從上面的實現中，我們可以看出採用左右值編碼的設計方案，在進行樹的查詢遍歷時，只需要進行2次資料庫查詢，消除了遞迴，再加上查詢條件都是數位的比較，查詢的效率是極高的，隨著樹規模的不斷擴大，基於左右值編碼的設計方案將比傳統的遞迴方案查詢效率提高更多。當然，前面我們只給出了一個簡單的獲取節點子孫的演演算法，真正地使用這棵樹我們需要實現插入、刪除同層平移節點等功能。

（2）獲取某節點的族譜路徑

假定我們要獲得某節點的族譜路徑，則根據左、右值分析只需要一條SQL語句即可完成，以Fruit為例：SELECT* FROM tree WHERE lft < 2 AND rgt > 11 ORDER BY lft ASC ，相對完整的儲存過程：

CREATE PROCEDURE `GetParentNodePath`(IN `node_id` INT)
BEGIN
DECLARE lftid INT;
DECLARE rgtid INT;
SELECT lft,rgt INTO lftid,rgtid FROM tree WHERE id= node_id;
SELECT * FROM treeview WHERE lft < lftid AND rgt > rgtid ORDER BY lft ASC;
END

（3）為某節點新增子孫節點

假定我們要在節點「Red」下新增一個新的子節點「Apple」，該樹將變成如下圖所示，其中紅色節點為新增節點。

CREATE  PROCEDURE `AddSubNode`(IN `node_id` INT,IN `node_name` VARCHAR(64))
BEGIN
   DECLARE rgtid INT;
   DECLARE t_error INT DEFAULT 0;  
   DECLARE CONTINUE HANDLER FOR SQLEXCEPTION SET t_error=1; -- 出錯處理 
   SELECT rgt INTO rgtid FROM tree WHERE id= node_id; 
   START TRANSACTION;
        UPDATE tree SET rgt = rgt + 2 WHERE rgt >= rgtid;
        UPDATE tree SET lft = lft + 2 WHERE lft >= rgtid;
        INSERT INTO tree (NAME,lft,rgt) VALUES(node_name,rgtid,rgtid+1);    
    IF t_error =1 THEN  
     ROLLBACK;
    ELSE
      COMMIT;
    END IF;
END

（4）刪除某節點

如果我們想要刪除某個節點，會同時刪除該節點的所有子孫節點，而這些被刪除的節點的個數為：(被刪除節點的右值 – 被刪除節點的左值+ 1) / 2，而剩下的節點左、右值在大於被刪除節點左、右值的情況下會進行調整。來看看樹會發生什麼變化，以Beef為例，刪除效果如下圖所示。

則我們可以構造出相應的儲存過程：

CREATE PROCEDURE `DelNode`(IN `node_id` INT)
BEGIN
   DECLARE lftid INT;
     DECLARE rgtid INT;
   DECLARE t_error INT DEFAULT 0;  
   DECLARE CONTINUE HANDLER FOR SQLEXCEPTION SET t_error=1; -- 出錯處理 
   SELECT lft,rgt INTO lftid,rgtid FROM tree WHERE id= node_id;
   START TRANSACTION;
       DELETE FROM tree WHERE lft >= lftid AND rgt <= rgtid;
       UPDATE tree SET lft = lft -(rgtid - lftid  + 1) WHERE lft > lftid;
       UPDATE tree SET rgt = rgt -(rgtid - lftid  + 1) WHERE rgt >rgtid;
    IF t_error =1 THEN  
     ROLLBACK;
    ELSE
      COMMIT;
    END IF;

END