欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Mysql樹形結(jié)構(gòu)的數(shù)據(jù)庫表設(shè)計(jì)方案

 更新時(shí)間：2021年09月22日 11:37:51   作者：mokingone  
樹形結(jié)構(gòu)對大家來說應(yīng)該都不陌生,在日常開發(fā)中經(jīng)常會遇到,下面這篇文章主要給大家介紹了關(guān)于Mysql樹形結(jié)構(gòu)的數(shù)據(jù)庫表設(shè)計(jì)的相關(guān)資料,文中通過示例代碼的非常詳細(xì),需要的朋友可以參考下

前言

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

程序設(shè)計(jì)過程中，我們常常用樹形結(jié)構(gòu)來表征某些數(shù)據(jù)的關(guān)聯(lián)關(guān)系，如企業(yè)上下級部門、欄目結(jié)構(gòu)、商品分類等等，通常而言，這些樹狀結(jié)構(gòu)需要借助于數(shù)據(jù)庫完成持久化。然而目前的各種基于關(guān)系的數(shù)據(jù)庫，都是以二維表的形式記錄存儲數(shù)據(jù)信息，因此是不能直接將Tree存入DBMS，設(shè)計(jì)合適的Schema及其對應(yīng)的CRUD算法是實(shí)現(xiàn)關(guān)系型數(shù)據(jù)庫中存儲樹形結(jié)構(gòu)的關(guān)鍵。

理想中樹形結(jié)構(gòu)應(yīng)該具備如下特征：數(shù)據(jù)存儲冗余度小、直觀性強(qiáng)；檢索遍歷過程簡單高效；節(jié)點(diǎn)增刪改查CRUD操作高效。無意中在網(wǎng)上搜索到一種很巧妙的設(shè)計(jì)，原文是英文，看過后感覺有點(diǎn)意思，于是便整理了一下。本文將介紹兩種樹形結(jié)構(gòu)的Schema設(shè)計(jì)方案：一種是直觀而簡單的設(shè)計(jì)思路，另一種是基于左右值編碼的改進(jìn)方案。

一、基本數(shù)據(jù)

本文列舉了一個(gè)食品族譜的例子進(jìn)行講解，通過類別、顏色和品種組織食品，樹形結(jié)構(gòu)圖如下：

這里寫圖片描述

二、繼承關(guān)系驅(qū)動的設(shè)計(jì)

對樹形結(jié)構(gòu)最直觀的分析莫過于節(jié)點(diǎn)之間的繼承關(guān)系上，通過顯示地描述某一節(jié)點(diǎn)的父節(jié)點(diǎn)，從而能夠建立二維的關(guān)系表，則這種方案的Tree表結(jié)構(gòu)通常設(shè)計(jì)為：{Node_id,Parent_id}，上述數(shù)據(jù)可以描述為如下圖所示：

這里寫圖片描述

這種方案的優(yōu)點(diǎn)很明顯：設(shè)計(jì)和實(shí)現(xiàn)自然而然，非常直觀和方便。缺點(diǎn)當(dāng)然也是非 常的突出：由于直接地記錄了節(jié)點(diǎn)之間的繼承關(guān)系，因此對Tree的任何CRUD操作都將是低效的，這主要?dú)w根于頻繁的“遞歸”操作，遞歸過程不斷地訪問數(shù)據(jù)庫，每次數(shù)據(jù)庫IO都會有時(shí)間開銷。當(dāng)然，這種方案并非沒有用武之地，在Tree規(guī)模相對較小的情況下，我們可以借助于緩存機(jī)制來做優(yōu)化，將Tree的信息載入內(nèi)存進(jìn)行處理，避免直接對數(shù)據(jù)庫IO操作的性能開銷。

三、基于左右值編碼的設(shè)計(jì)

在基于數(shù)據(jù)庫的一般應(yīng)用中，查詢的需求總要大于刪除和修改。為了避免對于樹形結(jié)構(gòu)查詢時(shí)的“遞歸”過程，基于Tree的前序遍歷設(shè)計(jì)一種全新的無遞歸查詢、無限分組的左右值編碼方案，來保存該樹的數(shù)據(jù)。

這里寫圖片描述

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

這里寫圖片描述

依據(jù)此設(shè)計(jì)，我們可以推斷出所有左值大于2，并且右值小于11的節(jié)點(diǎn)都是Fruit的后續(xù)節(jié)點(diǎn)，整棵樹的結(jié)構(gòu)通過左值和右值存儲了下來。然而，這還不夠，我們的目的是能夠?qū)溥M(jìn)行CRUD操作，即需要構(gòu)造出與之配套的相關(guān)算法。

四、樹形結(jié)構(gòu)CRUD算法

（1）獲取某節(jié)點(diǎn)的子孫節(jié)點(diǎn)

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

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

查詢結(jié)果如下所示：

這里寫圖片描述

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

創(chuàng)建表

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`

基于層次計(jì)算函數(shù)，我們創(chuàng)建一個(gè)視圖，添加了新的記錄節(jié)點(diǎn)層次的數(shù)列：

> 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

創(chuàng)建存儲過程，用于計(jì)算給定節(jié)點(diǎn)的所有子孫節(jié)點(diǎn)及相應(yīng)的層次：

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

 現(xiàn)在，我們使用上面的存儲過程來計(jì)算節(jié)點(diǎn)Fruit所有子孫節(jié)點(diǎn)及對應(yīng)層次，查詢結(jié)果如下：

這里寫圖片描述

從上面的實(shí)現(xiàn)中，我們可以看出采用左右值編碼的設(shè)計(jì)方案，在進(jìn)行樹的查詢遍歷時(shí)，只需要進(jìn)行2次數(shù)據(jù)庫查詢，消除了遞歸，再加上查詢條件都是數(shù)字的比較，查詢的效率是極高的，隨著樹規(guī)模的不斷擴(kuò)大，基于左右值編碼的設(shè)計(jì)方案將比傳統(tǒng)的遞歸方案查詢效率提高更多。當(dāng)然，前面我們只給出了一個(gè)簡單的獲取節(jié)點(diǎn)子孫的算法，真正地使用這棵樹我們需要實(shí)現(xiàn)插入、刪除同層平移節(jié)點(diǎn)等功能。

（2）獲取某節(jié)點(diǎn)的族譜路徑

假定我們要獲得某節(jié)點(diǎn)的族譜路徑，則根據(jù)左、右值分析只需要一條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）為某節(jié)點(diǎn)添加子孫節(jié)點(diǎn)

      假定我們要在節(jié)點(diǎn)“Red”下添加一個(gè)新的子節(jié)點(diǎn)“Apple”，該樹將變成如下圖所示，其中紅色節(jié)點(diǎn)為新增節(jié)點(diǎn)。

這里寫圖片描述

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; -- 出錯(cuò)處理 
   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）刪除某節(jié)點(diǎn)

      如果我們想要?jiǎng)h除某個(gè)節(jié)點(diǎn)，會同時(shí)刪除該節(jié)點(diǎn)的所有子孫節(jié)點(diǎn)，而這些被刪除的節(jié)點(diǎn)的個(gè)數(shù)為：(被刪除節(jié)點(diǎn)的右值 – 被刪除節(jié)點(diǎn)的左值+ 1) / 2，而剩下的節(jié)點(diǎn)左、右值在大于被刪除節(jié)點(diǎn)左、右值的情況下會進(jìn)行調(diào)整。來看看樹會發(fā)生什么變化，以Beef為例，刪除效果如下圖所示。

這里寫圖片描述

則我們可以構(gòu)造出相應(yīng)的存儲過程：

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; -- 出錯(cuò)處理 
   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

五、總結(jié)

我們可以對這種通過左右值編碼實(shí)現(xiàn)無限分組的樹形結(jié)構(gòu)Schema設(shè)計(jì)方案做一個(gè)總結(jié)：

（1）優(yōu)點(diǎn)：在消除了遞歸操作的前提下實(shí)現(xiàn)了無限分組，而且查詢條件是基于整形數(shù)字的比較，效率很高。

（2）缺點(diǎn)：節(jié)點(diǎn)的添加、刪除及修改代價(jià)較大，將會涉及到表中多方面數(shù)據(jù)的改動。

參考文獻(xiàn)

http://www.dbjr.com.cn/article/223579.htm

相關(guān)文章

最新評論