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

樹形結構數(shù)據(jù)庫表Schema設計的兩種方案

 更新時間:2021年09月22日 11:36:39   作者:MONKEY_D_MENG  
程序設計過程中,我們常常用樹形結構來表征某些數(shù)據(jù)的關聯(lián)關系,如企業(yè)上下級部門、欄目結構、商品分類等等,下面這篇文章主要給大家介紹了關于樹形結構數(shù)據(jù)庫表Schema設計的兩種方案,需要的朋友可以參考下

前言

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

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

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

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

二、繼承關系驅(qū)動的Schema設計

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


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

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

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


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

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

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

四、樹形結構CRUD算法

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

只需要一條SQL語句,即可返回該節(jié)點子孫節(jié)點的前序遍歷列表,以Fruit為例:SELECT* FROM Tree WHERE Lft BETWEEN 2 AND 11 ORDER BY Lft ASC。查詢結果如下所示:

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

CREATE FUNCTION dbo.CountLayer
(
    @node_id int
)
RETURNS int
AS
begin
	declare @result int
	set @result = 0
	declare @lft int
	declare @rgt int
	if exists(select Node_id from Tree where Node_id = @node_id)
	begin
		select @lft = Lft, @rgt = Rgt from Tree where node_id = @node_id
		select @result = count(*) from Tree where Lft <= @lft and Rgt >= @rgt
	end
	return @result
end
GO

基于層次計算函數(shù),我們創(chuàng)建一個視圖,添加了新的記錄節(jié)點層次的數(shù)列:

CREATE VIEW dbo.TreeView
AS
SELECT Node_id, Name, Lft, Rgt, dbo.CountLayer(Node_id) AS Layer FROM dbo.Tree ORDER BY Lft
GO

創(chuàng)建存儲過程,用于計算給定節(jié)點的所有子孫節(jié)點及相應的層次:

CREATE PROCEDURE [dbo].[GetChildrenNodeList]
(
	@node_id int
)
AS
declare @lft int
declare @rgt int
if exists(select Node_id from Tree where node_id = @node_id)
	begin
		select @lft = Lft, @rgt = Rgt from Tree where Node_id = @node_id
		select * from TreeView where Lft between @lft and @rgt order by Lft ASC
	end
GO

現(xiàn)在,我們使用上面的存儲過程來計算節(jié)點Fruit所有子孫節(jié)點及對應層次,查詢結果如下:


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

 (2)獲取某節(jié)點的族譜路徑

    假定我們要獲得某節(jié)點的族譜路徑,則根據(jù)左、右值分析只需要一條SQL語句即可完成,以Fruit為例:SELECT* FROM Tree WHERE Lft < 2 AND Rgt > 11 ORDER BY Lft ASC ,相對完整的存儲過程:

CREATE PROCEDURE [dbo].[GetParentNodePath]
(
	@node_id int
)
AS
declare @lft int
declare @rgt int
if exists(select Node_id from Tree where Node_id = @node_id)
	begin
		select @lft = Lft, @rgt = Rgt from Tree where Node_id = @node_id
		select * from TreeView where Lft < @lft and Rgt > @rgt order by Lft ASC
	end
GO

(3)為某節(jié)點添加子孫節(jié)點

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


仔細觀察圖中節(jié)點左右值變化,相信大家都應該能夠推斷出如何寫SQL腳本了吧。我們可以給出相對完整的插入子節(jié)點的存儲過程:

CREATE PROCEDURE [dbo].[AddSubNode]
(
	@node_id int,
	@node_name varchar(50)
)
AS
declare @rgt int
if exists(select Node_id from Tree where Node_id = @node_id)
	begin
		SET XACT_ABORT ON
		BEGIN TRANSCTION
		select @rgt = Rgt from Tree where Node_id = @node_id
		update Tree set Rgt = Rgt + 2 where Rgt >= @rgt
		update Tree set Lft = Lft + 2 where Lft >= @rgt
		insert into Tree(Name, Lft, Rgt) values(@node_name, @rgt, @rgt + 1)
		COMMIT TRANSACTION
		SET XACT_ABORT OFF
	end
GO

(4)刪除某節(jié)點

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

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

CREATE PROCEDURE [dbo].[DelNode]
(
	@node_id int
)
AS
declare @lft int
declare @rgt int
if exists(select Node_id from Tree where Node_id = @node_id)
	begin
		SET XACT_ABORT ON
		BEGIN TRANSCTION
			select @lft = Lft, @rgt = Rgt from Tree where Node_id = @node_id
			delete from Tree where Lft >= @lft and Rgt <= @rgt
			update Tree set Lft = Lft – (@rgt - @lft + 1) where Lft > @lft
			update Tree set Rgt = Rgt – (@rgt - @lft + 1) where Rgt > @rgt
			COMMIT TRANSACTION
		SET XACT_ABORT OFF
	end
GO

五、總結

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

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

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

當然,本文只給出了幾種比較常見的CRUD算法的實現(xiàn),我們同樣可以自己添加諸如同層節(jié)點平移、節(jié)點下移、節(jié)點上移等操作。有興趣的朋友可以自己動手編碼實現(xiàn)一下,這里不在列舉了。值得注意的是,實現(xiàn)這些算法可能會比較麻煩,會涉及到很多條update語句的順序執(zhí)行,如果順序調(diào)度考慮不周詳,出現(xiàn)Bug的話將會對整個樹形結構表產(chǎn)生驚人的破壞。因此,在對樹形結構進行大規(guī)模修改的時候,可以采用臨時表做中介,以降低代碼的復雜度,同時,強烈推薦在做修改之前對表進行完整備份,以備不時之需。在以查詢?yōu)橹鞯慕^大多數(shù)基于數(shù)據(jù)庫的應用系統(tǒng)中,該方案相比傳統(tǒng)的由父子繼承關系構建的數(shù)據(jù)庫Schema更為適用。

到此這篇關于樹形結構數(shù)據(jù)庫表Schema設計方案的文章就介紹到這了,更多相關樹形結構數(shù)據(jù)庫表Schema設計內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家!

參考文獻:《Storing Hierarchical Data in a Database Article

相關文章

  • datagrip如何找到數(shù)據(jù)庫和表

    datagrip如何找到數(shù)據(jù)庫和表

    這篇文章主要介紹了datagrip入坑指南(如何找到數(shù)據(jù)庫和表)的相關知識,本文給大家介紹的非常詳細,對大家的學習或工作具有一定的參考借鑒價值,需要的朋友參考下吧
    2020-09-09
  • SQL修改語法語句梳理總結

    SQL修改語法語句梳理總結

    這篇文章主要介紹了關于SQL修改語句的語法梳理總結,文中附含詳細的修改語句示例,有需要的朋友 可以借鑒參考下,希望能夠有所幫助
    2021-10-10
  • 一文告訴你Sql的執(zhí)行順序是怎樣的

    一文告訴你Sql的執(zhí)行順序是怎樣的

    這篇文章主要給大家介紹了關于Sql的執(zhí)行順序是怎樣的,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧
    2020-12-12
  • 寫出高性能SQL語句的35條方法分析

    寫出高性能SQL語句的35條方法分析

    高性能的SQL語句能提高頁面的執(zhí)行效率,讓你的服務器運行的更為流暢,所以大家在以后的使用過程中,盡量的考慮到效率。
    2009-10-10
  • 詳解Navicat簡單使用方法

    詳解Navicat簡單使用方法

    這篇文章主要介紹了Navicat簡單使用方法,本文通過圖文并茂的形式給大家介紹的非常詳細,對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下
    2020-11-11
  • 數(shù)據(jù)庫設計技巧奉送了

    數(shù)據(jù)庫設計技巧奉送了

    數(shù)據(jù)庫設計技巧奉送了...
    2007-03-03
  • sql注入教程之類型以及提交注入

    sql注入教程之類型以及提交注入

    所謂SQL注入,就是通過把SQL命令插入到Web表單提交或輸入域名或頁面請求的查詢字符串,這篇文章主要給大家介紹了關于sql注入教程之類型以及提交注入的相關資料,需要的朋友可以參考下
    2021-07-07
  • SQL查詢語法知識梳理總結

    SQL查詢語法知識梳理總結

    這篇文章主要為大家介紹了關于SQL查詢語法的知識梳理總結,文中附含詳細的查詢語法示例,有需要的朋友可以借鑒參考下,希望能夠有所幫助
    2021-10-10
  • 使用Bucardo5實現(xiàn)PostgreSQL的主數(shù)據(jù)庫復制

    使用Bucardo5實現(xiàn)PostgreSQL的主數(shù)據(jù)庫復制

    這篇文章主要介紹了使用Bucardo5實現(xiàn)PostgreSQL的主數(shù)據(jù)庫復制,作者基于AWS給出演示,需要的朋友可以參考下
    2015-04-04
  • MySQL與Oracle 差異比較之四條件循環(huán)語句

    MySQL與Oracle 差異比較之四條件循環(huán)語句

    這篇文章主要介紹了MySQL與Oracle 差異比較之四條件循環(huán)語句,需要的朋友可以參考下
    2017-04-04

最新評論