中文字幕av专区_日韩电影在线播放_精品国产精品久久一区免费式_av在线免费观看网站

溫馨提示×

溫馨提示×

您好,登錄后才能下訂單哦!

密碼登錄×
登錄注冊×
其他方式登錄
點擊 登錄注冊 即表示同意《億速云用戶服務條款》

Mysql樹形結構的數據庫表設計是怎樣的

發布時間:2021-09-24 17:26:57 來源:億速云 閱讀:265 作者:柒染 欄目:開發技術

今天就跟大家聊聊有關Mysql樹形結構的數據庫表設計是怎樣的,可能很多人都不太了解,為了讓大家更加了解,小編給大家總結了以下內容,希望大家根據這篇文章可以有所收獲。

    前言

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

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

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

    一、基本數據

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

    Mysql樹形結構的數據庫表設計是怎樣的

    二、繼承關系驅動的設計

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

    Mysql樹形結構的數據庫表設計是怎樣的

    這種方案的優點很明顯:設計和實現自然而然,非常直觀和方便。缺點當然也是非 常的突出:由于直接地記錄了節點之間的繼承關系,因此對Tree的任何CRUD操作都將是低效的,這主要歸根于頻繁的“遞歸”操作,遞歸過程不斷地訪問數據庫,每次數據庫IO都會有時間開銷。當然,這種方案并非沒有用武之地,在Tree規模相對較小的情況下,我們可以借助于緩存機制來做優化,將Tree的信息載入內存進行處理,避免直接對數據庫IO操作的性能開銷。

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

    在基于數據庫的一般應用中,查詢的需求總要大于刪除和修改。為了避免對于樹形結構查詢時的“遞歸”過程,基于Tree的前序遍歷設計一種全新的無遞歸查詢、無限分組的左右值編碼方案,來保存該樹的數據。

    Mysql樹形結構的數據庫表設計是怎樣的

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

    Mysql樹形結構的數據庫表設計是怎樣的

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

    四、樹形結構CRUD算法

    (1)獲取某節點的子孫節點

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

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

    查詢結果如下所示:

    Mysql樹形結構的數據庫表設計是怎樣的

    那么某個節點到底有多少的子孫節點呢?通過該節點的左、右值我們可以將其子孫節點圈進來,則子孫總數 = (右值 – 左值– 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所有子孫節點及對應層次,查詢結果如下:

    Mysql樹形結構的數據庫表設計是怎樣的

    從上面的實現中,我們可以看出采用左右值編碼的設計方案,在進行樹的查詢遍歷時,只需要進行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”,該樹將變成如下圖所示,其中紅色節點為新增節點。

    Mysql樹形結構的數據庫表設計是怎樣的

    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為例,刪除效果如下圖所示。

    Mysql樹形結構的數據庫表設計是怎樣的

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

    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

    五、總結

    我們可以對這種通過左右值編碼實現無限分組的樹形結構Schema設計方案做一個總結:

    (1)優點:在消除了遞歸操作的前提下實現了無限分組,而且查詢條件是基于整形數字的比較,效率很高。

    (2)缺點:節點的添加、刪除及修改代價較大,將會涉及到表中多方面數據的改動。

    看完上述內容,你們對Mysql樹形結構的數據庫表設計是怎樣的有進一步的了解嗎?如果還想了解更多知識或者相關內容,請關注億速云行業資訊頻道,感謝大家的支持。

    向AI問一下細節

    免責聲明:本站發布的內容(圖片、視頻和文字)以原創、轉載和分享為主,文章觀點不代表本網站立場,如果涉及侵權請聯系站長郵箱:is@yisu.com進行舉報,并提供相關證據,一經查實,將立刻刪除涉嫌侵權內容。

    AI

    额济纳旗| 和龙市| 儋州市| 牡丹江市| 巴东县| 雷州市| 永福县| 松潘县| 永靖县| 东辽县| 广宗县| 尼玛县| 登封市| 通辽市| 德江县| 舒城县| 泾川县| 胶南市| 太保市| 武平县| 达孜县| 房产| 老河口市| 湾仔区| 循化| 新沂市| 新郑市| 西藏| 通化市| 武宁县| 辰溪县| 连州市| 临高县| 镇远县| 德江县| 洛宁县| 柘荣县| 岢岚县| 阳曲县| 三原县| 奉节县|